450
\$\begingroup\$

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.

To post to the Sandbox, scroll to the bottom of this page or click on the "Add Proposal" link below, 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. 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, replace the post here with a link to the challenge and delete it.

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

The Sandbox works best if you sort posts by "active".

Add Proposal

Search the Sandbox

Browse your pending proposals

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]

\$\endgroup\$
  • 2
    \$\begingroup\$ Suggestion: instead of having a notice on the top answer ("note: if you are..."), you'd better just put a moderator notice below the question \$\endgroup\$ – nicael Mar 19 '18 at 19:35
  • 3
    \$\begingroup\$ @nicael We can only choose from three post notices: citation needed, current event, and insufficient explanation. \$\endgroup\$ – Dennis Apr 7 '18 at 14:43
  • \$\begingroup\$ If you remove a post but didn't post it you can replace the text body with [](lots of text here to reach the min chars) to make it much smaller when removed \$\endgroup\$ – Christopher Apr 13 '18 at 17:54
  • 5
    \$\begingroup\$ @Christopher Please don't do that for old proposals. It clutters the first page with an answer nobody cares about anymore, instead of staying hidden on page 10 where it will bother nobody. \$\endgroup\$ – Dennis Apr 13 '18 at 18:17
  • \$\begingroup\$ @Dennis ? what are you talking about. As if if you didn't post it like you just removed you own sandbox because dupe or something \$\endgroup\$ – Christopher Apr 13 '18 at 18:18
  • 4
    \$\begingroup\$ @Christopher If your proposal is still on the first few pages, you can replace the proposal with a stub to save vertical space on these pages. However, if your proposal is already on page 10, editing your proposal will bump it to page 1, where space is more precious than on page 10. \$\endgroup\$ – Dennis Apr 13 '18 at 18:21
  • \$\begingroup\$ @Dennis ohh that makes sense \$\endgroup\$ – Christopher Apr 13 '18 at 18:25
  • \$\begingroup\$ codegolf.meta.stackexchange.com/questions/12599/… \$\endgroup\$ – Redwolf Programs Apr 17 '18 at 17:38
  • 1
    \$\begingroup\$ Maybe it's time to consider cleaning some of this up a bit. There's just too much to go through and some of these proposals are years old and obviously not going anywhere (even some of the good ones). Perhaps cull anything that is two years old and has likewise been inactive for as long? \$\endgroup\$ – ouflak Aug 6 '18 at 9:07
  • 1
    \$\begingroup\$ @ouflak You can sort posts by "active". That seems to resolve all of the problems you describe. \$\endgroup\$ – FryAmTheEggman Sep 27 '18 at 19:04
  • \$\begingroup\$ I already posted this, but codegolf.stackexchange.com/questions/176599/… \$\endgroup\$ – 2br-2b Nov 27 '18 at 2:38
  • \$\begingroup\$ How are tags added to questions? \$\endgroup\$ – guest271314 Jan 9 at 7:51
  • \$\begingroup\$ It seems like there is a rollback war with moderators and the Community user to add and remove the featured tag. \$\endgroup\$ – smileycreations15 Mar 21 at 21:13
  • 3
    \$\begingroup\$ @smileycreations15 That's unfortunately unavoidable. Community is an automatic script, and, since most featured questions are only temporarily so, it assumes that we don't want this question to be featured forever. However, we do, so a mod has to edit the tag in every now and then. \$\endgroup\$ – Erik the Outgolfer Mar 24 at 15:22
  • 3
    \$\begingroup\$ @EriktheOutgolfer Yeah. Maybe they can create a special [featured-pin] tag which will both feature it and pin it from removal by the Community user. \$\endgroup\$ – smileycreations15 Mar 24 at 17:20

2479 Answers 2479

4
\$\begingroup\$

Peter Piper and the Peck of Pickled Peppers

tags:


Without an introduction, output the following tongue twister:

Peter Piper picked a peck of pickled peppers.
A peck of pickled peppers Peter Piper picked.
If Peter Piper picked a peck of pickled peppers,
Where's the peck of pickled peppers Peter Piper picked?

with or without a trailing newline.

This is , so shortest code wins.

\$\endgroup\$
  • \$\begingroup\$ I did some searching for duplicates, I came up with: this and this. There were a couple others that were also rather similar (slim shady and old macdonald), but they had a source restriction or some input as well. I'm not sure if any of them are duplicates, but these seem awfully close. \$\endgroup\$ – FryAmTheEggman Jul 26 '16 at 21:05
  • 3
    \$\begingroup\$ I wish the words didn't come in the same chunks. The substrings "Peter Piper picked" and "peck of pickled peppers" are most of the text, and the rest has little structure: X a Y. A Y X. If X a Y, Where's the Y X? Is there another tongue-twister where the words are permuted more? \$\endgroup\$ – xnor Jul 27 '16 at 1:21
4
\$\begingroup\$

Transpose a Ragged Array

Given an array of arrays of integers where the rows may not be of equal length, pad those rows with nulls, and transpose the array.

Rules

  • Use any sane input for the array.
  • Specify which null(s) you are using for this function.
  • The output should be a transposed array, printed in whatever way is sane for your language.
  • This is code golf. Aim for the shortest code possible.

Test cases

I: [[1, 2], [3], [4, 5]]          # Padding with nil here
O: [[1, 3, 4], [2, nil, 5]]

I: [[1], [2, 3], [4, 5]]
O: [[1, 2, 4], [nil, 3, 5]]

I: [[1, 4, 5], [8, 3, 2], [1, 7, 9, 6]]
O: [[1, 8, 1], [4, 3, 7], [5, 2, 9], [nil, nil, 6]]

I: [[1], [2]]
O: [[1, 2]]

I: [[1, 2]]
O: [[1], [2]]

I: [[4, 5, 6, 7], [8, 9]]                  # Padding with spaces here
O: [[4, 8], [5, 9], [6, ' '], [7, ' ']]    # as an example of a different null

As always, if the problem is unclear, please let me know. Good luck and good golfing!

\$\endgroup\$
  • \$\begingroup\$ Having arrays that contain both integers and strings seems odd (and unrelated to the challenge) to me. \$\endgroup\$ – Nathan Merrill Aug 19 '16 at 6:29
  • \$\begingroup\$ @NathanMerrill In my head, I was trying to allow as many nulls as possible by restricting what data the arrays would have. You're right, though, and I have removed the reference to numbers and strings. \$\endgroup\$ – Sherlock9 Aug 19 '16 at 6:32
  • \$\begingroup\$ There's still a test case with it :) \$\endgroup\$ – Nathan Merrill Aug 19 '16 at 13:54
  • \$\begingroup\$ @NathanMerrill That's because I still want arrays that can contain any data. \$\endgroup\$ – Sherlock9 Aug 19 '16 at 13:59
  • \$\begingroup\$ @NathanMerrill Alright I rewrote the test case \$\endgroup\$ – Sherlock9 Aug 19 '16 at 17:00
  • \$\begingroup\$ Perhaps "ragged" is a better term for "uneven" \$\endgroup\$ – Conor O'Brien Sep 10 '16 at 15:54
  • \$\begingroup\$ Does the "null" have to be constant or can it depend on the input? \$\endgroup\$ – Dennis Sep 16 '16 at 6:20
  • \$\begingroup\$ @Dennis, I think the nulls should be constant for all inputs. \$\endgroup\$ – Sherlock9 Sep 16 '16 at 10:01
4
\$\begingroup\$

Play a 1D chess variant

in this challenge, you must create a bot that plays a 1d variant I created, featuring all leaper pieces, and a 15 long board.

Esolangs are encouraged to participate

Game Rules

Goal

To capture the opponents royal (king/queen).

Board

The board is 15 squares long

Player _______________________________ Player
 one   |_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|   two
       player1 side       player2 side

Each player has their side of the board. (note that while playing, you will always be on the left side of the board). You have six squares that belong to you, the opponent has six of their squares, and three squares in the middle are unowned.

Setting up

At the start of the game, you will place your pieces into a configuration of your choice. The pieces will be set independently of each other; this game does not have perfect information. When setting up, you will pick where to place your four pieces, and whether they will be reversed (see next section). You may only place your pieces in your owned squares.

Pieces

There are 4 / 8 pieces; there are 4 distinct pieces, which you can have reversed, and unreversed. I have given them distinct names. Their movements are detailed here.

reversed

reversed means that all the moves of these pieces are reversed in their direction; 2 forward becomes 2 back, three back becomes three forward.

Capture means to move to a space occupied by an enemy piece, and remove that piece from the game. Move means to move to a space occupied by no pieces.

Ascii "diagrams" have been provided. P denotes the piece being showed, $ denotes a space the piece can move to, X a place the piece can capture on, # a piece can move and capture on. Diagrams are the same for both pieces in a pair, because one simply executes the moves backwards.

You must have exactly 4 pieces on the board, and have exactly one from each of the pairs below.

Footman (f)/Coward (c)

The footman may move to an empty space one (1) forward, and capture two (2) forward.

The coward may move to an empty space one (1) backward, and capture two (2) backward.

P$X
Horse (h)/spider (s)

The horse may move to an empty space two (2) or three (3) forward, and move or capture one (1) backward.

The spider may move to an empty space two (2) or three (3) backward, and move or capture one (1) forward.

#P $$
Archer (a)/Trickster (t)

(I doubt anyone will use trickster unironically)

The archer may move two (2) squares backward, one (1) forward, and may capture four (4) steps forward

The trickster may move two (2) squares forward, one (1) backward, and may capture four (4) steps backward

I have included some black and white squares for clarity in distance

# # # #
$ P$  X
King (k)/Queen (q)

Both Royal pieces will end the game when captured.

The king may move or capture one (1) backward

The queen may move or capture one (1) forward

#P

Misc.

Check does not exist: Royal pieces may be left en prise, capture of them results in a win for the capturing side.

There is no (pawn) promotion of any kind

A piece may not attempt to move of the board; the board is a fixed size and does not wrap.

Programs

Programs will take input. When they take input of "0", or a specific input of your choosing, they will output a setup for the game. when they take input "1", or a specific input of your choosing, they will then receive input of the board, and output a move. (the program will be run multiple times)

Moving

To move, you will output the square that the piece is currently on, and the space where you wish to move the piece to, or have the piece capture on. The format is as so (in regex):

[0-9a-e]\n?[0-9a-e]\n?

The board is zero indexed, a piece on the first square is on square 0.

There should be exactly 2 non-newline characters in the output

Input

when it is your turn to move, you will receive input. The input you receive will represent the pieces in the playing field. The input will fit the regex here:

[fFcChHsSaAtTkKqQ ]{15}

Caps represent enemy pieces, lowercase represent your pieces.

when you receive the board positions, you will always have the perspective of player one

WIP, will do more later

Sandbox

What should happen if bots enter an infinite loop? I could just make a draw on a time limit, but that seems not so great, since it is hard for bots to know when they are doing this.

Also just other feedback in general

\$\endgroup\$
  • \$\begingroup\$ Maybe put the ASCII characters used to represent the pieces next to each description so we know what each piece is? It looks pretty vague right now. Also, the king and queen together seems redundant - maybe have it one or the other? \$\endgroup\$ – Qwerp-Derp Oct 4 '16 at 5:47
  • \$\begingroup\$ 1. The solution to infinite loops would seem to be automatic draw on three-fold repetition. 2. Is the Nash equilibrium pure or mixed? \$\endgroup\$ – Peter Taylor Oct 4 '16 at 7:33
  • \$\begingroup\$ @PeterTaylor 1. Three-fold repetition== one repetition of position (if bots have no RNG/are determistic, and I don't want non-RNG bots to suffer), and the bots don't know when they are repeating, because they have no memory. I was kind of thinking of maybe removing a square or something, but that would kind of mess up some stuff... I kind of want to introduce some aspects that will change the position, like adding a piece or something. 2. I imagine you are talking about the starting positions, given perfect play. I have no idea, but it's probably an intricate Rock Paper Scissors cycle \$\endgroup\$ – Destructible Lemon Oct 4 '16 at 7:47
  • \$\begingroup\$ When I asked about the Nash equilibrium I'd calculated that the number of starting positions is only a bit over 5000 each, so I thought it would be practical to brute-force. But the number of board positions is quite a bit higher, so it's probably not very practical without spending a lot of money. I'm not going to try writing a game tree searcher tonight to verify that. Re repetition: normally in koth you want to use persistent processes where possible, because otherwise the overhead of launching the program for every single move makes it really slow to score. \$\endgroup\$ – Peter Taylor Oct 4 '16 at 20:57
  • \$\begingroup\$ I was also thinking that maybe I would make the time it takes to win factor into the score, so that riskier strategies can do as well as a perfectly planned program might; It would make a more diverse series of strategies \$\endgroup\$ – Destructible Lemon Oct 4 '16 at 22:46
  • \$\begingroup\$ Is there a limit on how long a turn can take? IMO the obvious solution is a minimax tree, so we'd need to know about how many turns we can look ahead. \$\endgroup\$ – Riley Oct 12 '16 at 15:40
4
\$\begingroup\$

(-: Emotional Programming ;-)

Write the most emotional program you can, i.e. which consists of emoticons as much as possible.

The program should receive a word and print an appropriate emoticon.

Scoring - I'm really not sure about this, and the question will be worthless without a good scoring algorithm. I want to:
1. Avoid giving an advantage to very short programs (e.g. (-:, is 100% emotional).
2. Avoid a meaningless help of emoticons - print '(-:' #(-:(-:(-: and such.
3. Prefer a variety of different emoticons.

Suggestion:
1. Count characters of code.
2. For each emoticon in the code, reduce a character. 2. For N different emoticons used, reduce further 2*N^2 characters.

What's an emoticon? Anything that somewhat resembles a face, or a closed list?

And should I ban Emoticon?

\$\endgroup\$
  • \$\begingroup\$ My suggestion to fix scoring would be to add restrictions to the submissions' output, and have scoring be a function of their code and their output. \$\endgroup\$ – jwrush Aug 31 '13 at 16:32
  • \$\begingroup\$ Thanks @jwrush, Scoring based on output seems to complicate things, and I'm already unclear about my scoring. I changed the required behavior to something more closed. Still, I don't feel the question is good enough. \$\endgroup\$ – ugoren Sep 1 '13 at 4:45
  • 2
    \$\begingroup\$ This seems to have a strong bias towards GolfScript, which produces lots of emoticons naturally. It also seems hard to tighten to an objective spec. \$\endgroup\$ – Peter Taylor Sep 1 '13 at 18:43
  • \$\begingroup\$ @PeterTaylor, I don't like a bias towards GolfScript, but if that was a reason not to post questions, this site would be much smaller. The requirement can be very tight - I can provide a list of words and emoticons, and require translation between them. I'm not sure I want to tighten this way though. \$\endgroup\$ – ugoren Sep 2 '13 at 4:27
  • \$\begingroup\$ I disagree on the first point. I see a difference between GS having an advantage in code golf because it's designed to be terse, and GS having an advantage in a challenge because the challenge actively rewards a property which GS has as a side-effect of its design. Also note that I probably wouldn't be the loudest protestor against a pro-GS bias, but I think it's fair to warn you that other people might protest ;) \$\endgroup\$ – Peter Taylor Sep 2 '13 at 10:53
  • \$\begingroup\$ @PeterTaylor, I wish that was the problem. I don't really how to make this a question that triggers interesting solutions, so it looks like it stays in the sandbox. \$\endgroup\$ – ugoren Sep 8 '13 at 6:54
  • \$\begingroup\$ Might want to forbid comments? \$\endgroup\$ – Justin Nov 28 '13 at 22:22
  • \$\begingroup\$ I think this would only work as a popcon \$\endgroup\$ – Destructible Lemon Nov 3 '16 at 10:19
4
\$\begingroup\$

Create an Autostereogram (Optical Illusion w/ Hidden 3D Shape)

An autostereogram is a type of optical illusion requiring the viewer to, simply put, change distance at which your eyes are trying to view the image. In order to see the hidden image rather than just a nonsensical two-dimensional image, the viewer must either focus their eyes in front of the image (cross-eyed), or behind the image (wall-eyed). Depending on its type, autostereograms may be viewed either way, only cross-eyed, or only wall-eyed. Wall-eyed are the most common.

The illusion below taken from the linked Wikipedia article may only be viewed successfully using the wall-eyed technique. Viewing the full-sized image may help.

https://upload.wikimedia.org/wikipedia/commons/f/fb/Stereogram_Tut_Shark.png

The hidden image is:

A shark

I didn't know they were called autostereograms until today, but I always liked this type of optical illusion, since I found the hidden image easy to spot using the wall-eyed technique.

Your goal is to take a depth map and either:

  1. Take in an image to modify with the map, then return/display the resulting image
  2. Create a random dot autostereogram

The quality of the image must be such that the image is hidden and can be viewed using one of the techniques listed above.

\$\endgroup\$
  • \$\begingroup\$ I've also seen reddit.com/r/crossview which is a similar idea but uses 2 images next to each other to make it look 3d. \$\endgroup\$ – Faraz Masroor Apr 7 '16 at 14:42
  • \$\begingroup\$ I'd like input on whether people would prefer a [popularity-contest] or [code-golf] for this. I'm not sure if answers would be unique enough for a popularity contest. How much quality will users drop for saving bytes? \$\endgroup\$ – mbomb007 Apr 7 '16 at 15:11
  • 1
    \$\begingroup\$ I would clearly go for code-golf and restrict it to random dot autostereogram (which e.g. also needs e.g. the number of points as input). This can be defined quite well. (In a popularity contest people would probably just vote what they can see easily. Furthermore the there would be the question about a validity criterion.) I totally like the idea! \$\endgroup\$ – flawr Apr 11 '16 at 20:19
  • \$\begingroup\$ @flawr The thing is, I actually think random dot ones are much harder when trying to view the hidden image. \$\endgroup\$ – mbomb007 Apr 11 '16 at 20:55
  • 1
    \$\begingroup\$ @mbomb007 Harder to view or harder to produce? (PS: tx.technion.ac.il/~yonie/stereogram.txt) What do you think about ASCII stereograms? It would be quite a bit easier to make a validity criterion. \$\endgroup\$ – flawr Apr 11 '16 at 21:01
  • \$\begingroup\$ From chat, it seems like the consensus is that this question should be narrowed. This could potentially become 3 different questions about autostereograms: using random dots, using an image, and using ASCII. I think I'd like to start with using an image, since its output is easily viewable. \$\endgroup\$ – mbomb007 Apr 12 '16 at 13:49
  • \$\begingroup\$ @flawr Do you think other languages would be able to do what Mathematica can? mathematica.stackexchange.com/a/57108/35531 \$\endgroup\$ – mbomb007 Nov 2 '16 at 16:35
  • \$\begingroup\$ Probably, but the mathemtica version is already quite long, and most other languages will probably need way more code to do the same, which, so I'm afraid, could deter many people from participating. \$\endgroup\$ – flawr Nov 2 '16 at 21:31
  • \$\begingroup\$ @flawr Well, it's not golfed yet. \$\endgroup\$ – mbomb007 Nov 2 '16 at 21:34
4
\$\begingroup\$

Generate a Call Tree

Given a C program, generate a graphical call tree.

A call tree is a tree where the nodes represent stack frames, and the connections represent nested function calls. For example, here is a simple C program and its call tree:

#include <stdio.h>

int foo() {
    return 4;
}

int bar(int a) {
    return a + 2;
}

int baz(int a, int b) {
    return a + foo() + bar(a)*bar(b);
}

int main() {
    int a = baz(1, 2);
    printf("%d\n", a);
    return 0;
}

call tree

Layout

The layout of a call tree is as follows:

  • The top function is always main().
  • On the next level below are all of the functions that main calls, in order of calling (top-to-bottom, left-to-right).
  • On the next level are all of the functions that those functions call, and so on.
  • The leaves of the tree are functions which do not call other functions, or are standard library functions (which are treated as black boxes).
  • Each function (with its argument list) is in a rectangle, large enough that the function name and argument list isn't touching the rectangle's borders.
  • Rectangles must not touch other rectangles.
  • The lines drawn between the rectangles must not touch or cross any line or rectangle other than the two rectangles they are connecting.
  • The text must be a monospaced 14-point font.
  • The colors of the text, rectangles, lines, and background are not important, so long as all text is one color, all rectangles are one color, all lines are one color, the background is a single color, and everything can be clearly distinguished from the background.

Note that the example image above does not perfectly follow these rules.

Rules

  • You may assume that the C program is a valid, standalone program (all functions called are either defined in the input source code or exist in an #included header, and no input is taken from any source).
  • Any functions not defined in the input source code are assumed to not call any other functions (this is not the case in reality, but it allows for simplification of the call trees, namely by avoiding implementation-specific details)
  • All function calls in the call tree must include the arguments passed.
  • main is assumed to not have any arguments.
  • There will be no function pointers, gotos, setjmp/jonglmp calls, dynamic memory allocation/deallocation (so no malloc, calloc, realloc or free), or preprocessor macros in the input source code.
  • There will be no infinite loops or infinite recursion (all programs are guaranteed to terminate and thus have a finite call tree).
  • All arguments will be ints (to simplify matters, since the types don't really matter for this challenge). This means that the example program above would not be a valid input, because of the printf call.
  • All functions will either return an int or will be void (non-returning) functions.
\$\endgroup\$
  • \$\begingroup\$ What about recursion? Do we have to support the full complexity of the C grammar? \$\endgroup\$ – orlp Dec 1 '16 at 7:07
  • \$\begingroup\$ @orlp Clarified on recursion as well as loops. Are there any parts of the C grammar that would be problematic, in your opinion? \$\endgroup\$ – Mego Dec 1 '16 at 7:09
  • \$\begingroup\$ Mainly that the actual grammar is quite large. \$\endgroup\$ – orlp Dec 1 '16 at 7:21
  • \$\begingroup\$ @orlp For the most part, a lot of it can be ignored, because it won't have anything to do with function calls. Solutions will still be larger than typical code golf solutions, but that's fine - not every code golf challenge needs a 10-or-less-bytes solution. \$\endgroup\$ – Mego Dec 1 '16 at 7:24
  • \$\begingroup\$ It is implied that the text in the nodes should include a representation of the arguments, but what should that representation be when they aren't "nice" ones like integers or strings? Obvious nasty cases are structs, unions, and pointers. \$\endgroup\$ – Peter Taylor Dec 1 '16 at 8:27
  • \$\begingroup\$ @PeterTaylor Good point. I'll restrict it to ints. \$\endgroup\$ – Mego Dec 1 '16 at 8:29
  • \$\begingroup\$ Is it possible that the source will contain function declarations (as opposed to function definitions)? Those can look a lot like function calls (especially if they appear inside functions, which is legal in C). \$\endgroup\$ – user62131 Dec 1 '16 at 10:59
  • \$\begingroup\$ @ais523 Yes, they are allowed. They don't look that similar to function calls - function calls don't have a type signature prefixed (foo(); versus int foo();). \$\endgroup\$ – Mego Dec 1 '16 at 22:35
  • \$\begingroup\$ What about code of the form a * foo();? That's either a function call or a function declaration depending on whether a is a type or a variable. (You could probably get around this by banning pointers full stop, not just function pointers.) \$\endgroup\$ – user62131 Dec 1 '16 at 22:40
  • \$\begingroup\$ @ais523 I clarified that all functions will either return int or void, so that won't be an issue. Besides, you can't declare a variable that has the same name as a type, so that situation could be deterministically resolved without the restriction. \$\endgroup\$ – Mego Dec 1 '16 at 22:42
  • \$\begingroup\$ I like the idea of the challenge a lot, but I'm not convince that the "graphical output" part adds something... I think just printing it one call per line, and increasing the indentation level would be enough. \$\endgroup\$ – Dada Dec 3 '16 at 16:04
  • \$\begingroup\$ Also, what about if there is a function call like f(f(n)) ? Should we consider that a call to f(1) is done first, then a call to f(result of f(1))? (maybe adding a line about it would be nice) \$\endgroup\$ – Dada Dec 3 '16 at 16:06
  • \$\begingroup\$ @Dada Re: graphical-output: it's a lot harder to have an unambiguous, readable tree in text format versus graphical format. RE; nested calls, yes, nested calls are evaluated left-to-right, starting with the innermost nest and working outwards. For example, int main() { f(a(), b(c())); return 0;} would be main [ a, c, b, f ] (see what I mean about unambiguous and readble format for text?). \$\endgroup\$ – Mego Dec 5 '16 at 7:42
  • \$\begingroup\$ @Mego If you ask for a text format version based on indentation, I don't think there can be any ambiguity. But if you prefer graphical-output, why not (I just think that most of the code will be about formatting the graphical output, while I find the "genrate the call tree" part more interesting, but that's only my personal opinion, I like the challenge either way). \$\endgroup\$ – Dada Dec 12 '16 at 17:33
4
\$\begingroup\$

Regex Golf Generators

Challenge:

Cops:

The cops must post a 150 byte or less program in any language that outputs between 20 and 200 strings of printable ASCII (this excludes newlines), half of them "match" strings and half "don't match" strings. You can't output an odd number of strings -- there must be one don't match for each match.

The strings can be output as two lists of strings, or one list with a fixed delimiter between the "match" and "don't match" sections. The "match" and "don't match" lists can come in any order.

The following special characters are not allowed in the strings: ()[]*+?.\|^$.

Note that the program must be deterministic, and the language must be revealed.

Robbers:

The robbers must pick a cop answer and submit a regex in any flavor that matches the "match" strings but does not match the "don't match" strings.

The regex must be shorter than min(<length of all the match strings> + <number of match strings>-1 + 4, <length of all the don't match strings> + <number of don't match strings>-1 + 10), as this is the length of the regex that simply hardcodes it: ^(<match string 1>|<match string 2>|...)$ or ^(?!(<don't match string 1>|<don't match string 2>|...)$).*.

The shortest regex posted for that submission wins (note that there can and should be multiple competing cracks for one submission).

Scoring:

The robber's score is simply their number of wins (posted the shortest regex for a given submission) -- higher is better.

The cop's score is max(byte count of winning regex - byte count of submission - 4*(number of match strings - 10) for each submission) -- again, higher is better (you should be maximizing the length of the cracks and minimizing the length of your code). The byte count of the winning regex for an uncracked submission is the length of the hardcoded regex. Self cracks are permitted but must be marked as non-competing and will not count toward your cop or robber score.

The winning cop and robber will be announced 2 weeks after the posting of this challenge. Submissions will be allowed after that, but will not count towards your score.

\$\endgroup\$
  • \$\begingroup\$ Can they be a list of lists, i.e. [['string1',truthy],['string2',falsy]...]? With truthy/falsy being match/don't match. \$\endgroup\$ – Rɪᴋᴇʀ Feb 15 '17 at 17:41
  • 2
    \$\begingroup\$ I've said this in chat, but I'm listing it here for reference: 1. No need to have a fixed number of match strings. 2. No need to remove regex special characters. Everybody has the same benefit of using them. 3. No need to have a maximum regex length. It's like having a maximum bytes on a code-golf. 4. I don't see why you want to aggregate the cops' scores. Simply make it a standard maximum-score-wins. Otherwise, a person who posted the best scoring submission may lose to another who only posted a single decent submission. 5. Disallow self-cracks. It's too abusive for robbers. \$\endgroup\$ – Nathan Merrill Feb 16 '17 at 1:42
  • 2
    \$\begingroup\$ What's the point of allowing a "Retina flavor" of regex? Wouldn't that be identical to .NET? \$\endgroup\$ – feersum Feb 16 '17 at 8:23
4
\$\begingroup\$

Machines learning arithmetic

Note: Feel free to take and use this challenge, either the entire challenge as is, or just parts of it.

I've made a complete rewrite of this question. I figured the original version was more complex than it had to be. The task is essentially the same. The original challenge text had 4 upvotes and can be found in the edit history.


You will receive 30 lists of integers. Those lists are the result of a polynomial expression y = p(x) = a*x^4 + b*x^3 + c*x^2 + d*x + e, for x in the inclusive range [-1e5, 1e5]. Let's call those lists L1, L2 ....

I reserve the right to make changes to the lists by changing constants and the order if solutions seem to be custom made for those 30 lists.

Challenge:

Your task is to figure out what the constants a, b, c, d, e are for each of those 30 lists.

You will write a code that pulls numbers from each list (one list at a time). It must ask for the y-values for individual x-values, as many as you want, but one at a time. When you think you have enough information, you'll attempt to guess the value of the constants.

You'll do this for all 30 lists.

Scoring:

The lowest score wins!

  • You get 1 point for every number you pull from the list
  • You get 10 points for every attempt to crack the code (guess a, b, c, d, e)
  • The scores for all lists will be added up.

If no submission cracks all lists successfully then the one that cracked the most will win. Tie breaker #1 will be fewest points, tie breaker #2 will be time of submission.

Rules and clarifications:

You can assume all constants to be integers

The lists will be formatted in this way (suppose the expression for L1 is: 2*x). I'm using MATLAB/Octave syntax for a cell array. You can change this to fit your needs (language).

L1 = {[-200000, -199998, -199996, ... -4, -2, 0, 2, 4, ... 199996, 199998, 200000], [0 0 0 2 0]};

You can change the format to fit your needs, but you must not mix the list and the values for a, b, c, d, e.

Example:

You ask for y for four different input values, and get the results:

L1(0) = 0
L1(1) = 0
L1(2) = 2
L1(3) = 12

Your function guesses (for some reason) that this is x^3-2x^2+1, and attempts to crack it:

L1([0, 1, -2, 0, 1]
false

You have tried 4 values, and attempted to crack it once. This gives you 4 + 10 = 14 points.

You try a few more values:

L1(-9) = 6480
L1(-7) = 2352
L1(7)  = 2352
L1(9)  = 6480
L1(100)= 99990000

You're now confident that this has to be: x^4-x^2, and attempt to crack it again:

f([1 0 -1 0 0])
true

You have successfully guessed the constants a, b, c, d, e, and get a score of `14 + (5 + 10) = 29 points.

You have 29 functions left.


  • I'll have to post the lists on some suitable place (where)?
  • Can I ban builtin interpolation functions somehow without risking the "unobservable requirements", "x without y" pitfalls?
  • Anything else?
\$\endgroup\$
  • \$\begingroup\$ This isn't yet 100% clear to me, but I've upvoted because it looks like an interesting idea that will make a great challenge once fine tuned. \$\endgroup\$ – trichoplax Jan 18 '17 at 10:58
  • \$\begingroup\$ :) Anything in particular that isn't clear, or everything in general? \$\endgroup\$ – Stewie Griffin Jan 18 '17 at 11:00
  • \$\begingroup\$ I've edited... It was never intentional to have the number of bytes mixed in here... I'm probably just so used to writing it that I didn't even notice it :P \$\endgroup\$ – Stewie Griffin Jan 18 '17 at 11:03
  • \$\begingroup\$ Will it be done like: 1. "start writing your function" 2. "end of function writing period" 3. "release black box function for scoring submissions"? To avoid learning the expressions and tuning the functions to fit. \$\endgroup\$ – Emigna Jan 18 '17 at 11:04
  • \$\begingroup\$ I guess you could have a controller that generates new random test cases each time to allow the competition to be open ended, but rescoring the old entries might reorder them in some cases. Might need to average over a number of different sets of test cases. \$\endgroup\$ – trichoplax Jan 18 '17 at 11:07
  • \$\begingroup\$ The given example of h(x) = ((3*x*x*x)/(x+1))+1 is incompatible with "You can assume the functions will give integer results back". But basically it's a case of guessing and verifying a rational function of some bounded degree? \$\endgroup\$ – Peter Taylor Jan 18 '17 at 11:09
  • \$\begingroup\$ If you want a variety of languages to be able to compete without having to implement arbitrary size integer arithmetic, you could use modular arithmetic. For example, everything is mod 256, or 65536. \$\endgroup\$ – trichoplax Jan 18 '17 at 11:10
  • \$\begingroup\$ @Emigna, good question :) One solution could be: Provide x number of functions on a certain format. After the submission is posted it will be tested against the "real" cases that are of similar difficulty, but different. I think I can have some fairly easy, and some quite hard. But it's a really good question, so I'm not sure... I'm open for ideas :) \$\endgroup\$ – Stewie Griffin Jan 18 '17 at 11:11
  • \$\begingroup\$ @PeterTaylor, I made a blooper when making the examples. Using rational functions with input arguments and 8/10(?) significant figures in the output is probably a good idea. I think 10 is low enough that rounding shouldn't be an issue as long as you have the correct function..? And it can be restricted to 3/4/5..9th degree polynomials. \$\endgroup\$ – Stewie Griffin Jan 18 '17 at 11:15
  • \$\begingroup\$ Peter's comment also makes me wonder what happens for division by zero. Will this be avoided somehow or will we be informed that a particular input causes an error? Will the error be specifically "division by zero" or just "error"? \$\endgroup\$ – trichoplax Jan 18 '17 at 11:16
  • \$\begingroup\$ First comment @trichoplax: You have a point, but it will also make it harder, since it will no longer be a continuous function. Second comment: I think an error message / warning of some sort would suffice. Handling that error should be very simple, since this isn't code golf. It will probably be 1-3 lines of code. Giving inf for divison by zero, and error for 0/0 could also be a solution (that's the default solution in MATLAB). \$\endgroup\$ – Stewie Griffin Jan 18 '17 at 11:21
  • \$\begingroup\$ Note that if you want continuous functions you would need to avoid rational functions, but it sounds like you're happy with piecewise continuous if you don't mind "inf" and "error" in some places? \$\endgroup\$ – trichoplax Jan 18 '17 at 11:34
  • \$\begingroup\$ @trichoplax, What do you think? Is modular arithmetic a good idea? Should I skip division (impossible to avoid division by zero if not)? \$\endgroup\$ – Stewie Griffin Jan 18 '17 at 11:51
  • \$\begingroup\$ I really don't know. I'm just suggesting possibilities. Someone more mathematical would probably be useful for assessing whether modular and rational functions would be interesting to crack. Are you aiming for a situation where most people can write code that cracks all 10, but getting a low score is challenging, or where most people can only crack a proportion of the 10? \$\endgroup\$ – trichoplax Jan 18 '17 at 11:59
  • 1
    \$\begingroup\$ Parentheses should be removed since it makes this challenge much more difficult... and it is already really difficult without them \$\endgroup\$ – Anthony Pham Jan 19 '17 at 0:44
4
\$\begingroup\$

Exiting Vim — Cops & Robbers

In honour of the recent milestone, let's turn escaping Vim into a game!

Rules for Cops

Starting from launching vim with no arguments (i.e. no initial file open), provide a sequence of keys to be typed in to the editor.

Rules for Robbers

Starting from the state described by the cop, provide a sequence of keys to exit Vim.

Scoring

Cops are scored by the difference between key counts <robber_key_count> - <cop_key_count>, and robbers are scored by the ratio of key counts <cop_key_count> / <robber_key_count>. Higher scores are better.

Keys are counted as one per key-down event (e.g. a sequence of Ctrl+X, Ctrl+Y, Ctrl+Z only need count the Ctrl once, unless it must be released during the sequence). Note that this is not the same as the golf-rules scoring for Vim.

Plugins are not permitted.

Example 1

Cop (1 key): i

Robber (4 keys): Esc : q Enter

Score for cop = 4 - 1 = 3, score for robber = 1 / 4 = 0.25

Example 2

Cop (2 keys): i i

Robber (5 keys): Esc : q ! Enter

Score for cop = 5 - 2 = 3, score for robber = 2 / 5 = 0.4

Example 3

Cop (3 keys): i Ctrl+V

Robber (6 keys): Return Esc : q ! Enter

Score for cop = 6 - 3 = 3, score for robber = 3 / 6 = 0.5

\$\endgroup\$
  • 1
    \$\begingroup\$ I'm not sure that the scoring here rewards cops enough for ingenuity (all the examples score 3 after all!), so ideas on that would be great. Also I'm considering banning Esc & Ctrl+[ to make this more interesting, but I suspect even with Esc permitted there are ways to get seriously tied-up. \$\endgroup\$ – Dave May 23 '17 at 20:13
  • \$\begingroup\$ I'm worried that there may not be much scope for the cops to improve; it'd be something of a design flaw in the challenge if there's a hard limit to how well a cop can do. Also, what about key sequences that depend on the environment within which vim is running? (For example, Ctrl-Z will suspend vim and require the use of the shell to either exit or restart it, but how you do that depends on which shell is running; or on Linux, Ctrl-Alt-F1 will probably switch to a different virtual terminal altogether, and what assumptions can you make about its state?) \$\endgroup\$ – user62131 May 31 '17 at 21:35
  • \$\begingroup\$ Another potential problem: exit sequences which have side effects. In particular, I'm thinking about Alt-SysRq-K, which is guaranteed to exit vim, in addition to everything else, on Linux systems which have it enabled. That compares favourably to basically all the exit strings you have right now, and there's no way, short of reconfiguring the OS, to block it. \$\endgroup\$ – user62131 May 31 '17 at 21:36
  • \$\begingroup\$ @ais523 I'm thinking it could easily be restricted to "vim-only" commands, so anything which is intercepted by the shell can be forbidden. But I agree that it feels like there's a hard-limit on the cop (though I don't know vim nearly well enough to be sure, and I've seen some hints around the internet that it's possible to get exceedingly stuck, but perhaps only because some modes need obscure non-esc keys, rather than needing more keys). Any ideas for better scoring? \$\endgroup\$ – Dave Jun 5 '17 at 20:36
4
\$\begingroup\$

Me, Me, Me!

Edit: changed success when the input matches the source code to when the input is any permutation of the source.

Your code is clearly superior to all other code. In fact, your code is so great that it prints itself when the opportunity arises (but not when any other, inferior code is around.)

Task

Write a program or function that takes a string as input. If the string is equal to some permutation of the characters in your source code, then output the entire source code. Otherwise, output Gross.

If your language uses a non-ascii encoding, "character" is defined as whatever a character in your source looks like. If it's unreasonable to take input in that format, you can treat the bytes of your source as their respective extended ascii codes.

Input

Takes a string using whatever input mechanism your programming language provides.

Output

Prints either the entire source of your program or the word Gross. No additional output is permitted.

Rules

  • You can take input using any reasonable method. (Stdin, function parameter, etc.)
  • A string a is a permutation of a string b iff each character in the alphabet appears the same number of times in a and b.
  • This is Shortest code (in bytes) wins.
\$\endgroup\$
  • \$\begingroup\$ quine? -- \$\endgroup\$ – MD XF Jun 7 '17 at 21:32
  • \$\begingroup\$ @MDXF it will have the quine tag, of course – but it's not strictly a quine unless it gets the right input! I just didn't see how to add tags in the answer... \$\endgroup\$ – vroomfondel Jun 7 '17 at 21:34
  • 1
    \$\begingroup\$ Use [tag:quine] in the header. And yes, we accept the quine tag for quine variants :-) \$\endgroup\$ – MD XF Jun 7 '17 at 21:34
  • 2
    \$\begingroup\$ trivial extension of this challenge \$\endgroup\$ – Destructible Lemon Jun 7 '17 at 23:14
  • \$\begingroup\$ aw shucks. I figured something like this existed already, just didn't know what to search for. \$\endgroup\$ – vroomfondel Jun 8 '17 at 14:36
  • \$\begingroup\$ actually, @DestructibleLemon I could be missing something obvious but I don't think the extension is trivial. Printing its own source code is, I would say, significantly harder than printing "true" as long as I add the usual restriction that it can't read its own source. \$\endgroup\$ – vroomfondel Jun 8 '17 at 14:38
  • \$\begingroup\$ @rogaos If the test on the input passes, printing its source code is as simple as printing the input string. \$\endgroup\$ – NonlinearFruit Jun 8 '17 at 15:33
  • \$\begingroup\$ @NonlinearFruit true of course, but adding the print statement may make the quine harder to construct in the first place. (Except in languages like javascript, which are basically reading their own source anyway.) Maybe the challenge would be improved by transforming the input string in some way, or crashing on "correct" input? \$\endgroup\$ – vroomfondel Jun 8 '17 at 15:38
  • \$\begingroup\$ @rogaos it is the difference between printing true and printing the input \$\endgroup\$ – Destructible Lemon Jun 8 '17 at 23:29
  • \$\begingroup\$ modified to use permutations of the input rather than the input itself \$\endgroup\$ – vroomfondel Jun 19 '17 at 18:21
4
\$\begingroup\$

The Chroma Key to Success

\$\endgroup\$
  • \$\begingroup\$ So essentially, for every pixel in the second image, if it's #00FF00, replace it with the corresponding pixel in the first image; otherwise, don't modify that pixel? \$\endgroup\$ – HyperNeutrino Jul 16 '17 at 17:33
  • \$\begingroup\$ @HyperNeutrino Yes. \$\endgroup\$ – ckjbgames Jul 16 '17 at 17:34
  • \$\begingroup\$ I don't know image formats very well, but are we guaranteed that the image will be in 3-byte-RGB format? As in, is there transparency? \$\endgroup\$ – HyperNeutrino Jul 16 '17 at 17:36
  • \$\begingroup\$ @HyperNeutrino Assume the image is full opacity. \$\endgroup\$ – ckjbgames Jul 16 '17 at 17:39
  • 3
    \$\begingroup\$ Please delete this, now that it is posted. \$\endgroup\$ – programmer5000 Jul 17 '17 at 13:05
4
\$\begingroup\$

How high can you count in English?

Challenge

In 500 bytes (or fewer) write a program that outputs a list of the English word forms of as many consecutive integers greater than zero as you can.

For example, score 6:

one two three four five six

Example submission (hopefully you can do better than this):


Python 3, score 43 (488 bytes)

print(["one","two","three","four","five","six","seven","eight","nine","ten","eleven","twelve","thirteen","fourteen","fifteen", "sixteen","seventeen","eighteen","nineteen","twenty","twenty-one","twenty-two","twenty-three","twenty-four","twenty-five","twenty-six","twenty-seven","twenty-eight","twenty-nine","thirty","thirty-one","thirty-two","thirty-three","thirty-four","thirty-five","thirty-six","thirty-seven","thirty-eight","thirty-nine","forty","forty-one","forty-two","forty-three"])

Try it online!


Scoring and rules

For each language, the person whose code counts the highest wins. In case of a tie, the person who submitted first wins.

  • No modules, libraries, builtins that convert from numeric to word form are allowed.
  • You must output all integers from 1 (one) to n (your score) without missing any. If you want to output 0 (zero) as well, that's fine.
  • You are allowed up to 500 bytes of code. Your code may be a full program or function.
  • Number format: for consistency, all numbers must match the output of this site.
  • Standard loopholes apply (of course)
  • Standard output rules apply
\$\endgroup\$
  • 2
    \$\begingroup\$ Come on, you could at least make your example better by just using a single space-separated string ;) but nice challenge! :) \$\endgroup\$ – HyperNeutrino Jul 18 '17 at 18:00
  • 1
    \$\begingroup\$ Alternate title: How high can you count in English? \$\endgroup\$ – Stephen Jul 18 '17 at 18:06
  • \$\begingroup\$ You may, however, omit "and" if you'd like. do we have to omit and or not? Personally, I'd say you wouldn't as it 'sounds more correct'. \$\endgroup\$ – Okx Jul 18 '17 at 18:11
  • \$\begingroup\$ @StepHen changed, thanks. \$\endgroup\$ – wrymug Jul 18 '17 at 18:15
  • \$\begingroup\$ Your edit doesn't answer my question. Do we have to omit and or not? \$\endgroup\$ – Okx Jul 18 '17 at 18:15
  • \$\begingroup\$ @Okx I take your point. Removed. \$\endgroup\$ – wrymug Jul 18 '17 at 18:28
  • 1
    \$\begingroup\$ I'm not sure this adds to existing number-to-english challenges like this or this. Past getting the same basic pattern of digits down, the question seems to be how many prefixes for powers of 1000 one can compress into the remaining bytes. \$\endgroup\$ – xnor Jul 18 '17 at 18:33
  • 1
    \$\begingroup\$ Off the jokes, what if I can count to infinity? \$\endgroup\$ – V. Courtois Jul 20 '17 at 13:40
  • \$\begingroup\$ @courtois I don't see how that would be possible, but I guess you'd win \$\endgroup\$ – wrymug Jul 20 '17 at 13:42
  • \$\begingroup\$ @rosslh yeah you're right, I just saw the sentence Number format: for consistency, all numbers must match the output of [this](https://lingojam.com/NumbersToWords) site. And for my method, it would have been with million of billion of billion of ... though the site stops at one hundred novenonagintanongentillion, something like 3002 zeros. \$\endgroup\$ – V. Courtois Jul 20 '17 at 13:43
4
\$\begingroup\$

ASCII addition

Objective

Given two strings, your job is to:

  1. Convert each character to their respective ASCII decimal value
  2. Concatenate the numbers into one large number
  3. Add these values together
  4. Get the ASCII characters represented of each pair of numbers starting from the right (or if there are not enough numbers, take a number alone)
  5. Leave unprintables (ie not in the range 32 - 126), and output the rest

An example for HELLO and WORLD

"HELLO"    + "WORLD"
H E L L O  + W O R L D
7269767679 + 8779827668
1 60 49 59 53 47    (separated to show ASCII conversion easily)
   <  1  ;  5  /    convert to ASCII by converting pairs to their respective characters (note: you start from the last pair)
<1;5/               output (note there is no 0x01) 

Notes

  • Each string will be a maximum of 6 characters long
  • Input will always contain readable ASCII characters
  • You have to take pairs of numbers from the end of the sum and convert each one of them to ASCII
  • You must not print unreadable characters if their values appear and instead skip them

Examples

ABC + XYZ  //input
656667 + 888990
1 54 56 57
   6  8  9       //again 0x01 is left out
689      //output

Rules

  • Your submission can be either a program or a function

This is so the program with the shortest bytecount wins!

Sandbox Questions

  • Are the specs clear enough?
  • Will this question give me hats?
  • Any better title suggestions?
\$\endgroup\$
  • \$\begingroup\$ What range of ASCII characters do we need to be able to handle in the input? Only printable characters or any? \$\endgroup\$ – Robert Hickman Dec 20 '16 at 20:07
  • 1
    \$\begingroup\$ I swear we've had this challenge, but I can't seem to find it ... \$\endgroup\$ – AdmBorkBork Dec 20 '16 at 20:21
  • \$\begingroup\$ Edited that into the specs \$\endgroup\$ – Cows quack Dec 20 '16 at 20:22
  • \$\begingroup\$ @TimmyD How's this now? \$\endgroup\$ – Cows quack Dec 21 '16 at 7:28
  • \$\begingroup\$ what if a character is unprintable? do we still need to output it then? \$\endgroup\$ – Destructible Lemon Dec 21 '16 at 7:46
  • \$\begingroup\$ @DestructibleWatermelon Yes \$\endgroup\$ – Cows quack Dec 21 '16 at 7:56
  • \$\begingroup\$ Better wording. Given that a bunch of control codes are possible, some test cases that demonstrate expected behavior when (e.g.) 11 or 13 occur in the output would be of good value. \$\endgroup\$ – AdmBorkBork Dec 21 '16 at 13:49
  • \$\begingroup\$ @TimmyD Do you think it would be a good idea if I restrict the output to displaying only characters if their values are between 32 and 126 because outputting other values might be difficult in some languages? \$\endgroup\$ – Cows quack Dec 21 '16 at 13:54
  • \$\begingroup\$ That may be a better way to go, but you'll need to be very careful with the wording. For example, suppose that the output number is ...226... and the 26 is slated to be the pair of digits that get converted to ASCII. Obviously, that's outside the printable range, so let's look at the next digit, but now 226 is also outside. Does that mean just the 6 is skipped? The 26 is skipped? The 226 is skipped? \$\endgroup\$ – AdmBorkBork Dec 21 '16 at 13:58
  • \$\begingroup\$ @Cowsquack You don't say precisely (but we see it in the test case) how many digits we need to parse at a time, before outputting. \$\endgroup\$ – V. Courtois Jul 18 '17 at 14:06
  • \$\begingroup\$ @V.Courtois Is this clearer now? \$\endgroup\$ – Cows quack Jul 19 '17 at 12:48
  • \$\begingroup\$ @Cowsquack This is! In fact you could see, in the comments some were wondering too if we had to print things like 125 -> }. \$\endgroup\$ – V. Courtois Jul 19 '17 at 12:55
4
\$\begingroup\$

Let's play Othello (Reversi)!

Open for takeover

I don't have the time to devote to this right new, and not for the foreseeable future. Anyone who wants this idea, the post, and any code I have in the repo should comment below.

Side note on the code, I have a gorilla repl file in the repo that I can use to run test games on, and get screenshots of during any point of the game. If you want I can make up screenshots for the rules section since I have everything setup on my end for that.


This would be a king of the hill about reversi. Yep. I'm going to write up the post and controller later The controller is being written here: https://github.com/JJ-Atkinson/reversi-koth-ppcg , but I'm putting this here so show the idea is taken ;)


Post start

Rules

(you can probbably skip this if you've played Reversi before)

enter image description here

(images from http://www.coolmath-games.com/0-reversi)

Reversi is a two player game with a simple goal - own the most pieces on the board.

Wikipedia

\$\endgroup\$
  • \$\begingroup\$ You will need a complete set of rules, and some high-level description of the controller (as well as a detailed spec when it's written), and you'll need to work out some victory criteria. \$\endgroup\$ – VisualMelon Jun 29 '17 at 6:50
  • \$\begingroup\$ Yep, all that is in the works. I'll add a questions section when it is ready for review. \$\endgroup\$ – J Atkin Jun 29 '17 at 18:46
  • \$\begingroup\$ As for a longer title, you could simply do "Let's play Reversi" \$\endgroup\$ – Shelvacu Jul 3 '17 at 22:46
  • 1
    \$\begingroup\$ This is not Reversi. This is Othello. Source. In Reversi as it was originally played, the starting configuration was not predetermined, like it is in Othello. Players would take turns setting down the first four pieces in the center of the board \$\endgroup\$ – Okx Jul 4 '17 at 11:23
  • \$\begingroup\$ Thanks for the heads up! I'll keep reversi in the title, since I've always seen this game called reversi. \$\endgroup\$ – J Atkin Jul 4 '17 at 15:54
  • \$\begingroup\$ @JAtkin But it is not called Reversi. I quote: Unfortunately, because the games look similar and have similar rules, and “Othello” is a trademark and “Reversi” is not, many board game sellers, websites, software makers, etc., wanted to piggy back on the popularity of Othello by calling their game “Reversi”. Quite aggravatingly, they never use the rules of real Reversi (as far as we've ever seen). I insist that you remove all instances of Reversi from your post. \$\endgroup\$ – Okx Jul 5 '17 at 17:22
  • \$\begingroup\$ I understand fully that Reversi is not the correct name of this game. However, many people (myself included) have not heard of Othello, and only know about Reversi, even if our understanding was incorrect. I plan to keep both names. I think I'll include the article you reference, but I won't remove Reversi. This is not because I dislike being correct, it is because I believe that it brings the tangible benefit of wider recognition and perhaps higher viewership of the post. I will have a strongly defined rules section so any concern about confusion about rules can be dismissed. \$\endgroup\$ – J Atkin Jul 7 '17 at 1:11
4
\$\begingroup\$

Prime encode integers!

In this challenge, you must convert inputted natural numbers into a prime encoding.

The sequence of the primes, and 1, is a complete sequence (We're going to consider 1 an honourary prime for this challenge). What this means is that it's possible to express any positive integer as a sum of the terms of the sequence (without reusing terms). For example, the powers of two are a complete sequence, and you can encode numbers in them (this is binary).

As with binary, you use a sequence of 1s and 0s to represent which terms are used. 1011 will represent 5 + 1 + 2, or 8. 8 could also be represented as 10001, or 7+1. the place values represent primes:

... 13 11 7 5 3 2 1

continuing with all of the primes to the left

In this challenge, you must output a string of 1s and 0s, such that the place value primes sum to inputted strictly positive integer

Test cases

8 -> 10001 or 1011
2 -> 10
11 -> 1111 or 10101 or 100000 (I might have missed one of the possibilities?)
13 -> 1000000 or any other possibility

you may use any valid representation of the in

input note:

input is 1 strictly positive integer

you do not need to consider the value 0, even though it is possible to represent in this system, by just outputting zero

\$\endgroup\$
  • \$\begingroup\$ I'm assuming input is n>0? IO in all normal means? Is this code-golf? I'm also assuming we can return any valid combination? \$\endgroup\$ – TheLethalCoder Aug 4 '17 at 10:48
  • \$\begingroup\$ didn't it specifically say n>0? and also specifically say you can return any valid representation? \$\endgroup\$ – Destructible Lemon Aug 4 '17 at 22:49
  • \$\begingroup\$ It does specifically say "strictly positive", but a long way after it says "inputted integers". It's best to state restrictions like that as early as possible to avoid misleading or confusing readers. \$\endgroup\$ – Peter Taylor Aug 6 '17 at 19:00
4
\$\begingroup\$

Find the longest Factor-Multiple sequence

Inspired by this riddle.

A Factor-Multiple sequence is any sequence where A[n+1] is either a multiple or factor of A[n].

Task

Create a full program or function that, given a list (or any other accepted input) of positive integers, returns (one of the) the longest possible Factor-Multiple sequence containing those numbers. Each number can only be used once and each number in the input will be unique.

Input

As mentioned above, input is a list of integers. If your language only supports strings, or if you like doing so, you may take input as strings instead.

Output

You can output your sequence in any way you like as defined on meta.

Rules

Test cases

More need to be added.

Input                                                Output                 
1 2 3 5 7 11                                         2 1 3 or 3 1 2 or 11 1 7 etc.
1 2 3 4 5 6 7 8 9 10                                 5 10 1 4 8 2 6 3 9  

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20   11  1  7 14  2  8 16  4 12  6 18  9  3 15  5 10 20 

Meta:

  • Need to add more test-cases

  • Can't think of any relevant rules, did I miss any?

\$\endgroup\$
  • \$\begingroup\$ Related (same problem, different graph). \$\endgroup\$ – Peter Taylor Aug 15 '17 at 22:28
  • \$\begingroup\$ @PeterTaylor Thanks for the link. From what I can see, that challenge has a one-directional graph, while in this challenge if a is connected to b => b connects to a. I am not sure if that changes the algorithms involved, but it would be interesting to see them golfed. \$\endgroup\$ – JAD Aug 16 '17 at 7:20
  • \$\begingroup\$ Actually the biggest difference is that the other one asks for approximate answers and this one asks for exact answers. \$\endgroup\$ – Peter Taylor Aug 16 '17 at 7:25
4
\$\begingroup\$

Case Matching Find Replace

Take three inputs, a string of text, T; a string of characters to replace, F; and a string of characters to replace them with, R. For each substring of T with the same (case insensitive) characters as F, replace them with the characters in R. However, keep the same case as the original text.

If there are more characters in R than F, the extra characters should be the same case as they are in R. If there are numbers or symbols in F, then the corresponding characters in R should keep the case they have in R. F will not necessarily appear in T.

You can assume all text will be in the printable ASCII range.

Examples

"Text input", "text", "test" -> "Test input"

"tHiS Is a PiEcE oF tExT", "is", "abcde" -> "tHaBcde Abcde a PiEcE oF tExT"

"The birch canoe slid on the smooth planks", "o", " OH MY " -> "The birch can OH MY e slid  OH MY n the sm OH MY  OH MY th planks"

"The score was 10 to 5", "10", "tEn" -> "The score was tEn to 5"

"I wrote my code in Brain$#@!", "$#@!", "Friend" -> "I wrote my code in BrainFriend"

"This challenge was created by Andrew Piliser", "Andrew Piliser", "Martin Ender" -> "This challenge was created by Martin Ender"

// Has a match, but does not match case 
"John does not know", "John Doe", "Jane Doe" -> "Jane does not know"

// No match
"Glue the sheet to the dark blue background", "Glue the sheet to the dark-blue background", "foo" -> "Glue the sheet to the dark blue background"

// Only take full matches
"aaa", "aa", "b" -> "ba"

// Apply matching once across the string as a whole, do not iterate on replaced text
"aaaa", "aa", "a" -> "aa"
\$\endgroup\$
  • \$\begingroup\$ Example(s) where the replacement string narrowly does not appear in the text might help. \$\endgroup\$ – isaacg Aug 17 '17 at 19:55
  • \$\begingroup\$ @isaacg Added one, let me know if it's not what you were thinking \$\endgroup\$ – Andrew Piliser Aug 17 '17 at 21:11
  • \$\begingroup\$ What is the expected output for "aaa","aa","b" and "aaaa","aa","a"? \$\endgroup\$ – fireflame241 Aug 17 '17 at 21:33
  • \$\begingroup\$ Will we guaranteed that F will appear at least once in T? \$\endgroup\$ – Shaggy Aug 17 '17 at 21:58
  • \$\begingroup\$ @Shaggy F will not necessarily appear in T. \$\endgroup\$ – Andrew Piliser Aug 17 '17 at 22:04
  • \$\begingroup\$ @fireflame241 Added your two examples, good catch. \$\endgroup\$ – Andrew Piliser Aug 17 '17 at 22:07
  • \$\begingroup\$ I would personally appreciate some kind of note on test case 3. It took me quite a while to realize that John Doe actually appears in full in the input string, rather than requiring we be able to replace all instances of John with Jane in that situation. \$\endgroup\$ – Kamil Drakari Aug 18 '17 at 17:45
  • 1
    \$\begingroup\$ @KamilDrakari Added explanation for that case and a few others. Thanks for the feedback! \$\endgroup\$ – Andrew Piliser Aug 18 '17 at 19:03
4
\$\begingroup\$

I'm symmetric, not palindromic!

Background

Inspired by I'm a palindrome. Are you?, where it is presented the shocking fact that “()() is not a palindrome, but ())(”, I asked myself what instead is ()() and the answer is simply: it is a string with a vertical symmetry axis!

The task

Write a program or function that takes a string S (or the appropriate equivalent in your language) as input, checks for symmetry along the vertical axis, and returns a truthy or falsy value accordingly. You can use any reasonable means to take the input and provide the output.

Reflectional symmetry

Reflectional symmetry around a vertical axis (or left-right symmetry) means that if you put a mirror vertically at the exact center of the string, the reflected image of the first half of the string is identical to the second half of the string.

For example, the following strings are reflectional symmetric around a vertical axis:

()()
()()()
[A + A]
WOW ! WOW
OH-AH_wx'xw_HA-HO
(<<[[[T*T]]]>>)
(:)
)-(
())(()
qpqp

while the following are not:

())(
((B))
11
+-*+-
WOW ! wow
(;)
qppq

Rules of the contest

• Your program or function will receive only printable ASCII characters. You can include or not the empty string, (which is symmetric, of course!) as legal input, which is better for you.

• The ASCII characters that can be considered symmetric with respect to the vertical axes are the following (note the initial space, and the difference between uppercase and lowercase letters):

 !"'+*-.:=AHIMOTUVWXY^_ovwx|

The ASCII characters that can be considered “mirrored” and their corresponding characters are:

()<>[]{}qpbd/\

Note that, since they are mirrored, you can have both () as well as )(, /\ and \/, etc.

All the other ASCII printable characters must be considered asymmetric and without a mirrored corresponding character.

• This is a challenge: the shorter your program is, measured in bytes, the better, in any programming language.

• Kudos to people that will produce a symmetric program!

\$\endgroup\$
  • \$\begingroup\$ You seem to be missing two pairs of mirror-able characters: qpdb. Also, I'm not sure about the mixed-win criteria: "this is code-golf ...but I will mark as accepted the shortest symmetric program, if there will be at least one!", I'd go for "imaginary brownies" or just "kudos" (let the upvotes or bounties reward). \$\endgroup\$ – Jonathan Allan Sep 6 '17 at 9:54
  • \$\begingroup\$ Thanks a lot, @JonathanAllan, I will correct the text about mirrored characters, and the criteria for winning. \$\endgroup\$ – Renzo Sep 6 '17 at 9:57
  • 2
    \$\begingroup\$ This question is very confusing, because the string it gives as an example of vertical symmetry is actually vertically symmetric, but the definition it gives of vertical symmetry is actually the definition of horizontal symmetry. \$\endgroup\$ – Peter Taylor Sep 6 '17 at 11:10
  • \$\begingroup\$ @PeterTaylor, my definition is in accord with wikipedia: “If the letter T is reflected along a vertical axis, it appears the same. This is sometimes called vertical symmetry.” I said that one should put “a mirror vertically”. If you think it is ambiguous, however, I will change “vertically symmetric” with “has a vertical symmetry axis” or “has a left-right symmetry”. Or I could add a picture. \$\endgroup\$ – Renzo Sep 6 '17 at 11:51
  • \$\begingroup\$ The very next sentence in the Wikipedia article you quote says that this is an ambiguous phrasing and best avoided. I must say that I didn't know it was ambiguous: this is the first time I've seen anyone say that an object with a vertical axis of symmetry has vertical symmetry, and I have understood since I was a small child that an object with a vertical axis of symmetry has horizontal symmetry (and so, presumably, has the person who upvoted my comment). Since questions on PPCG should be unambiguous, I can only advise a rewrite which explicitly uses the word "axis" everywhere. \$\endgroup\$ – Peter Taylor Sep 6 '17 at 12:00
  • \$\begingroup\$ @PeterTaylor, ok, thank you very much for your comment, I will change the question. Do you think I should change also the title? \$\endgroup\$ – Renzo Sep 6 '17 at 12:14
  • \$\begingroup\$ Yes, but in the title it would suffice to say "symmetric". Which symmetry is a detail which can be left for the body. \$\endgroup\$ – Peter Taylor Sep 6 '17 at 12:36
  • \$\begingroup\$ @geokavel, thanks, I corrected it. \$\endgroup\$ – Renzo Sep 6 '17 at 15:06
4
\$\begingroup\$

Zoom box drawing characters

Here are some sample box drawing characters:

  ╷
 ┌┴┐
╶┤ ├╴
 └┬┘
  ╵

How do we zoom them? Well, we need to triple their size. The result looks like this:

      ╻
      ┃
      ┃
   ┏━━┻━━┓
   ┃     ┃
   ┃     ┃
╺━━┫     ┣━━╸
   ┃     ┃
   ┃     ┃
   ┗━━┳━━┛
      ┃
      ┃
      ╹

As you can see, what happens is this:

  • Each box drawing character is replaced by its heavy version (for extra thickness)
  • The box drawing characters are extended using the heavy horizontal and heavy vertical characters, resulting in a separation of three between the original characters

You can use any reasonable character I/O format. You will only need to support spaces and the 15 basic box drawing characters, plus newlines if you need them as line separators. You can only require rectangular input, but your output may contain arbitrary whitespace padding, except on the left, so that the characters in the zoomed image are aligned.

This is , so the shortest solution in bytes that violates no standard loopholes wins, but if you're using UTF-8 encoding then you can score all box drawing characters as 1 each.

\$\endgroup\$
  • 3
    \$\begingroup\$ RIP Charcoal, it doesn't use UTF-8 :P \$\endgroup\$ – ASCII-only Oct 6 '17 at 11:58
4
\$\begingroup\$

Does it have a square? (simple version)

Given a matrix of 0s and 1s, determine if there are 4 points that are 1 and are the corners of a square.

Here's an example to clarify, with a possible square (in bold):

0 0 0 0 0 0 0 1
0 0 0 1 0 1 0 0
0 0 0 0 1 1 0 0
0 0 0 1 0 1 0 0
1 0 0 0 0 0 0 1
0 1 1 0 0 1 1 1
1 1 1 1 1 0 0 1
0 1 0 0 1 0 1 1
1 1 1 1 0 0 1 0
1 0 0 1 0 1 0 1
0 0 1 0 1 0 1 1
1 0 0 1 1 0 1 1
Another possible square is the following:

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

There are many squares in this matrix, but the point isn't to count the squares, just to determine if there's a square in it. Since there is a square in it, your solution, given this matrix, must return a truthy value.

Given this matrix, your solution must return a falsy value:

0 0 0 0 0 0
0 1 1 0 0 1
0 1 0 0 1 1
0 1 1 0 1 0
You can see there's no square in there.

Rules

  • Since the input is a matrix, it will always be rectangular.
  • Probably needless to say, the sides of a square must be equal.
  • The corners of a square must all be 1.
  • A square must have at least side length 2 to be considered a square, otherwise this challenge would be extremely trivial.
  • Standard Loopholes, as usual, are forbidden.

Test cases

This section is under construction.

\$\endgroup\$
  • \$\begingroup\$ Related. \$\endgroup\$ – Jonathan Frech Oct 27 '17 at 22:52
  • \$\begingroup\$ Is a 2x2 square a square? \$\endgroup\$ – Magic Octopus Urn Oct 27 '17 at 23:22
  • \$\begingroup\$ @MagicOctopusUrn A square must have at least side length 2 to be considered a square \$\endgroup\$ – Erik the Outgolfer Oct 28 '17 at 9:34
  • \$\begingroup\$ Can one's solution require that the matrix' dimensions are given? If so, can the input be a single list instead of a nested one? \$\endgroup\$ – Jonathan Frech Oct 28 '17 at 20:42
  • \$\begingroup\$ @Jonathan Relevant but not necessarily answering your question. \$\endgroup\$ – ბიმო Oct 28 '17 at 22:06
  • \$\begingroup\$ @JonathanFrech Does your language really not support nested arrays (like e.g. Neim)? Otherwise I don't see why... \$\endgroup\$ – Erik the Outgolfer Oct 28 '17 at 22:08
  • \$\begingroup\$ @EriktheOutgolfer I was thinking of languages like C, where I find it simply nicer to only have to deal with one list, even though the language can handle nested lists. I just wanted to ask about, not necessarily influence, the validity of a solution taking a flat list. \$\endgroup\$ – Jonathan Frech Oct 28 '17 at 22:27
4
\$\begingroup\$

LaTeX truth tables

Write a program or a function that accepts the list of outputs from a logic function and outputs the LaTeX code for its truth table.

The inputs should be labeled as lowercase letters a-z, and the output should be labelled as F. The length of list of inputs will always be shorter than 2^25, which means that number of inputs will always be less than 25, so you can use letters from lowercase alphabet for input names.

Input

A number n of inputs and list of length 2^n of binary numbers which represents the outputs of a logical function.

Output

LaTeX code that produces the truth table for that function. Input and output values should be centered in rows. There must be a line between table header and its values and between inputs and output, so the code should be similar to that below.

\begin{tabular}{c * <NUMBER OF INPUTS>|c}
<INPUTS>&F\\
\hline
<INPUT VECTOR i>&<OUTPUT>\\
\end{tabular}

Example

Input:

2
[0, 0, 0, 1]

Output:

\begin{tabular}{cc|c}
a & b & F \\
\hline
0 & 0 & 0 \\
0 & 1 & 0 \\
1 & 0 & 0 \\
1 & 1 & 1 \\
\end{tabular}

Which when displayed in LaTeX shows the following truth table

Truth table

General rules

\$\endgroup\$
  • \$\begingroup\$ What happens if there are >25 outputs? Do we label them abcdef...uvwxz? Also, just to be clear, can we assume that there will be at most 25 variables present? Also, what is the winning criterion? (I recommend code-golf for this challenge). \$\endgroup\$ – HyperNeutrino Oct 31 '17 at 20:09
  • \$\begingroup\$ There are not going to be > 25 input variables. I was thinking of shortest code so yeah, code-golf :) \$\endgroup\$ – drobilc Oct 31 '17 at 20:11
  • \$\begingroup\$ Okay. For the >25 variables part you might want to specify it, and you should add a note saying what the winning criterion is, and you might also want to consider what tags to use (probably just code-golf and maybe math, really). Once you add that ping me and I'd be happy to check it over :) \$\endgroup\$ – HyperNeutrino Oct 31 '17 at 20:16
  • 1
    \$\begingroup\$ "The inputs should be labeled as lowercase letters a-z, and the output should be labelled as y." It isn't really clear from this whether 'y' can also be part of the inputs or not (I guess not). Another thing that came to my mind is that you could give the possibility of taking 'n' as an input in addition to the list of '2^n' values, since that could remove some annoying boilerplate from some answers and this challenge seems more about generating a structured output than computing the base-2 logarithm of a number. \$\endgroup\$ – Leo Nov 1 '17 at 0:17
  • \$\begingroup\$ I agree, should I label the output name to something else? Like uppercase F or something like that? I'll add number of inputs as an input. \$\endgroup\$ – drobilc Nov 1 '17 at 8:03
4
\$\begingroup\$

Insert Random Squares Here


Related challenges.

< Insert sales pitch here >

The Challenge

Given a width and a height, output an image filled with random squares.

Input

Your program/function is given a width and a height in pixels.

E.g.:

yourProgram <width> <height>

Output

You must display the result on the screen, or output an image file in any acceptable format.

Rules

  • The number of squares to be generated is a random natural number between sqrt(w * h) / 2 and sqrt(w * h) * 2 (inclusive).
  • Each square's color will be randomly generated for each with R, G, B ranging from 0-255 and with alpha values ranging from 1-255.
  • Each square's width/height will be a random value between 1 and min(w, h) (inclusive)
  • Each square must be placed randomly. Part of the square may be outside the output image, as long as at least one pixel of the square is visible.
    • Placement at sub-pixel coordinates (e.g. x=0.239420, y=2.8298329) is allowed but not required.
  • Each possible output must be equally likely to occur.
  • The output must have a white or transparent background.

Example

Input and randomly generated parameters

Width: 10
Height: 20

Maximum square height: 10

Minimum number of squares: 8 Math.sqrt(10*20)/2 = 7.0710678118654755
Maximum number of squares: 28 Math.sqrt(10*20)*2 = 28.284271247461902

Number of squares  in this example: 8

Output

Scaled 2000%:

Output with the parts of the squares that are off-screen

(Scaled 2000%.) The gray part is the part that is displayed on the screen.

\$\endgroup\$
  • \$\begingroup\$ does the background have to be transparent, or can it be a constant color? \$\endgroup\$ – dzaima Nov 22 '17 at 15:01
  • \$\begingroup\$ @dzaima I guess the "transparent" doesn't make sense if there is nothing behind the background. A better question is: Must the background be white? \$\endgroup\$ – user202729 Nov 23 '17 at 13:10
  • \$\begingroup\$ @AdmBorkBork That's kind of what I meant to say with "Each possible output must be equally likely to occur". Think it needs clarification? \$\endgroup\$ – user2428118 Nov 23 '17 at 13:44
  • \$\begingroup\$ @dzaima Clarified \$\endgroup\$ – user2428118 Nov 23 '17 at 13:46
  • \$\begingroup\$ @user202729 Updated the rules to say the output must have a white or transparent background \$\endgroup\$ – user2428118 Nov 23 '17 at 13:47
  • \$\begingroup\$ Ah, I had understood the "each possible output equally likely" to mean the positioning of the squares themselves, rather than a comment on the entirety of the random possibilities. Maybe just expanding that bullet point to read something like "The squares' number, color, size, and position must all be equally likely to occur" or similar wording. \$\endgroup\$ – AdmBorkBork Nov 27 '17 at 13:39
4
\$\begingroup\$

A Fine-Grained Mesh

If you've used Matlab before, it's highly likely that you've heard of meshgrid. It's a function that has since mostly been obsoleted by broadcasting, but it still has its uses sometimes.

The function itself is relatively simple. Given two vectors x and y of length m and n, create two 2-dimensional matrices X and Y both with m columns and n rows such that:

  1. Any row of X is a copy of x
  2. Any column of Y is a copy of y

But typing out meshgrid(x,y) takes so long, you know? I'd like to be more efficient with my coding. Your job is to reimplement this function in the fewest bytes possible.

Standard loopholes disallowed.

\$\endgroup\$
  • 2
    \$\begingroup\$ This is a classical case of do X without Y which is discouraged. The reason is that some languages might have something similar that is not quite equal, and then it is always the question: Where do you draw the line? I recommend against banning built ins. \$\endgroup\$ – flawr Dec 10 '17 at 19:46
  • \$\begingroup\$ @flawr I removed that as a requirement. \$\endgroup\$ – Steven H. Dec 11 '17 at 19:58
  • 1
    \$\begingroup\$ You could add "builtins that compute this are allowed but a second implementation without using that builtin are strongly encouraged" \$\endgroup\$ – Giuseppe Dec 11 '17 at 20:34
  • \$\begingroup\$ what types are x and y? Int, float, char, ...? \$\endgroup\$ – Giuseppe Dec 11 '17 at 20:36
  • \$\begingroup\$ x and y can be any vector-like type. Lists, arrays, actual vectors... \$\endgroup\$ – Steven H. Dec 12 '17 at 2:30
4
\$\begingroup\$

Flit - a simple board game for bots


I've made a human playable version of this game with a simple strategy to give an idea of how the game plays out. You can play it before or after reading the rules here - picking up the rules intuitively adds an extra challenge...

If playing this gives any idea about whether the KotH version would be better with 2, 4, or more players per game, or any other subtle adjustments that would help, please let me know.


Note: adjacency is vertical or horizontal - for this game there are no diagonal neighbours.

Overview

The board is a square grid. Each bot starts with 2 pieces of their colour, and gains more pieces by converting neutral pieces that appear from time to time. The objective is to end up with more pieces than your opponents.

Each turn, one bot moves. It chooses one of its pieces and moves it to be next to another of its pieces. There is no limit to the distance a piece can move in a single step, provided it lands next to a piece of the same colour.

Neutral pieces

There are initially zero neutral pieces.

A new neutral piece can appear at any time, regardless of whether there are already neutral pieces unconverted. A neutral piece will only appear on an empty square that has 4 empty neighbours, to prevent it being instantly converted.

If a neutral piece is adjacent to another piece, it is converted - it becomes the colour of that piece. A neutral piece can only ever be adjacent to a single other piece - it will be instantly converted before any other bot has a chance to move next to it.

Moving

A move is specified by an origin square and a destination square. It is a valid move if the origin square contains a piece of the bot's colour, and the destination square is empty and is adjacent to at least one piece of the bot's colour. Note that the piece being moved cannot also be the piece adjacent to the destination square (a piece cannot simply move next to its own previous position). Two distinct pieces are required - one to be moved, and one to be adjacent to the destination.

[Not moving is a valid move, and is indicated by specifying the same coordinates for origin square and destination square. not sure about this rule] Not supplying a move within the time limit also results in not moving, but repeatedly exceeding the time limit will lead to the bot losing the opportunity to make further moves.

Communication

The board information will not be supplied each turn. Instead the bot must keep track of the board state itself. Each time a change is made a message will be sent to all bots describing the change. If a bot chooses not to move, the non-move will not be broadcast.

The board starts empty. The initial two pieces for each bot will be broadcast to all bots, then the first bot will be sent a request for a move, to which it must respond within the time limit. Any response sent after the time limit expires will be discarded (any waiting input will be read and discarded before the next request for a move is sent to that bot).

Bots will therefore have complete information about the board state at all times.

Specification

Available: An available square is an empty square that has 4 empty neighbours

Players

There are 4 bots competing in each game. Bots are numbered 1 to 4 and take turns in that fixed order.

Board

The board is a 32 by 32 square grid. It wraps toroidally - every square has 4 neighbours. The board has no boundaries - no edges or corners to give an advantage.

Initial state

For each bot, one piece will be placed on a square chosen uniformly from the available squares. After all first pieces have been placed, a second piece will be placed for each bot in the same way. The initial state contains no neutral pieces.

Addition of neutral pieces

Each turn one bot will move. After that move has been made, the addition of a new neutral piece will be considered. A square will be selected at random. If that square is available then a neutral piece will be placed on it with probability 1/16. If the square is unavailable then play continues - a second square will not be selected. [This differs from the human playable version linked above: there a list is kept of all available squares and a neutral piece is placed on one of those with probability 1/6 each turn - I now prefer this approach so the rate of new neutral pieces does not slow in the end game]

Bot STDIN

All received messages will be terminated by a newline. Each bot will receive messages of two types: an update or a move request

Update:

x y c

where (x, y) is the square to be updated, and c is the new colour (which may be 0 for empty, 1, 2, 3 or 4 for a bot colour, or 5 for neutral).

Move request:

M

where M is the literal string "M" and indicates that a move is required.

Bot STDOUT

The response must be terminated by a newline. A bot responds with a move in the following format:

x0 y0 x1 y1

where (x0, y0) is the origin square, and (x1, y1) is the destination square.

If origin and destination are identical, no move will be made. This is valid and does not lead to the bot being penalised. The bot will only be penalised if it fails to respond within the time limit.

Time limit

The time limit is 50ms. If a bot exceeds the time limit on 5 consecutive turns then it will no longer be prompted for moves. That bot will be frozen for the rest of the game.

Winning criterion

The winner is the bot with the most pieces when the game ends. There is no reward for second place. If two bots tie for first place, neither is rewarded.

The game ends when one of the following conditions is met:

  • the total number of turns taken exceeds 32,768 (8,192 per bot)
  • all 4 bots choose not to move consecutively
  • one bot has too many pieces to catch up with

Too many pieces to catch up with is defined as follows:

  • A, B and C are the numbers of pieces of the other 3 bots.
  • D is the number of pieces of the bot in question.
  • N is the number of neutral pieces.
  • E is the number of empty squares.
  • P is the number of potential neutral pieces. P = N + E - 4
  • M is the maximum number of pieces attainable by A, B or C.
  • M = Max(A+P, B+P, C+P)
  • If D > M then the bot has too many pieces to catch up with.

I've tried to make this game as simple as possible, while still having non-trivial dynamics.

\$\endgroup\$
  • 1
    \$\begingroup\$ Time limit could be abused - the bot is allowed to just take its sweet time for 4 turns straight, followed by a reset... How about average time? \$\endgroup\$ – Alion Feb 18 '18 at 12:40
  • \$\begingroup\$ Ah good point. I'll probably go with average time per move after an arbitrary 10 seconds to allow for high variance early on. \$\endgroup\$ – trichoplax Feb 18 '18 at 12:57
  • 1
    \$\begingroup\$ First player is at a very slight, systemic disadvantage. He's the only one that cannot see a neutral piece on his first turn. Piece spawning should probably happen before each player makes a move, instead of after. \$\endgroup\$ – Alion Feb 20 '18 at 14:58
  • \$\begingroup\$ Oh good point. That small difference is definitely relevant. Neutral pieces before rather than after a move sounds good. \$\endgroup\$ – trichoplax Feb 20 '18 at 17:18
4
\$\begingroup\$

Musical Washing Machine

I have a washing machine with a knob and several buttons. The knob selects the type of laundry and the buttons cycle through water temperature, etc. options. When pressed, these each create a musical note. There are five musical notes that can be made, in this ascending order: F A C D E

knob (K)
   When 360ed: play D and reset all other buttons
wash temp (T)
   1st press (cool -> warm): A
   2nd press (warm -> hot): F
   3rd press (hot -> cold): E
   4th press (cold -> cool): C
   (repeat)
spin speed (S)
   1st press (medium -> max extract): F
   2nd press (max extract -> no spin): E
   3rd press (no spin -> medium): A
   (repeat)
soil level (L)
   1st press (medium -> heavy): A
   2nd press (heavy -> extra heavy): F
   3rd press (extra heavy -> light): E
   4th press (light -> medium): C
   (repeat)

The Challenge

Given a series of notes, determine if if can be played on my washing machine, and, if so, output the series of moves to generate it.

I/O coming soon to a washing machine near you

\$\endgroup\$
  • \$\begingroup\$ As a side note, there is a washing machine that plays the New Zealand Athem \$\endgroup\$ – MickyT Aug 27 '15 at 21:02
  • \$\begingroup\$ I think I understand, but it looks a bit confusing. Maybe you should give an example with an explanation. \$\endgroup\$ – Beefster Feb 9 '18 at 17:18
4
\$\begingroup\$

Make a Sierpinski triangle

Your challenge is to output a n-th order right-angle Sierpinski triangle, similar to this (third-order):

#
# #
#   #
# # # #
#       #
# #     # #
#   #   #   #
# # # # # # # #

Input:

A number, n, and a character (in this example '#');

Output:

A 2**n (two to the n) line Sierpinski triangle, made of the given character. You could consider it a two-state cellular automaton: the cells are separated by a single spaaace; if it is on, it contains the given character; Otherwise is contains a spaaace.

Examples:

in:

0 *

out:

*

explanation:

2**0=1

in:

1 *

out:

*
* *

in:

2 *

out:

*
* *
*   *
* * * *

Winner:

this is codegolf so the winner is the answer with the least bytes. (NOTE: might add something tho do with triangles of the same character.)

Hint:

it might be helpful to know that the n-th line contains the previous line xor that line shifted right by one cell (x^(x>>1)).

\$\endgroup\$
  • \$\begingroup\$ Welcome to PPCG and thanks for using the sandbox! There is a challenge to draw an Sierpinski Triangle which is broad enough to allow your format, so the challenge might be considered a duplicate. Then again I think the old challenge is no longer up to the current site standards and should probably be closed ... \$\endgroup\$ – Laikoni Mar 10 '18 at 10:08
  • 1
    \$\begingroup\$ This is also close enough to Generate Pascal's triangle that by the standards of this site (can answers be copied with trivial modifications?) I would consider it a duplicate. \$\endgroup\$ – Peter Taylor Mar 10 '18 at 19:42
4
\$\begingroup\$

King of the Hill: Avalon

Avalon is a semi-team-based strategy card game played with 5 - 10 players. The objective is simple but the gameplay is not as simple. The good people want to complete 3 quests while keeping Merlin alive, and the evil people want to fail 3 quests or assassinate Merlin.

Gameplay

Each player has a role, some of which have special abilities. All players need to contribute and use logic for that alignment to win. There are up to 5 day cycles which look like the following:

  1. The leader is the player to the right of the last leader. If this is the start of the game, choose a random player to start.
  2. The leader will select a specified number of players to form a Quest Team.
  3. Discussion Period will open. Everyone can post up to 50 messages to global chat.
  4. Everyone (including the leader) will vote Yes or No. If there is a majority, the Team will attempt the Quest (step 4). Otherwise, the Team is disbanded and another attempt is made (step 1).
  5. Discussion Period will open. Everyone can post up to 20 messages to global chat.
  6. Each player will perform the Quest Task (no actual task is required). Good people automatically perform the task. Evil people will be given the option whether or not to perform the task.
  7. If enough players perform the Task (all players for small quests, or at least #players-1 for larger quests in the end game), then the Quest is completed (progress for good). Otherwise, the Quest is failed (progress for evil).
  8. Final Discussion will happen. Everyone can post up to 10 messages to global chat.

If all players have been the leader in a single day cycle, the original leader will be given the choice of who the Quest Team is and there will be no vote; it will automatically pass.

If 3 quests pass, a 50-message Discussion Period will open for all players to discuss the Assassin's plans.

Roles

Good

  • Merlin - Merlin knows Good and Evil apart. At the beginning of the game, Merlin will be given a list of evil people.
  • Percival - Percival is the Protecter of Merlin. At the beginning of the game, Percival will be given the roster number of Merlin. However, if Merlin's shadow Morgana is present, Percival will be given two roster numbers, one of which is Merlin and the other which is Morgana (in no particular order or distinction)
  • Loyal Servant - The Loyal Servant has no special abilities but is good-aligned.

Evil

  • Assassin - The Assassin can lead evil to triumph even if 3 quests are completed. At the end of the game, if 3 quests are completed, the Assassin can choose a player to assassinate. If they are Merlin, evil is truimphant; otherwise, evil fails.
  • Morgana - Morgana is Merlin's shadow. Her ability is merely to confuse Percival, because Morgana also knows who evil is, just like Merlin.
  • Mordred - Mordred is the Leader of the Evil. Mordred doesnot reveal himself to Merlin.
  • Minion - The Minion has no special abilities but is evil-aligned.

At the beginning of the game, all evil people are given a list of all other evil people. This list does not tell evil who the Assassin is.

Controller and Bot Details

Bots may be written in any language as long as it can be run from the command line. Each bot must be a single file and take input from STDIN and output to STDOUT. In order to speed things up, your submission must be able to idle; that is, it will be started up and then given lines of input as the game progresses. If this inhibits too many people's ability to make a bot, I may change this rule.

At the start of the game, all of the bots will be started up. They should wait for input before doing anything. They will all be run in parallel and if any of them freeze, take too long to respond, or crash, they will be removed from the competition, so please make sure your bot runs correctly :P.

The first input will be given as a space-separated list of non-negative integers. The first integer represents the bot's role; 1 is Loyal Servant, 2 is Merlin, 3 is Percival, 4 is Minion, 5 is Assassin, 6 is Morgana, and 7 is Mordred. The second integer represents the number of players, n. The following n integers represent the roles that are in the game, in no particular order. The remaining integers represent a list of relevant characters; for Percival, this is a list of length 1 or 2 representing who Merlin is or who Merlin and Morgana are, and for Merlin and all evil roles, it is a list of all other evil players (except for Mordred in the case of Merlin). This input will be fed in followed by a newline ("\n") and the game will start immediately without waiting.

The following messages are valid for input with their meanings written beside (# represents any non-negative integer and #... represents a list of non-negative integers of any size). All messages are given as a space-separated list of non-negative integers (there will only be a single space between integers in the program input; the formatting below is just to make it look nice in the post).

0  # #... - Day # has begun and the day cycle begins. The players in this game are #...
1  #      - You are selected as the leader; please form a Quest Team of # people.
2  #      - Same as above, but there will be no vote for your final decision.
3  # #... - # selected the team #... has been selected. Discussion Period will start.
4  # #... - # posted the message #... in chat during pre-vote Discussion Period.
5  #      - Discussion Period is currently happening (pre-vote). You have # messages remaining. Please post a message.
6  # #... - # selected the team #... has been selected. Please vote.
7  # # #  - The final vote is # to # for yes. The Quest Team was # { 0 - disbanded ; 1 - accepted }. Discussion Period will start.
8  #...   - The quest team is #...
9  # #... - # posted the message #... in chat during pre-quest Discussion Period.
10 #      - Discussion Period is currently happening (pre-quest). You have # messages remaining. Please post a message.
11        - You are in the quest team and you are evil. Please choose whether or not to perform the Quest Task.
12 # # #  - # passes and # fails; the quest # { 0 - failed ; 1 - succeeded }.
13 # #    - Currently # quests have succeeded and # quests have failed. Discussion Period will start.
14 # #... - # posted the message #... in chat during final Discussion Period.
15 #      - Discussion Period is currently happening (final). You have # messages remaining. Please post a message.
16        - 3 quests have passed. Merlin must be killed for evil to win. Who do you choose to assassinate?
17 # #    - #-th game over; # won. Please reset the state of your bot. Please go back to the first step.

Each of the non-obvious inputs are explained below along with valid responses.

1

This one means that you are the current leader and you must choose # people for a Quest Team. If you are good, you should try to choose either all good people or choose evil people and hope to reveal them. If you are evil, you should try to choose at least one evil person so that the quest fails, but try not to choose one evil person along with all confirmed good people because then that will either cause the quest to pass or cause the evil person to be revealed.

One line of space-separated non-negative integers will be taken from the program. If the number of players chosen is wrong, the formatting is incorrect, or there are integers greater than the number of players, your program will be disqualified.

2

This one means that you are the current leader again and you must choose # people for a Quest Team, but this time your decision is final. The output format is the same.

6

This one means that a Quest Team is being proposed and you must vote. One line of output will be taken; if it is 0 exactly, then the vote is no. If it is 1 exactly, then the vote is yes. Otherwise, the bot is disqualified.

7

This one means that the vote has concluded with # people agreeing to the team and # people disagreeing with the team. The third argument is 0 if the vote failed or 1 if the vote passed (you can probably ignore this since greater-than and less-than comparison is trivial in almost all languages).

10

This one means that you were selected on a Quest Team that was approved, but you are an evil player. One line of output will be taken; if it is 0 exactly, then the action is not performed. If it is 1 exactly, then the action is performed. Otherwise, the bot is disqualified.

11

THis one means that the quest has finished with # people performing the task and # people not. The third argument is 0 if the quest failed and 1 if the quest succeeded (most of the time you can just check to see if the second argument is 0, but in late-game that doesn't always work for larger game sizes). No output will be taken.

14

This one means that 3 quests have succeeded and it is time for the Assassin to try to assassinate Merlin (this message is only given to the Assassin). One non-negative integer will be taken representing who to assassinate. If you try to assassinate any evil role who you know is evil (including yourself), you are disqualified for gamethrowing.

15

This one means that the #-th game has finished with # { 0 - evil ; 1 - good }. At this point, your bot should "restart". If your bot learns from past games, your bot can keep information around such as who won and different bots' strategies. You can't read other bots' files but you can try to remember how different bots play by preserving state between games.

Chat Message Format

Each message consists of up to 2 parts. The first part is optionally to state your role (this does not have to be truthful). The second part is to state something about either general observations or something about another player in particular.

First Part

The first part is a single integer representing which role you wish to claim. 1 is Loyal Servant, 2 is Merlin, 3 is Percival, 4 is Minion, 5 is Assassin, 6 is Morgana, and 7 is Mordred. Use 0 if you don't want to claim your role.

Second Part

The second part is a bit more complicated. Since there are three Discussion Periods that are used for different purposes, some of the messages are unique to certain discussion periods. All messages can be posted at any time, but if you post a message in a Discussion Period where it doesn't make sense to post it, other bots might think you're insane :P.

0       - I don't want to send a message.
1  #    - My decision on the Quest Team is # (only applicable for PRE-VOTE)
2  #    - I think # is evil
3  #    - I think # is good
4  #    - I trust # / I think # is telling the truth
5  #    - I don't trust # / I think # is lying
6  #    - I agree with #
7  #    - I disagree with #
8  #... - I think #... are working together
9  # #  - I think # has role # (see above for numbering of roles)
10 #    - I think the quest will # { 0 - fail ; 1 - pass } (only applicable for PRE-QUEST)

For example, if I wanted to say "I'm Percival and I think 3 and 7 are working together", I would send "3 8 3 7" as my message. If I just wanted to say "I don't trust 2", I'd send "0 5 2".

If you send anything that doesn't match one of the valid formats, it will skip your message for that turn.

Role Lists

The game looks slightly different depending on the number of players:

5  - Loyal, Loyal, Merlin, Minion, Assassin
6  - Loyal, Loyal, Loyal, Merlin, Minion, Assassin
7  - Loyal, Loyal, Percival, Merlin, Minion, Minion, Assassin
8  - Loyal, Loyal, Loyal, Percival, Merlin, Minion, Morgana, Assassin
9  - Loyal, Loyal, Loyal, Percival, Merlin, Minion, Mordred, Morgana, Assassin
10 - Loyal, Loyal, Loyal, Loyal, Percival, Merlin, Minion, Mordred, Morgana, Assassin

The game always has a good-majority with as little of a difference between faction sizes as possible. If there are 7 or more players, the second last quest requires 2 fails in order to fail.

Quest Team Sizes

5 - 2, 3, 2, 3, 3
6 - 2, 3, 4, 3, 4
7 - 2, 3, 3, 4, 4
8+- 3, 4, 4, 5, 5

Controller

Controller TIO link

Scoring

The game size will be max(players, 10). All combinations of players to roles will be run ten times. The player with the most total wins will win, tiebreak by whichever bot was submitted first. Scoring will not start until there are 5 players.

Rules

  • The game will only run once there are 5 submissions
  • You can name your bot anything because the name is not used in-game
  • Your bot does not have to be deterministic (because if they all were, then running the games ten times each would be pointless)
  • You may not read from or write to any external files, including other bots' files. If I remove the restriction about bots needing to run idly for the entire game, I will allow bots to write to an external file to store state.
  • You must use software that I can access for free on Fedora 27. Unfortunately, if the software is not available or not free, I will not be able to score your submission.
  • I reserve the right to disqualify any solutions that I believe to be malicious, including but not limited to taking excessive amounts of time or memory or otherwise attempting to harm my system. Also my computer is not very strong in terms of computing power so please make sure your bot doesn't require a supercomputer to run :P

motivation for this challenge and some of the wording and rules were taken from the Let's Play Mafia! king-of-the-hill challenge

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

-(-(--x)--))> Code Kebabs! <-(-(--x)--))


Your goal is to parse Code Kebabs, they look like this:

-x--> 8
2 <-(-(--x)--))
-x-x-x--> -10
--x> 255

A Code Kebab is made up of 3 parts, the stick, the tip (< and >), and the stand (the number compared by)

stick tip stand 
--x-- >   -5

The stick


The stick contains 4 operators, and the variable (x) The operators are listed here, in order of precedence:

  1. ( ... ) | Brackets. They are the "veggies" on a code kebab. Everything inside them runs before the rest of the kebab, with the last, deepest pair going first. Brackets can be nested.

  2. v-- | Suffix decrementation. This is one of the 4 parts of the stick, and decrements the value supplied to it by one.

  3. v-v | Subtraction. This is the 2nd part of the stick, and subtracts the two values.

  4. --x | Prefix decrementation. This is the 3rd part of the stick, and decrements the value supplied to it by one.

  5. -v | Negation. This is the 4th and final part of the stick, and inverts the value supplied.

Each operator returns it's result, and can be used as input for other operators.

The Tip


The tip is one of two symbols: < or > When the tip is <, the stand must be left of it, with the tip being left of the stick. When it is >, the stand is to it's right, with the tip being on the right of the stick.

The Stand


The stand is any integer. That's all there really is to say about it.

Execution of the kebab


You can't execute a kebab without eating it!

Kebabs are executed in a loop until their condition (The result of the stick being less than the stand's value) is fulfilled. When execution is finished, the variable (x) is set to the result of the stick, X is printed, and execution resumes again unless the condition is fulfilled.

When execution starts for the first time, X is set to 10 beforehand.

TODO


  • Add test cases.

  • Clear a few things up.

  • Make the description of execution a bit clearer?

\$\endgroup\$
  • 1
    \$\begingroup\$ You should describe the difference between pre and post decrement. \$\endgroup\$ – Pavel Apr 30 '18 at 21:22
  • \$\begingroup\$ Also, how are the input variables initialized? \$\endgroup\$ – Pavel Apr 30 '18 at 21:22
  • \$\begingroup\$ A test case that has something like -x--5 to force parsing it as a subtraction and unary negation, rather than post-decrement x, would be very good. \$\endgroup\$ – AdmBorkBork May 1 '18 at 13:02
  • \$\begingroup\$ @AdmBorkBork Numbers aren't mentioned as a requirement for parsing, so -x--x would probably work better. But yea, good idea. \$\endgroup\$ – moonheart08 May 1 '18 at 13:48
  • \$\begingroup\$ @Pavel The input variable X is set to 10 beforehand, as mentioned in The execution of the kebab \$\endgroup\$ – moonheart08 May 1 '18 at 13:51
  • \$\begingroup\$ Is this correct? And if not, where is my flaw? The input is the Code Kebab (i.e. -x--> 8) with x=10 by default, and the output is the x once it fulfills the Kebab check. So for -x--> 8 with x=10 as start, it will do x-- first (so it becomes x=9), and then the -x negation (so it becomes x=-9), and then checks it with the tip (-9 > 8). This is false, so it continues with x now being -9? So then x-- again (x=-10), then -x again (x=10), and then the check again (10 > 8). Which is true, so it outputs 10 as result? I have the feeling I misunderstand it a bit.. \$\endgroup\$ – Kevin Cruijssen May 2 '18 at 11:08
  • \$\begingroup\$ Also, why is suffix decrementation before prefix? In most languages (Java, JS, C, etc.) it's usually the other way around. \$\endgroup\$ – Kevin Cruijssen May 2 '18 at 11:10
  • \$\begingroup\$ And one more question, is something like ---x (negation & prefix decrementation), or x---x (suffix decrementation & subtraction) a possible valid input? Or would these always be surrounded by parenthesis (---x would be -(--x) instead; x---x would be (x--)-x or x-(--x) instead). \$\endgroup\$ – Kevin Cruijssen May 2 '18 at 11:14
4
\$\begingroup\$

Nearest neighbors in a square lattice

Premise

Consider an infinite 2D square lattice. We can choose one point as the origin and label each point with a pair of integers that corresponds to points on the Euclidean plane:

enter image description here

Now consider the point at the origin, \$(0,0)\$. The set of lattice points closes to the origin (but not including the origin) is \$\{(1,0),(0,1),(-1,0),(0,-1)\}\$. We will call this set the \$1\$st nearest neighbors. The set of lattice points closest to the origin but not including the \$1\$st nearest neighbors is \$\{(1,1),(-1,1),(-1,-1),(1,-1)\}\$. We call this set the \$2\$nd nearest neighbors

Now we can define the \$k\$-th nearest neighbors as the set of points closest to the origin and not included in the union of the set of \$n\$-th nearest neighbors for \$n\in\{1,2,...k-1\}\$.

Define the sequence \$NN(k)\$ as the length of the set of \$k\$-th nearest neighbors.

Task

Given \$k\$, compute \$NN(k)\$. This is A105352 on OEIS without the first element.

Rules

  • You may use 0- or 1- based indexing.
  • Given \$k\$, you may either output the first \$k\$ elements of the sequence or the \$k\$-th element.
  • You may alternatively take no input and output the sequence indefinitely.
  • Standard loopholes disallowed.

Here are some 1-indexed test cases:

n   NN(k)
1   4
8   8
9   4
10  8
38  16
52  8
80  8
121 24
145 12
\$\endgroup\$
  • \$\begingroup\$ OEIS A105352. \$\endgroup\$ – Mr. Xcoder Sep 13 '18 at 20:47
  • \$\begingroup\$ @Mr.Xcoder Thanks \$\endgroup\$ – dylnan Sep 13 '18 at 20:58
  • \$\begingroup\$ Could you allow the infinite sequence \$\{NN(1),NN(2),NN(3),\ldots\}\$ as output (with no input)? \$\endgroup\$ – Delfad0r Sep 15 '18 at 8:34
  • \$\begingroup\$ @Delfad0r Sure. \$\endgroup\$ – dylnan Sep 15 '18 at 16:33
  • 1
    \$\begingroup\$ Very related. Just filter out zeroes. \$\endgroup\$ – user202729 Sep 15 '18 at 16:38
  • \$\begingroup\$ @user202729 Do you think it's a dupe? \$\endgroup\$ – dylnan Sep 15 '18 at 17:06
  • \$\begingroup\$ @dylnan I don't know... \$\endgroup\$ – user202729 Sep 17 '18 at 13:08
  • \$\begingroup\$ IMO it's a dupe: adding a loop and an if test is a pretty trivial modification. \$\endgroup\$ – Peter Taylor Sep 17 '18 at 14:34
4
\$\begingroup\$

Breaking into 3 Palindromes:

As discussed here and here, every positive integer can be written as the sum of 3 palindrome integers. Given a number "n", output these integers.

Challenge

  • This is a code golf challenge. The shortest functional solution wins.
  • The input number "n" will be any integer greater than 0 but less than 1,000,000,000.
  • The three output numbers must be palindromes. Their sum must be "n".
  • A palindrome number is a number which is the same forwards as backwards. It can have any number of digits.
  • To make this easier, I will allow positive or negative palindrome integers.
  • Output and input can be formatted in any what that is convenient as long as it can be readily understood.

Examples

input: 5
output: 0,0,5

input: 1234
output: 1001,222,11

input: 3141592
output: 2200022,926629,14941
\$\endgroup\$
  • 2
    \$\begingroup\$ This is actually a very interesting problem. The paper which proved that this would work for any base lists 40 different algorithms that are used to find these values depending on the value of "n". I suppose there should be a requirement to solve this in a reasonable about of time to avoid brute force but I don't know how I should phrase that. \$\endgroup\$ – kaine Sep 17 '18 at 21:18
  • \$\begingroup\$ It's up to you, but time limit requires a particular computer to test the solutions on. \$\endgroup\$ – user202729 Sep 18 '18 at 1:18
  • \$\begingroup\$ Maybe it would be a good idea to link that paper in the challenge. Also, I tried to bruteforce in 05AB1E, and the 1234 case already times out after 60 sec, so I won't even have to try 3141592.. It barely doesn't make it within the 60 sec, but does output most of the possible outputs. Maybe make this a [fastest-code] challenge instead of code-golf, so the goal is to solve it as fast as possible. Alternatively [fastest-algorithm] could be used as well, but usually when someone find one, others will copy it. \$\endgroup\$ – Kevin Cruijssen Sep 18 '18 at 6:41
  • 1
    \$\begingroup\$ Honestly, i don't think i am comfortable managing a fastest-algorithm challenge due to my own limited skill. I'm a pretty amateur programmer so if someone uses languages, libraries, etc. I'm unfamiliar with I won't be able to fairly judge them. This idea though (complicated but sounds simple) seems great for one of these challenges. \$\endgroup\$ – kaine Sep 18 '18 at 13:04
  • 1
    \$\begingroup\$ Would it be feasible to require the code to run within 20 minutes on Ideone? Is that linked to my computer's abilities? \$\endgroup\$ – kaine Sep 20 '18 at 13:39
  • \$\begingroup\$ I think if you keep this at base 10 (decimal only) it's not so bad. \$\endgroup\$ – ouflak Sep 21 '18 at 12:59
  • \$\begingroup\$ @ouflak I had no intention of leaving base 10. I'm really liking the Ideone idea but am not sure if people would be ok with that. \$\endgroup\$ – kaine Sep 21 '18 at 18:51
  • 1
    \$\begingroup\$ rnta.eu/cgi-bin/three_palindromes/pal3.py and somethingorotherwhatever.com/sum-of-3-palindromes The speeds for these are bad at all. One in python the other in Javascript. I'm doing a C++ version (completely ungolfed) as I'm at a bit of a lull at the moment. It's just a translation of the Javascript code with some tweaks. I'll post a link to that as well. I would forget the timings and go with the straight up challenge. \$\endgroup\$ – ouflak Sep 26 '18 at 9:22
  • 1
    \$\begingroup\$ I've done this up in non-golfed C++. Anybody know a site where I can put this online where people can run it? It's big, but fast. \$\endgroup\$ – ouflak Oct 3 '18 at 15:24
  • 1
    \$\begingroup\$ The non-golfed C++ is 36 kbytes. Maybe limiting this to just the 4 digit case might be OK. I might try that in LUA and see what it looks like. This is such a great idea. Unfortunate that the algorithms are so lengthy. \$\endgroup\$ – ouflak Oct 8 '18 at 13:56
  • \$\begingroup\$ @ouflak, the fact that the algorithms are lengthy is why I thought this would make a good challenge. It is ripe for optimization. I'm worried about posting this challenge though as I'm sure there are many algorithms that will give an answer eventually but are so slow they defeat the purpose of the challenge. \$\endgroup\$ – kaine Oct 8 '18 at 14:29
  • \$\begingroup\$ Ok, I've sorted out a much shorter algorithm in LUA for the three digit case, un-golfed. repl.it/repls/AchingEnchantedHack. This has given me an idea for how to sort out the general case, which I think now actually might not be so bad. \$\endgroup\$ – ouflak Oct 9 '18 at 7:43
  • \$\begingroup\$ Here is a solution that should work for any sized number. This is brutally un-golfed LUA. I haven't even taken the opportunity to use a recursive function where it obviously would apply. For 5 digit numbers and smaller, it's pretty quick, easily less than a second. For 6 digit numbers and above, it depends on how soon it finds the first set of palindromes. I had one number (390081) take a good five minutes on the test site. I'm sure it would be quicker on my machine. I'd like to think there are places for optimization for speed (as well as golfing). repl.it/repls/BlondWaryShareware \$\endgroup\$ – ouflak Oct 9 '18 at 11:59
  • \$\begingroup\$ Just one other comment on your constraints, I wouldn't allow negative palindromes as I'm not convinced this makes it 'easier'. Should I start golfing this thing? ;) \$\endgroup\$ – ouflak Oct 9 '18 at 12:10
  • \$\begingroup\$ @ouflak you can probably wait until i post it as a real question but your enthusiasm definitely implies I need to. \$\endgroup\$ – kaine Oct 9 '18 at 12:50

You must log in to answer this question.

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