438
\$\begingroup\$

What is the Sandbox?

This "Sandbox" is a place where Programming Puzzles & Code Golf (PPCG) 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

2417 Answers 2417

3
\$\begingroup\$

Got Your PIN!

I bet I can write down your PIN! 0000 0001 0002 0003 ... 9999.

Task: Write a program that outputs a string containing all possible four digit PINs.

The string should not contain any whitespace (trailing newline is okay).

Score: Length of program (in bytes) + length of output.

Explanation

The output string only needs to contain each PIN somewhere in it; digits can be reused. For instance the string “123456789” contains the PINs 1234, 2345,3456,4567,5678,and 6789. By reusing digits, it's possible to save a significant amount of space from the naive implementation (0000000100020003...9999).

At best, this could be written as a 10,003 digit string. 4 digit for the first PIN, then one more digit for the other 9999 PINs.

Testing your code

I've written a basic Python script that can check your solution and indicate any PINs you are missing.

import sys
s = sys.stdin.readline()
passes = True
for ix in range(10000):
    pin = "%04d" % (ix)
    if s.find(pin) == -1:
        print("Missing PIN %s" % pin)
        passes = False

if passes:
    print('Result passes!')
print('String length is %d characters.' % len(s))
\$\endgroup\$
  • 1
    \$\begingroup\$ Nice, but I think you need to replace code-golf with code-challenge as this isn't just scored by shortest code. \$\endgroup\$ – Adám Sep 28 '17 at 22:25
  • \$\begingroup\$ Very related \$\endgroup\$ – H.PWiz Sep 28 '17 at 22:29
  • \$\begingroup\$ This is just codegolf.stackexchange.com/q/42728/194 with hard-coded input, and hence qualifies as a dupe. \$\endgroup\$ – Peter Taylor Sep 29 '17 at 11:08
  • \$\begingroup\$ Too bad it's a duplicate... but now I know about De Bruijn sequences! \$\endgroup\$ – Dominic A. Sep 29 '17 at 23:19
  • \$\begingroup\$ @PeterTaylor: I think there's one even more dupey than that; I've been trying to find it all day. The "background" to it was a keypad on a building door that had a 4-digit code. \$\endgroup\$ – Shaggy Sep 30 '17 at 0:59
3
\$\begingroup\$

Roll identical boson dice

When you roll two dice, the chance of a 5 and 6 in either order is a 2 in 36 (or 1/18), since it could happen as (5,6) or (6,5). But (6,6) can only happen one way and has a 1 in 36 chance.

Our dice will instead work as identical bosons: (5,6) and (6,5) are a single outcome {5,6} that is equally likely to {6,6}. So, each of these 21 unordered pairs is equally likely, with chance 1/21.

{1,1}, {1,2}, {1,3}, {1,4}, {1,5}, {1,6}, {2,2}, {2,3}, {2,4}, {2,5}, {2,6}, {3,3}, {3,4}, {3,5}, {3,6}, {4,4}, {4,5}, {4,6}, {5,5}, {5,6}, {6,6}

Similarly, for 3 dice, [5,5,6], [5,6,5], and [6,5,5] all count as a single outcome {5,5,6}, but [6,5,6] is different.

Task: Output a random roll of n boson dice, so that each possible result is equally likely as an unordered multiset, i.e. when sorted.

It's OK if your output is ordered as long as the overall probabilities are right. You may sometimes output [5,6] and sometimes [6,5] as long as their total chance is 1/21. They don't have to each be 1/42 chance. You could output [5,6] with 1/21 chance and never [6,5].

Input: A positive integer n

Output: A random list of n numbers from 1 to 6, so that each outcome is equally like when taken as an unordered multiset.

Time restriction: Your code has work up to n=50 within 1 minute.

\$\endgroup\$
  • \$\begingroup\$ I think it's unlikely that there'll be an algorithm for this terser than simply constructing the list of all possibilities, then selecting a random element from it. As such, I'm not sure the randomness adds to the task here. It's possible I'm wrong. (I toyed with some methods of restricting complexity to ban this solution, but I couldn't find one I was satisfied with.) \$\endgroup\$ – user62131 Jun 22 '17 at 22:48
  • \$\begingroup\$ @ais523 I know some fairly nice methods to generate these directly, but I don't know if they'll beat out the boring one you suggest. Rolling repeatedly until sorted is also boring and direct. Maybe a complexity restriction is needed. I'll see what I can golf up. \$\endgroup\$ – xnor Jun 23 '17 at 7:24
  • \$\begingroup\$ with the (new) time restriction this is more like math-golf than code-golf. Can you give away any of your "nice methods"? Is it the weighted probability of every digit of the 50-digit number ,one of them? \$\endgroup\$ – user72269 Oct 2 '17 at 17:29
3
\$\begingroup\$

Limited-Information Maze-Solving Bot

(Still in draft/beta format. Feedback welcome.)

Based on a challenge idea I posted in chat and the ensuing conversation. Thanks to NathanMerrill, zgarb, and Jonathan Frech for assistance in fleshing this out.

The challenge

You're writing two separate programs/functions/routines/etc. The first, which we'll call the helper program, takes the input maze and calls the second, which we'll call the solving bot. The solving bot must solve the maze based on its interaction with the helper program.

The maze is 51x51 characters in size. For clarity in this challenge description, it is composed of # walls and corridors, but you can use any two distinct, consistent ASCII characters of your choice. E.g., use ! for walls and x for corridors, use 1 for walls and 0 for corridors, etc. This maze is one of many that will be the input to your helper program/function.

The maze start is always guaranteed to be somewhere on the left-most column, and the exit is always guaranteed to be somewhere on the right-most column. The maze is guaranteed to have at least one path from the start to the exit. As a result of this construction, the very top row and very bottom row are all #, and the very left and right columns are all # except for the start and exit.

The solving bot that you're creating needs to find a solution to the maze (not necessarily the shortest), but is limited in that it can only "see" a new 5x5 section of the maze at a time. The bot is scored by how many times it needs to request a new 5x5 section from the helper program/function.

The upper bound is obviously to simply request every possible 5x5 section, for a score of around 100. The lower bound is where someone with perfect knowledge of the maze can request only those 5x5 sections containing the exact route of the shortest solution, possibly as low as 10. Your bot will be run through (1000?) different mazes, and the bot with the fewest total requests will be the winner.

The solving bot is placed on the left-hand side where the start is, and the first 5x5 section is provided for free. However, the bot doesn't know where, vertically, it is on the left-hand side of the maze. It could be in the top corner (as in the example below), in the bottom corner, or anywhere in between.

Input/Output

The code you're writing be required to take the maze as an input (STDIN, a file to read, etc.) and call a subroutine of some sort for the solution bot.

Input: (1000?) 51x51 mazes Output: How many total requests your solving bot took

Yes, this is a non-observable requirement to be on the honor system and ensure the two "halves" of your program (i.e., the I/O half and the solving half) talk to each other correctly and accurately. I trust the community enough to believe that this is OK.

Further rules

Your solving bot should be deterministic. That is, when presented with the same maze two or more times, it should request the same number of 5x5 sections.

Example Maze

(generated from http://www.delorie.com/game-room/mazes/genmaze.cgi )

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

Example starting block:

#####

# ###
#   #
### #
\$\endgroup\$
  • \$\begingroup\$ Does the solving bot also have to find the maze's start by scanning the left side or is it placed at the start position? \$\endgroup\$ – Jonathan Frech Sep 17 '17 at 19:18
  • \$\begingroup\$ related \$\endgroup\$ – Liam Sep 17 '17 at 21:47
  • \$\begingroup\$ @JonathanFrech Good point. We'll say that it's placed at the start position and the first 5x5 area is free. \$\endgroup\$ – AdmBorkBork Sep 18 '17 at 16:39
  • \$\begingroup\$ You could maybe only use one space wide corridors, as the second space does not add any information and thus you do not really get a true 5x5 section of the maze. Just a thought, though. \$\endgroup\$ – Jonathan Frech Sep 25 '17 at 11:50
  • \$\begingroup\$ @JonathanFrech No, that's a good point. I went with double-wide corridors since it looks more even with the character height, but looks aren't important when doing this challenge. I'll update the sizing. \$\endgroup\$ – AdmBorkBork Sep 25 '17 at 15:54
  • \$\begingroup\$ Are this maze's dimensions not 51x51? \$\endgroup\$ – Jonathan Frech Sep 25 '17 at 16:29
  • \$\begingroup\$ @JonathanFrech Apparently, with that generator, a size 50 doesn't yield a size 50. I'll either find a different generator or make my own for the actual challenge. Thanks! \$\endgroup\$ – AdmBorkBork Sep 25 '17 at 17:28
  • \$\begingroup\$ I think the problem does not lie in the generator; it lies in the maze's nature. If your corridors are always one character wide and you have walls on the far left and far right, your maze size has to be odd. \$\endgroup\$ – Jonathan Frech Sep 25 '17 at 19:13
  • \$\begingroup\$ Does this allow for "relative" vision? As in, after we get the initial block we would request "The next block to the right" instead of "the block at (2,7)"? \$\endgroup\$ – Kamil Drakari Sep 26 '17 at 20:22
  • \$\begingroup\$ @KamilDrakari Sure, that would be allowed. It's dependent upon how that half of your submission works. \$\endgroup\$ – AdmBorkBork Sep 26 '17 at 20:32
  • \$\begingroup\$ @JonathanFrech Good point. Maybe I'll compromise and make it a 51x51 maze. Thanks for the insight. \$\endgroup\$ – AdmBorkBork Sep 26 '17 at 20:32
3
\$\begingroup\$

Type the alphabet as fast as you can

Your task is to make a program that measures how fast you can type the letters of the English alphabet.

  • The program shall only accept lowercase letters a to z in alphabetical order.
  • Each letter is echoed as typed on the same line (without new line or any other separators between letters).
  • If you type an invalid character the program shall output Fail and exit.
  • If you type all 26 letters the program shall output the time in milliseconds it took from the first to the last letter and exit.
  • The timer starts when you type the first letter, a.

Example outputs:

b
Fail

abcdefgg
Fail

abcdefghijklmnopqrstuvwxyz
6440

This is , so shortest answer in bytes wins.

\$\endgroup\$
  • \$\begingroup\$ Related. I would also recommend to put "time" in some way into the title. \$\endgroup\$ – Laikoni Oct 27 '17 at 13:49
  • \$\begingroup\$ Thanks @Laikoni \$\endgroup\$ – Danko Durbić Oct 27 '17 at 14:53
  • \$\begingroup\$ Does the output have to be strictly in milliseconds, or at least in milliseconds, e.g. nanoseconds. Many builtin timing functions are in ns these days. \$\endgroup\$ – nimi Oct 27 '17 at 16:39
3
\$\begingroup\$

Draw the ☣ (Biohazard Symbol)

Draw the Biohazard symbol in an arbitrary colour on a distinctly coloured background.

Details

As output writing to a file (raster and vector formats are permitted) or displaying on the screen. The symbol itself should be at least 500 pixels wide. The background must at least have the size of the bounding box of the symbol but may be larger. The exact ratios of the used distances are given in following diagram (which was originally from here):

(Inspired by a post on 99%invisible)

\$\endgroup\$
  • 3
    \$\begingroup\$ Presumably simply outputting the character is invalid? I would mention that in the post, just to prevent those who think they're being "funny" \$\endgroup\$ – caird coinheringaahing Nov 20 '17 at 17:31
3
\$\begingroup\$

Stable modular exponents

It is well-known that the final three digits of Graham's number are 387. This is because Graham's number is a ridiculously tall exponent tower of threes: 3^(3^(3^...))), and it can be shown that any such tower of height at least 5 has 387 as its final three digits.

This generalises: given any base n and any starting number a, the exponent tower a^(a^(a^...))) will eventually stabilize modulo n. After that point, whatever you put in the topmost exponent, be it just a last a, or a continuation of the exponent tower (i.e. more than one a), or any other number, its congruency class modulo n will not change. That is the challenge that I set before you here today.

Problem statement

Write a program or a function that takes two numbers a and n (within your language's standard signed or unsigned integer range) as input, and outputs the limit l of the sequence a%n, (a^a)%n, (a^(a^a))%n,..., which can be mathematically proven to be eventually constant (and therefore have a well-defined limit).

Your program should be able to handle a > n (note that a and a+n doesn't necessarily give the same result), and we require that 0 <= l < n.

Warning: Reducing the exponents mudulo n, i.e. calculating this sequence recursively using b[0] = a%n, b[i] = (a^b[i-1])%n will yield the wrong result, and might not stabilize.

Test cases

If we call the function f(a, n), it should give the following:

> f(3, 1000)
387
> f(6, 10)
6
> f(5, 9)
2
> f(14, 9)
4
> f(3, 81)
0

Scoring criteria

Standard code golf rules, use as few bytes as possible.

\$\endgroup\$
3
\$\begingroup\$

Voronoi Iteration

Given a finite set of points in the plane, output the set vertices of the corresponding Voronoi diagram.

Details

A vertex of the voronoi diagram is a point of the plane that has the same distance to the three or more closest input points. As usual, you don't have to worry about the rounding issues of limited precision floating point numbers.

Examples

[(0,0),(2,0),(0,2),(2,2)] -> [(1,1)]
[(0,0),(1,0)] -> []
[(0,0),(2,0),(0,2)] -> [(1,1)]

Inspired by this question on MO.

\$\endgroup\$
  • 1
    \$\begingroup\$ I suggest having a test case with floating point coordinates. \$\endgroup\$ – user202729 Jan 22 '18 at 14:10
  • \$\begingroup\$ (although I already understood the test cases) it would be helpful to have an image. \$\endgroup\$ – user202729 Jan 22 '18 at 14:16
  • \$\begingroup\$ @user202729 It definitely needs more examples, but you can obviously interpret these coordinates as floating points as well. \$\endgroup\$ – flawr Jan 22 '18 at 14:17
  • \$\begingroup\$ Having a test case with floating point coordinates will help testing if programs handle floating point input correctly. \$\endgroup\$ – user202729 Jan 28 '18 at 7:32
3
\$\begingroup\$

Invisible target - probability KotH

?


In short

Walls are gradually added and the player nearest to the stationary invisible target at the end of the game wins.


Detail

Players are all present on a 32 by 32 grid of square cells, which wraps toroidally. One randomly chosen cell is the target, which is not indicated to any of the players (regardless of whether they are on that cell or not). The target does not move.

Players all take their turn simultaneously. After each turn there is a small chance of a wall being added.

Wall rules

  • The wall will never be placed on a player.
  • The wall will never be placed in a cell that does not have a route to the target.
  • Of the possible positions for the wall to be placed, one will be chosen uniformly pseudorandomly.
  • The probability of a wall being placed each turn is 1/7.
  • The wall will be placed such that every player still has a route to the target (this includes never placing a wall on the target).

Note that a player having a route to the target means that there exists a path that does not include a wall. If another player blocks the path it still counts as a path.

Movement rules

  • A player can move to any of the 4 orthogonally adjacent cells (or stay still).
  • A player cannot share a cell with another player.
  • A player cannot move onto a wall.
  • A player can move onto the target, but will have no way of knowing that this has happened.

Starting position

At the start of the game the arena will have no walls and the players will be randomly positioned with the guarantee that there are no other players within each player's 5 by 5 neighbourhood.

Winning

Play will continue until no wall can be placed for 10 consecutive attempts (note that attempts only occur with probability 1/7 each turn so this will take more than 10 turns). When play stops the player closest to the target (by Manhattan distance) is the winner. Although this makes it possible to have an arbitrary number of joint winners, the density of walls by this point makes it unlikely there will be many, and in most cases there will be a player on the target cell, meaning only a single winner.

Each of the (one or several) joint winners scores one point. Games will be played until one player is the clear winner, or until it is clear there should be joint winners overall.


Input and output

Input

During an N player game the input will be a space separated string of N+1 integers received on STDIN:

  • The player's position (an integer).
  • The position of any wall added since the player's last turn (an integer).
  • The position of every enemy player (N-1 integers).

Positions will be single integers from 0 to 1023, representing the distance in English reading order from the top left cell.

For a 4 by 4 arena this would give the following numbering:

 0  1  2  3
 4  5  6  7
 8  9 10 11
12 13 14 15

If no wall was added the wall location will be 1024.

During a particular game the order of enemy players will be consistent - the nth location will always refer to the same enemy player.

Output

The player must send an integer from 0 to 4 to STDOUT representing a move in English reading order:

  0
1 2 3
  4

(2 being no move).

A move to an unoccupied cell will not necessarily succeed - it will fail if another player is also trying to move to the same cell.

A move to an occupied cell will not necessarily fail - it will succeed if that player is also moving away from that cell (provided that player succeeds in moving away from that cell, and no other player is also trying to move to that cell).

This means two players can swap cells if they both decide to on the same turn.

A player taking longer than 50 milliseconds to respond will not move.


Sandbox questions

  • If someone can demonstrate that there can exist no better strategy than moving uniformly randomly, then I will not post this challenge. I'm hoping that the knowledge of the rules behind wall placement and the ability to block the movement of other players will make probability estimating competitive strategies non-trivial. This is answered - Nathan Merrill's strategy of moving to the reachable cell whose maximum distance to any other reachable cell is the shortest will beat the strategy of moving uniformly randomly (although in a crowded arena I don't believe this will be the best strategy so I still consider the question worth posting).

  • Should this be tagged ? I am expecting answers to make use of probability theory, but I can't know in advance what all the strategies will be. Is this close enough to use the tag?

  • I'm aiming for this to be a language agnostic challenge communicating with STDIN/STDOUT. Is there a language that is overdue to have its own language specific KotH contest, but that would still allow most users to participate? If not, I'll stick with language agnostic and include at least one example answer so that the processing of STDIN and STDOUT is provided in at least one language.

  • Method for deciding which attempted moves succeed. Is there any problem with this: Make a list of every intended destination (including own current cell for non-movers). For any destination that appears more than once, make all players aiming for that destination aim for their own current cell instead. Repeat (as this may have created more clashes) until no change is made. Move all the players to the resulting destination. Guaranteed to finish in N steps per turn for an N player game (worst case being a chain of players each moving to the next player's current cell, with the last player in the chain attempting to move onto a wall).

  • Pseudo random number source: Does anyone have a preferred/recommended random number generator? Is there any reason to consider a true random number source?

  • Alternative adversarial 2 player version: One player is the target, and the other player is seeking the target. Each player can move one square orthogonally or stay still. Walls are added as in the multiplayer game, and the game ends when the seeker moves onto the target's cell. The score of each player is the number of moves the game lasted. Lower score is better for the seeker player, higher score is better for the target player. The target can always see the location of the seeker. The seeker can never see the location of the target. Might also be interesting to allow both players to choose where to place a wall on their turn (in addition to moving). This might open up the possibility of double bluff. Walls would still be prevented from being placed on a cell that doesn't leave a path from seeker to target. Would this be more/less interesting than the multiplayer version? Are they sufficiently distinct to post as separate challenges, or should one be chosen as the one to be posted? Would this adversarial version work best as two KotHs that use each other's answers to judge their own answers (like a cops and robbers challenge) or should all the seeker answers and target answers be posted to one challenge? Alternatively each answer could be required to deal with being either a seeker or a target, but I like the idea of people being able to specialise and build just one or other, without being obliged to write both.

\$\endgroup\$
  • \$\begingroup\$ I believe the best strategy is to take all of the connected squares, and find the one that has the shortest walking distance to all other squares. Also, I think that walls should be placed every turn, as it appears to only slow down the game. \$\endgroup\$ – Nathan Merrill Jun 20 '15 at 0:18
  • \$\begingroup\$ Also, I believe an interesting variant would be to have it more like the cats/mice KotH, where several mice compete to stand on the square first, and the cat tries to delay them as long as possible. \$\endgroup\$ – Nathan Merrill Jun 20 '15 at 0:21
  • \$\begingroup\$ @NathanMerrill thanks for the feedback. When you say walls should be placed every turn, do you mean each time any player moves, or each time all N players have moved? \$\endgroup\$ – trichoplax Jun 20 '15 at 0:23
  • \$\begingroup\$ Each time all N players have moved, although I wouldn't be against the other either. \$\endgroup\$ – Nathan Merrill Jun 20 '15 at 0:24
  • \$\begingroup\$ Would the variant involve a cat that knows the position of the target? \$\endgroup\$ – trichoplax Jun 20 '15 at 0:24
  • \$\begingroup\$ Yes, it would (wouldn't be interesting otherwise, I think) \$\endgroup\$ – Nathan Merrill Jun 20 '15 at 0:25
  • \$\begingroup\$ @NathanMerrill my problem with adding the wall at the same point each time, after N players have moved, is that this means the players at the start of the cycle get first choice about where to move, which becomes more relevant in the later stages of the game. \$\endgroup\$ – trichoplax Jun 20 '15 at 0:26
  • 1
    \$\begingroup\$ Then I would add a wall after N+1 players have taken a turn, or rotate the player's turns \$\endgroup\$ – Nathan Merrill Jun 20 '15 at 0:26
  • \$\begingroup\$ That's an interesting idea - I'll consider changing it to that (N + 1 turns between walls) \$\endgroup\$ – trichoplax Jun 20 '15 at 0:27
  • \$\begingroup\$ I'm not against several moves per player between walls though. I've chosen the arena small enough to allow a large number of moves in total, and the cell a player wishes to be on may be several cells away from the current cell, so I don't feel a strong need to add walls at high frequency. \$\endgroup\$ – trichoplax Jun 20 '15 at 0:30
  • \$\begingroup\$ Moving to the center of the arena may well be worse than a uniformly random strategy ;) There's definitely one better than random though. \$\endgroup\$ – feersum Jun 20 '15 at 10:01
  • \$\begingroup\$ Question: will player bots have information storage? That is, will a player be able to remember every wall that has been placed? \$\endgroup\$ – Draco18s Jul 29 '17 at 1:30
  • \$\begingroup\$ @Draco18s yes the players will persist between moves, and can store information. I may place an upper limit on the amount of storage, but if I do it will be very generous. \$\endgroup\$ – trichoplax Jul 29 '17 at 1:36
  • \$\begingroup\$ In which case, moving randomly is not the best strategy :) \$\endgroup\$ – Draco18s Jul 29 '17 at 1:38
  • \$\begingroup\$ No, I'm thinking not, especially as a player can track what all of the other players are doing (they are distinguishable from each other, not just generic "enemy", but "player 1", "player 2", ...) \$\endgroup\$ – trichoplax Jul 29 '17 at 1:39
3
\$\begingroup\$

Number rewinder

Inspired by this SO question and little bit expanded.

Your task is to rotate left a given integer by one digit in a given base and return integer (move the MSD to the LSD position).

Input: Two integers Number > Base > 1
Output: Result

Test cases:

Number Base  Result  String representations
61453   10    14536  61453 -> 14536
61453   16      223  F00D -> DF (00DF)
61453    8   229481  170015 -> 700151
60429   16    49374  EC0D -> C0DE
62977   16    24607  F601 -> 601F

This is Code-golf, standard loopholes are forbidden and shortest answer wins.

\$\endgroup\$
  • 3
    \$\begingroup\$ I don't think your restriction about strings is going to work out well, there's not really a way to verify strings aren't being used. In any case, string rotation isn't that much different from the arithmetic required to do this operation. Personally, I'd recommend just allowing them. Thanks for using the sandbox! \$\endgroup\$ – FryAmTheEggman Feb 5 '18 at 22:09
  • \$\begingroup\$ (i.e., we don't like do X without Y or unobservable behavior) \$\endgroup\$ – user202729 Feb 6 '18 at 5:45
  • \$\begingroup\$ @FryAmTheEggman If there isn't some ToString-like function that opperates on any base using strings may be more difficult than dealing with it numerically. \$\endgroup\$ – Crowley Feb 6 '18 at 8:12
  • 3
    \$\begingroup\$ I've never heard "rewind" used with this meaning before. I would call that operation "rotation left". \$\endgroup\$ – Peter Taylor Feb 6 '18 at 11:09
  • \$\begingroup\$ @PeterTaylor Thanks for suggestion. I've updated bounds for the inputs to avoid rotating 1 digit "number" \$\endgroup\$ – Crowley Feb 6 '18 at 16:04
3
\$\begingroup\$

How acceptable is it to base challenges off of pre-existing challenges? I saw the challenge for Your Own Pet Ascii Snake and had a thought about making the output look more 'snakelike' by printing the characters |,\,/,(,),_ instead of always using the + character.

Here's how it would work. You would get some positive, negative, and 0 numbers as input, and based on those numbers, the snake moves one row down and that many characters in that direction. So, for a snake like the ones in the previous problem, your array would be restricted to the numbers 0, 1, and -1.

Here are the rules to draw the snake, the characters you print are dependent on the spacing of the lines before and after it.

So, say your snake is at position n (in the previous problem, n=30 to start, in this one you need to figure out a number for n that will keep your entire snake on the screen),

if the input is 0 you print n-1 spaces and a |
if the input is +1 you print n spaces and a \
if the input is +2 you print n spaces and \_, +10 would be \_________ (9 _ and a backslash)
if the input is -1 you print n-2 spaces and /
if the input is -2 you print n-3 spaces and _/, -10 would be _________/

Here's an example snake based on this array [+4, -3, +1, -4, +2, -3, +2, +5, -4, -1, -2, 0, +4, -4]

                        |
                         \___
                          __/
                          \
                       ___/
                       \_
                      __/
                      \_
                        \____
                        ____/
                       /
                     _/
                    |
                     \___
                     ___/

I could also add optional 'curvy' rules that would include the '(' and ')' characters on direction changes to produce a snake like this, based on the same array above:

                         |
                         \___
                          ___)
                         (_
                       ____)
                      (__
                      ___)
                     (__
                        \____
                        _____)
                       /
                     _/
                    (
                     \___
                     ____)

note that for the curvy snake, 0s are handled differently depending on if there is a direction change in the rows above and below them, here there is a negative, 0, positive pattern, so we use a '(', if there were no direction change we'd use a |, and in the opposite pattern, a ')'

There are spaces to the left of my example snake because I didn't want to count out how many spaces I should leave exactly, I don't know whether it should be mandatory to cut out extra whitespace to the left, or whether to let people have as much or as little whitespace as they want, provided that their snake doesn't 'go off screen'

\$\endgroup\$
  • \$\begingroup\$ I don't think there's a problem determining the next line randomly. For example, my program could generate the numbers for all 30 lines and then go back and format the characters appropriately. However, I'm not sure that's different enough to warrant its own challenge. Your second idea, though, regarding taking +1/-1/0 as input, that has some merit as it's pretty radically different than the existing snake challenge. \$\endgroup\$ – AdmBorkBork Feb 23 '18 at 19:29
  • \$\begingroup\$ I'm far, far too tired for you to rely on my opinion alone but this looks sufficiently different enough from the 2 existing challenges to not be a dupe, once it's fleshed out a bit more. I'd suggest waiting a while before posting it, though, as people do get jaded of a barrage of similarly themed challenges. \$\endgroup\$ – Shaggy Feb 24 '18 at 21:26
3
\$\begingroup\$

The TI series of calculators. I've put a lot of hours in writing TI-BASIC programs. The single most tedious part was either scrolling through the program, or switching between alpha and numeric input.

For those unfamiliar, the entire Latin alphabet is overlaid on the existing keys alphabetically, and to type any of them (For variable names or assembly programming), you had to first press the ALPHA key, then your desired letter. Alternatively, you could press 2ND, A-LOCK and type in any number of letters, before pressing ALPHA again for numeric input.

Why am I saying all this? I want to write a code golf like challenge where scoring is done with this tediousness in mind, like switching between numbers/punctuation and letters carrying an extra penalty.

My original idea is that the source code of the submission would be converted to hexadecimal, and the number of transitions between alphas and numerics would be the "score," with a lower score being better.

How can/should I better refine this scoring system, and what sort of challenge should accompany it?

The Challenge

Implement a program or function, in the language of your choice, that takes a string of characters as input and outputs that string's "tediousness score."

How tediousness is scored:

  1. The string is converted into its hexadecimal representation. This is Unicode for languages that don't specify, but for a language like, say, Jelly, the Jelly codepage is used.
    "The quick brown fox jumps, over the lazy dog's back." in Unicode == 0x54686520717569636b2062726f776e20666f78206a756d70732c206f76657220746865206c617a7920646f672773206261636b2e
  2. Each switch between numbers and letters in the hexadecimal representation is counted.
    0x54686520717569636b2062726f776e20666f78206a...
    ..0 12 34 56 78 9...
  3. This is your tediousness score. For this example, it is 25.

Standard loopholes apply.

Should I change the tediousness score? How might I implement golf? I thought about adding/multiplying the two together, but it still seemed to be in favor of just plain golfing. I wanted to make golfing languages be a bit harder for a golfing challenge, since they really pack their character sets and there would be a high "tediousness score".

Is the challenge, as written, clear enough? Should I restrict or relax the I/O requirements?

\$\endgroup\$
  • 5
    \$\begingroup\$ I have found that challenges with novel scoring mechanisms work nicely if the task is to implement the score calculator itself, see e.g. this challenge. \$\endgroup\$ – Laikoni Mar 12 '18 at 8:24
  • 1
    \$\begingroup\$ Probably tedious×log(nbytes)? \$\endgroup\$ – user202729 Mar 13 '18 at 14:16
  • \$\begingroup\$ What about giving a list of integers (byte values), or restricting the input to printable ASCII? \$\endgroup\$ – user202729 Mar 13 '18 at 14:29
  • \$\begingroup\$ @user202729 Because I wanted entries to be scored by this method, and I didn't want to exclude esoteric golfing languages. I specifically want to include them, and make them hard to win with. \$\endgroup\$ – Orion Mar 14 '18 at 6:06
  • \$\begingroup\$ What about "the input is a byte string"? That way you don't need to worry about the encoding. \$\endgroup\$ – user202729 Mar 14 '18 at 8:19
3
\$\begingroup\$

Signed exponentiation


Let us define signed exponentiation of a base x to a power n as this procedure:

  1. Take the absolute value of x.
  2. Raise to the power of n.
  3. Re-apply the original sign of x.

Or, for a more mathematical (albeit slightly flawed) definition:

the absolute value of x, to the power of n - 1, times x

For this challenge, we will denote the signed exponentiation of x to a as x ' a. Some notes:

  • Unlike f(x) = xa, f(x) = x ' a is defined for negative x no matter the value of a.
  • The negative portion of the graph of x ' n is the positive portion rotated halfway about the origin; hence, f(x) = x ' a is an odd function for all values of a.
  • If a is odd, x ' a = xa for all values of x.
  • x ' 1 = x, while x ' -1 = 1 / x. x ' 0 is a sign function (+1 for positive x, -1 for negative x).

Challenge

Given a base x and a power n, compute x ' n.

Rules

  • You may assume that -9 ≤ x, n ≤ +9.
  • You may assume that x ≠ 0, for the sake of avoiding 0 ' 0, 0 ' -1, etc.
  • You may assume that 1e-4 ≤ |x ' n| ≤ 1e9.
  • The output must be precise to at least 3 significant digits for the given test cases.
  • Input/output may be taken/given in any standard format.

Test cases

x, n -> output
1, 0 -> 1
3.14159, 0 -> 1
-9, 0 -> -1
7, 1 -> 7
-1.23456, 1 -> -1.23456
5, 2 -> 25
-4, 3 -> -64
0.1, 4 -> 0.0001
-9, 9 -> -387420489
1, -1 -> 1
-3, -1 -> -0.33333
5, -2 -> 0.04
2.71828, -9 -> 0.0001234
4, 0.5 -> 2
-2, 0.5 -> -1.41421
2, -0.5 -> 0.7071
3.8236, -1.6702 -> 0.10645
0.1, -9 -> 1000000000

Scoring

This is , so the shortest code in bytes in each langauge wins.


Sandbox questions

  • Could the definition be improved?
  • Too many test cases? Are there any important ones missing?
  • Any issues with the rules?
\$\endgroup\$
  • \$\begingroup\$ This isn't a huge deal, but I find the "your answer must be accurate to x significant figures" to be a largely unobservable property. The only ways to know that a submission meets this criterium is to check each and every possible combination, or to give an incredibly complex proof. I've always thought it was better to say floating point errors don't matter and to use loopholes otherwise. Maybe just a small thing about having to be able to represent any of the numbers from 1e-4 to 1e9? \$\endgroup\$ – FryAmTheEggman Oct 2 '17 at 21:23
  • \$\begingroup\$ Thanks @FryAmTheEggman; I like your suggestion, but I'm afraid if it's not objective enough it'll cause any issues. Any suggestions on how to phrase it? \$\endgroup\$ – ETHproductions Oct 3 '17 at 21:38
  • \$\begingroup\$ Perhaps have a few special test cases where they have to match the first three sig figs, and put in a line that those can't be hard coded. Then otherwise floating point errors don't matter? I'm honestly unsure. I've been getting to the point where I want to ask on meta because it always feels like fp questions are unclear or unobservable. \$\endgroup\$ – FryAmTheEggman Oct 4 '17 at 16:38
  • \$\begingroup\$ @FryAmTheEggman Hopefully a little more objective now. \$\endgroup\$ – ETHproductions Feb 27 '18 at 1:54
  • \$\begingroup\$ I think this looks much better, but there are perhaps too many "mandatory" test cases? Maybe making a split will make it easier for people to check the validity of answers. \$\endgroup\$ – FryAmTheEggman Feb 27 '18 at 6:04
  • \$\begingroup\$ Am I allowed to print more than 3 sigfigs? \$\endgroup\$ – Stephen Leppik Apr 6 '18 at 22:02
  • \$\begingroup\$ @StephenLeppik Of course. Should be slightly clarified now \$\endgroup\$ – ETHproductions Apr 7 '18 at 1:37
  • \$\begingroup\$ The way to prevent hardcoding is to have hidden test cases. \$\endgroup\$ – user202729 Apr 7 '18 at 11:15
  • \$\begingroup\$ @user202729 Not sure I understand. How could hard coding possibly be useful for this challenge? \$\endgroup\$ – ETHproductions Apr 7 '18 at 14:09
  • \$\begingroup\$ "for the given test cases". Although, yes, normally it is not useful. Whether you think it's necessary is up to you, but I doubt anyone would do it. \$\endgroup\$ – user202729 Apr 7 '18 at 14:32
3
\$\begingroup\$

Inversion languages

Cops

For this challenge you will design two languages, A and B. Both A and B should be Turing equivalent1. When run in your two languages a program has four options:

  1. It halts in both A and B.

  2. It halts in A but not B.

  3. It halts in B but not A.

  4. It doesn't halt in either A or B.

Your goal is to try to design A and B such that as many programs as possible halt in exactly one language (options 2 and 3). Doing such for all programs is impossible2, thus there will always be programs that meet either criterion 1 or criterion 4. The robbers will attempt to find these programs.

Further rules on languages

Since we are only considering whether programs halt or not we don't care about I/O. Because of this programs should not take any input. You may produce output but really doesn't matter because it can neither hurt nor help you.

All programs should be deterministic in both languages, this means that any program that can halt must always halt and any program that can run indefinitely must do so.

Answering

Your answer should contain the following information.

  1. A concrete description of both languages

  2. Proofs that each language as described is Turing complete.

Your definitions should be rigorous and unambiguous. Meaning that a reasonable person should (given enough time) be able to workout the result of any computation. This means all edge cases should be covered and there should be no undefined behavior.

Scoring

Your score will be the time between your post and the first crack with a higher score being better.

Robbers

Robbers will score 1 point for every answer that they crack, with a higher score being better.

Your answers should include the program which cracks the cop's answer and a proof that it does.

Sandbox

This is kind of just an idea right now. I have to iron out a lot of details and I will. I'll flesh it out later I just want to get it down so I don't forget it. Right now the most useful feedback would be in broad strokes. Don't worry about details, that's my job.


1: Turing equivalent is very similar to Turing completeness, but also stipulates that the language can be simulated by a Turing machine. Turing complete languages are not Turing equivalent if they are incomputable.

2: Suppose that we did have two Turing complete languages A and B such that every program halted in exactly one of the languages. We could solve the halting problem in language A by running a program in both A and B on separate threads until one of them halted, then outputting whether it was A or not.

\$\endgroup\$
  • 1
    \$\begingroup\$ +1, very nice idea. But "to maintain fairness, this challenge will only be open to submissions for one week after the first cop's answer is posted" doesn't make sense to me - it seems to make it less fair, by preventing anyone from competing who comes across the challenge late or just spends time on their submission. \$\endgroup\$ – Nathaniel Apr 3 '18 at 4:05
  • \$\begingroup\$ @Nathaniel The problem is that answers are scored based on how long they last answers that are late to the party have a huge advantage, since people won't be monitoring the challenge as much the older it gets. I would love to have a challenge that is open indefinitely, I strive to make that for all my challenges, so if anyone can think of a objective winning criterion that allows for this I'm all ears. \$\endgroup\$ – Sriotchilism O'Zaic Apr 3 '18 at 4:08
  • \$\begingroup\$ I see, hmm, that makes sense even if it's unsatisfying. Nothing comes to mind as an alternative scoring mechanism for this challenge for now. \$\endgroup\$ – Nathaniel Apr 3 '18 at 4:10
  • \$\begingroup\$ A separate point: I wonder if this might be a bit hard for the cops. Off the top of my head, I find it hard to think of a way to design two languages such that it wouldn't be obvious how to crack it. This might just be a failure of my imagination, however! \$\endgroup\$ – Nathaniel Apr 3 '18 at 4:12
  • \$\begingroup\$ What do you mean with input [a program] into your two languages? Is this about polyglots? If so, how would you consider programs which are syntax errors in one or both of the languages? \$\endgroup\$ – Leo Apr 3 '18 at 4:25
  • \$\begingroup\$ @Leo Input should probably be replaced with the verb "run". This is about polyglots. This is one of the things I plan on expanding on later on, but I'll either disallow syntax errors or consider them to be halting. \$\endgroup\$ – Sriotchilism O'Zaic Apr 3 '18 at 4:34
  • 2
    \$\begingroup\$ Maybe avoid encrypting? (If key doesn't match, A always halt and B never halt; you hve no key lol \$\endgroup\$ – l4m2 Apr 3 '18 at 5:23
  • \$\begingroup\$ but once known turing complete it's usually easily converted to an ans \$\endgroup\$ – l4m2 Apr 3 '18 at 5:25
  • \$\begingroup\$ Although languages A and B such that all programs halt in exactly one language is impossible, A and B such that can't find one is possible \$\endgroup\$ – l4m2 Apr 3 '18 at 7:24
  • 2
    \$\begingroup\$ With respect to @Nathaniel's observation about "only open for a week", it's certainly true that one of the problems of C'n'R is that the robbers get bored or don't notice late cop submissions, but it's not clear what "open to submissions" means. You're surely not thinking of asking the mods to lock the question, so you can't stop people posting new submissions. Perhaps that would be better rephrased in terms of when you will award the "accepted answer". \$\endgroup\$ – Peter Taylor Apr 3 '18 at 8:47
  • \$\begingroup\$ The issue of testability is also a big one. If B is something along the lines of "Run the program through A for N steps. If it terminates, enter an infinite loop. Otherwise take the parts which are comments in language A and run them." Tune N so that it takes about a week to get any program to terminate in B. \$\endgroup\$ – Peter Taylor Apr 3 '18 at 8:52
  • \$\begingroup\$ @l4m2 I would rather not ban encrypting because I consider it an unenforcable restriction. As you pointed out proving an answer to be Turing complete becomes a large hurdle for cops to overcome if they choose to cryptography. For example it is unknown whether Malbodge Unshackled is TC. \$\endgroup\$ – Sriotchilism O'Zaic Apr 3 '18 at 17:00
  • 1
    \$\begingroup\$ @tsh The problem with bubblegum or similar languages is that crypto functions are designed to be really hard to predict. This makes it hard to say anything concrete about their behavior, which in turn makes any language that uses them in a non-trivial manner, really hard to prove TC. TCness means it is possible to write a program for every Turing machine, and since it is almost impossible to write a program in the language it is hard to show that every program can be written. I would recommend trying to come up with a language pair that has these properties. You might run into some issues. \$\endgroup\$ – Sriotchilism O'Zaic Apr 8 '18 at 16:05
  • 1
    \$\begingroup\$ @tsh There is no such thing as undefined behavior. \$\endgroup\$ – Sriotchilism O'Zaic Apr 9 '18 at 2:30
  • 1
    \$\begingroup\$ Another couple of related questions: (1) to what extent does the interpreter have to meet the spec? Obviously it can't meet it completely, since the interpreter runs on a finite machine with finite addressing, and therefore can't technically be Turing complete. What about cases like integer overflow? (2) How would you handle bugs in the interpreter, and/or ambiguities in the spec? \$\endgroup\$ – Nathaniel Apr 9 '18 at 3:57
3
\$\begingroup\$

Really skirting bit of sandboxing here (I haven't taken the time to develop the question):

I'd like to do a 2-d variant of this one.

Two lasers between two mirrors

The input would be an ascii maze, with a marker for the laser starting point, e.g.:

+---+------+
|*  |      |
|   |      |
|   |  ----+
|   |      |
|   |      |
|   |      |
|   +---   |
|          |
|          |
|          |
+----------+
  • Astrisk(*): laser starting point.
  • Whitespace: passable.
  • Any other character is a reflective obstacle.

Result:

+---+------+
|\  |   /\ |
| \ |  /  \|
|  \| /----+
|  /|/   /\|
| / |\  / /|
|/  | \/ / |
|\  +---/  |
| \    /   |
|  \  /    |
|   \/     |
+----------+

Rules:

  • When you can't move horizontally, reverse horizontal direction.
  • When you can't move vertically, reverse vertical direction.
  • Stop going when you meet the same laser coming the other way (e.g. when you hit a corner or reach your starting position again).I'm thinking of a golfing challenge.
  • If the laser revisits a space in the other direction, draw an upper case X.

Simplifying factors:

  • Let's just say the laser always goes the same way.
  • The map is always a rectangle.
  • Just the one laser.

It'll probably just be a golfing challenge.

\$\endgroup\$
  • 1
    \$\begingroup\$ What's the goal of the program, just to draw the path? Food for thought, if you wanted a related but different challenge you could include a "start" and "goal" marker, and make the program determine if the laser ever hits the goal, returning "true" or "false" instead of a drawn maze. Or perhaps it should return how many steps it takes to hit the goal, returning either an integer, or a falsy value if it never hits it? Up to you, but some ideas. \$\endgroup\$ – BradC Apr 11 '18 at 16:34
  • 3
    \$\begingroup\$ Consider removing the outside wall. You say that the laser always goes in the same direction, but I think that you should explicitly say that it always starts heading south-east (or down-right). Important test cases: All of the walls aren't connected to the border. Laser hits a 1-length wall. Laser crosses itself. Laser hits a + (on the inside). Laser barely misses a +. Laser starts next a right wall. Laser starts next to bottom wall. Laser starts at a bottom-right corner. \$\endgroup\$ – Nathan Merrill Apr 11 '18 at 17:08
3
\$\begingroup\$

X1M4L got in before me and posted the very similar challenge Print the previous answer!, which I don't mind at all. However, that one seems to have turned out quite a lot more open-ended than this version would be, with answers tending to score in the tens of thousands. So after a sufficiently long delay this will probably not be considered a duplicate - I intend to leave it in the sandbox for at least a few months before posting.

Compress the previous answer

This is an challenge. The first answer must output the empty string. The second answer must output the source code of the first answer, and so on, with each answer outputting the code of the previous one.

To make this challenging, no answer may be longer than 100 bytes in length. Once the answers start getting close to this limit, it will become necessary to compress the text of the previous answers, which itself will become harder over time.

Each answer should output the exact string of bytes that forms the previous program. Because of this, if your program is in any format other than plain ASCII, you should post a hexdump as well as the source, so that the next person knows exactly what to output.

An answer's score is its position in the chain, i.e. the Nth answer scores N points. Your score is the score of your highest-scoring answer. You are encouraged to treat this challenge cooperatively, keeping the chain going as long as possible by not adding extra unnecessary entropy to your code.

The code of your answer cannot be identical to the code of any previous answer. The first answer must be at least one byte in length.

You may not post two consecutive answers. There are no restrictions on language.

tags:

\$\endgroup\$
  • \$\begingroup\$ that's so weird, I was thinking of this the other day, after seeing all those quine/answer chaining challenges. \$\endgroup\$ – geokavel Mar 21 '18 at 16:13
  • 1
    \$\begingroup\$ You'd probably need to provide some non-empty seed, to prevent the answers from all being blank themselves. Also, would there be any restrictions on language choice - e.g. would each answer need to be in a different language than all those that came before? \$\endgroup\$ – Sok Mar 21 '18 at 16:29
  • \$\begingroup\$ @user56656 just position in the chain - I've added it \$\endgroup\$ – Nathaniel Mar 22 '18 at 0:30
  • \$\begingroup\$ @Sok I've fixed the "all programs empty" issue by requiring each entry to be different from the previous one. I tend towards not putting restrictions on language choice (I've added that for now) but if there's a good argument for including such restrictions I'm open minded. \$\endgroup\$ – Nathaniel Mar 22 '18 at 0:31
  • \$\begingroup\$ You should probably prevent source reading. A pretty good strategy will to be to make a valid submission in language A that is also a period 2 quine in language B. Alternatively, you might want to impose the restriction that new answers are different from every previous answer instead of just the last one. \$\endgroup\$ – Sriotchilism O'Zaic Mar 22 '18 at 0:33
  • \$\begingroup\$ Another consideration is whether consecutive answers should be permitted. It is pretty common to put restrictions on individual answerers, to prevent schemes designed to game the system. \$\endgroup\$ – Sriotchilism O'Zaic Mar 22 '18 at 0:35
  • \$\begingroup\$ @user56656 I've implemented your idea about making them distinct from all previous answers, and I've banned consecutive answers by the same person. Does that cover all the bases? \$\endgroup\$ – Nathaniel Mar 22 '18 at 0:38
  • \$\begingroup\$ I've also changed the length restriction to 100 (makes a shorter challenge, but the restriction will kick in sooner) \$\endgroup\$ – Nathaniel Mar 22 '18 at 0:39
  • 1
    \$\begingroup\$ It might be prudent to try a test drive of the challenge (in chat) to test if the 100 byte limit is good. I'd be willing to help with that. Other than that I have no further thoughts at this time. \$\endgroup\$ – Sriotchilism O'Zaic Mar 22 '18 at 0:43
  • \$\begingroup\$ @user56656 that makes sense - I'll try that when I have a chance (might be in a week or two). \$\endgroup\$ – Nathaniel Mar 22 '18 at 5:40
  • \$\begingroup\$ I think you probably gain more from saying languages cannot be repeated (and including a stack snipped of used languages) than you do by adding a lot of workarounds for quines. I think it will cause the answers to become more interesting more quickly. It will also result in the challenge ending sooner, but given how the hello world answer chaining question went, I don't think you have too much to worry about with respect to longevity (though increasing the 100 may be a good idea if you decide to do this). \$\endgroup\$ – FryAmTheEggman Mar 22 '18 at 18:00
  • 1
    \$\begingroup\$ @FryAmTheEggman I don't think quines will be a problem in any case, because the Nth answer has to output a program that outputs a program that ... that outputs the empty string, so by definition it can't be a quine. That could be got around with polyglots, but I'd be very surprised if it would be an issue in practice - the criterion of not being identical to a previous answer is there to prevent quines not only in practice but also in theory! \$\endgroup\$ – Nathaniel Mar 23 '18 at 0:59
  • \$\begingroup\$ The problem that I see is that if languages are repeatable you might get a really boring and repetitive sequence of 3-4 languages that somewhat trivialise the problem appearing quickly after each more interesting answer. I perhaps should have said "trivial modifications of near-quines" instead? Anyway, this may not happen, but I think you should focus on this as well when doing the short test run (i.e. check what portion of answers can be trivially followed by a /// or Bubblegum program). \$\endgroup\$ – FryAmTheEggman Mar 23 '18 at 1:31
  • 1
    \$\begingroup\$ How about making the maximum length of answer n a slowly growing function over n? \$\endgroup\$ – Laikoni Mar 24 '18 at 10:43
  • \$\begingroup\$ @Laikoni that's an interesting idea. I guess probably logarithmic would be good choice. I'll give it some thought. \$\endgroup\$ – Nathaniel Mar 24 '18 at 14:11
3
\$\begingroup\$

Rebuild My Scrabble Board

My daughter and I have an ongoing Scrabble tournament. We enjoy admiring the board at the end of a game. But recently we knocked over the board and didn't get a chance to get a good look or take a picture. Fortunately, we kept track of all our moves. Your challenge is to take the list of moves and use it to rebuild the Scrabble board.

Input

Each move includes 4 pieces of information

  1. Column - A - O, like the column label of a typical spreadsheet. Upper or lower case is OK, but you only need to support one or the other.
  2. Row - 1 - 15, like the row label of a typical spreadsheet. 0-indexed 0 - 14 is acceptable.
  3. Orientation - H=Horizontal, V=Vertical - Upper or lower case is OK, or you may choose any other 2 printable ASCII characters.
  4. Tiles - A - Z plus @ for blank. Upper or lower case is OK, but you only need to support one or the other. You can use a different printable ASCII character for blank if you prefer, but not the space character or a period. The tiles for a move may be a string or a list of characters - e.g., CAT or (C,A,T).

Input format may be a tuple, list, separate lines (4 per move) or any other reasonable format. Column + Row may be combined, spreadsheet-style (e.g., A1, O15), but the orientation and tiles must be separate fields. Column can't be numeric - that is easy for the computer but in the middle of a game we have enough to keep track of, so remembering which # is Row and which # is Column would be too confusing - spreadsheet notation is easy to remember.

Output

The completed Scrabble board is to be printed in a format similar to Draw an Empty Scrabble Board. However, the double/triple squares are not printed and the moves are, obviously, included. Specifically:

  • 15x15 matrix
  • Unused spaces display as a period .
  • No leading spaces allowed.
  • Trailing spaces allowed.
  • One line feed at the end of each row.
  • Up to one leading and one trailing line feed permitted.
  • Blank tiles are to be output using the same character as input (default @).

Rules

Each move is placed starting with the first tile in the specified location. Each additional tile is to be placed in the next available location. In other words, your program must keep track of filled locations and skip them, just like a player placing tiles on the board.

What you don't need to worry about:

  1. Invalid words - if my daughter and I decided it was OK, you don't have to check it.
  2. Invalid locations - these are real moves, so there will of course be enough space to place all the tiles, and you don't have to double-check that a move starts on an empty space (but you can do that if it makes your algorithm shorter since you do have to check for all the other tiles in each move).
  3. Proper use of the standard Scrabble set of tiles - e.g., you don't have to check that there are only 2 blanks, 1 Z, etc.

Examples

[Sandbox note: Plan to include a couple of complete games plus a few shorter examples to highlight particular issues]

Input:

(G,8,H,CAT)
(G,9,V,OMPUTE)
(F,9,H,RB)
(H,7,H,TIME)
(I,6,V,BE)

Output:

...............
...............
...............
...............
...............
........B......
.......TIME....
......CAT......
.....ROBE......
......M........
......P........
......U........
......T........
......E........
...............

Scoring

  • The input and output can be given by any convenient method.
  • Either a full program or a function are acceptable. If a function, you can return the output rather than printing it.
  • Standard loopholes are forbidden.
  • This is so all usual golfing rules apply, and the shortest code (in bytes) wins.
\$\endgroup\$
  • 3
    \$\begingroup\$ This is a very nice challenge! :-) A few suggestions/answers: yes, allow zero indexed values. I suggest that the input may optionally be numeric for both row and column, but that's up to you. You don't need to mention the next challenge. \$\endgroup\$ – Stewie Griffin Apr 22 '18 at 7:01
  • \$\begingroup\$ Should you include scrabble game rules too? \$\endgroup\$ – user202729 Apr 22 '18 at 13:12
  • \$\begingroup\$ @user202729 I am limiting the rules to those required for the challenge. There are plenty of rules (especially scoring, but also passing/trading letters and a lot of other stuff) that isn't relevant to this challenge. If this goes well and I make another challenge for scoring then I will include the relevant rules there. I believe I have enough information here that someone could produce functional code without understanding anything else about Scrabble. \$\endgroup\$ – manassehkatz Apr 22 '18 at 13:47
  • \$\begingroup\$ Suggest to allow other characters than . for empty board tiles. \$\endgroup\$ – JayCe Jun 11 '18 at 3:45
  • \$\begingroup\$ Are trailing new lines allowed? \$\endgroup\$ – JayCe Jun 11 '18 at 3:47
  • \$\begingroup\$ @JayCe ok for both. I need to finish this and turn it into an actual challenge \$\endgroup\$ – manassehkatz Jun 11 '18 at 3:53
  • 1
    \$\begingroup\$ It is a really nice challenge indeed :) \$\endgroup\$ – JayCe Jun 11 '18 at 3:55
3
\$\begingroup\$

Find the minimum set of letters to buy

Imagine that you own a board like this:

Black letter board

which lets you write any message that you want, given that you have the letters for the message. Given that you have a list of messages that you want to switch between, find the minimum number of each letter that you have to order with your board.

As an example, if your messages are Hello world and Hello aliens, you would need the letters Helloworldaiens, as both messages share the Hello part and the letter l in the second word.

For this challenge, input messages will only consist of letters a-zA-Z and space, however note that spaces are not included in the output as you don't need to buy them.

Input

Input consists of a list of strings, which all match [a-zA-Z ]+. There is no limit on the amount of messages that can be provided, or their length.

Output

Output consists of a string of a list of characters, where the letters in the output can be rearranged to create all the input messages, and is of minimal length. The output does not need to be sorted.

Examples
['Hello world', 'Hello aliens'] => Hadeeilllnoorsw
['foo', 'bar', 'baz'] => abfoorz
['Eat more tacos', 'Drink more tequila'] => DEaaceeiiklmnooqrrsttu
['Golfing is a fun activity', 'Code should be readable'] => CGaabbcdddeeeeffghiiiillnnoorsttuvy
['a', 'b', 'c', 'd', 'e', 'f', 'g'] => abcdefg

This would of course be a code-golf challenge

\$\endgroup\$
  • \$\begingroup\$ Hmm ... this is ringing a bell; I think we might have had it before but asking how many of each letter was needed. \$\endgroup\$ – Shaggy May 9 '18 at 21:50
  • \$\begingroup\$ I tried searching for similar questions, but I couldn't find anything. This question would also ask for how many of each letter is needed, but I guess the output format might be different. \$\endgroup\$ – maxb May 10 '18 at 6:14
  • 1
    \$\begingroup\$ It's this, isn't it? \$\endgroup\$ – Peter Taylor May 10 '18 at 10:53
  • \$\begingroup\$ Darn it, here I thought I had a good challenge going, but I guess the topic was too common. Thanks for the help! \$\endgroup\$ – maxb May 10 '18 at 10:55
3
\$\begingroup\$

Note: I'm putting this challenge on the back burner for a indefinite time in favor of the Hierarchies challenge. Go check that or the Formic Forest out if you're interested in a Formic sequel.


Formic Functions 3: Memory

This is a preliminary write-up of a new challenge heavily inspired by Formic Functions. The spec is based on the original challenge's spec - credits for most of what you'll read here to trichoplax.

Each player starts with one ant - a queen, who collects food. Each piece of food can be held or used to produce a worker. Workers also collect food to be brought back to the queen.

All players compete in one arena. The winner is the queen holding the most food after she has taken 8,000 10,000 [Thanks @Draco18s] turns. Ants can communicate by changing the colors of the arena squares (which can also be modified by rivals), as well as by storing messages for their peers.

The arena

The arena is a toroidal (edge wrapping) grid of hexagonal cells arranged in a rhombus of side length 1000. All cells start as color 1.

Initially exactly 1% 0.5% of cells will contain food. The 5000 pieces of food will be scattered uniformly randomly. No new food will be introduced during the game.

The queens will be placed randomly on empty cells, with no guarantee that they will not be adjacent to each other (although this is very unlikely).

Ant abilities

  • Sight: Each ant sees the 7 cells in its neighborhood. It has no knowledge of any other ants outside this neighborhood. It sees the contents of each of the 7 cells (other ants and food), and also each cell's color.
  • Memory: Each ant has access to a string as its memory. It is initially empty for the queen, and must be initialized by the queen when spawning a worker. For ways to change the memory after initialization, see Output below.
  • No orientation: An ant does not know where it is or which way it faces - it has no concept of North. The neighborhood will be presented to it at a randomly rotated orientation that changes each turn so it cannot even walk in a straight line unless it has colors to guide it. (Making the same move every turn will result in a random walk rather than a straight line.)
  • Moving, color marking, producing workers and transferring food: See Output below.
  • Immortality: These are highland ants that cannot die. You can confuse rival ants by changing the colors around them, or constrain them from moving by surrounding them with 6 ants of your own, but they cannot be harmed apart from this. [Should ants be able to die? If so, how?]
  • Carrying food: A worker can carry up to 1 piece of food. A queen can carry an arbitrary amount of food.

Coding

Provide a function body

Each ant is controlled by an ant function. Each turn the player's ant function is called separately for each ant (not just once per player, but once for the queen and once for each worker that player controls). Each turn, the ant function will receive its input and return a move for that particular ant.

Post an answer containing a code block showing the body of a JavaScript function, and it will be automatically included in the controller. The name of the player forms the title of the answer, in the form # PlayerName.

No access to outside data

Functions must be fully deterministic. When called with a given input, they must return the same output every time. A function must not access global variables and must not store state between turns in other ways than through the provided memory string. It may use built in functions that do not involve storing state or accessing data from the outside. For example, the use of Math.abs() is fine, but Date.getTime(), Math.random() must not be used.

An ant function may only use a pseudo random number generator that it supplies itself, that utilizes data provided through input. For example, it may implement its own pseudo RNG via its memory string, seeded by the environment (or statically).

A simple random strategy is still possible due to the random orientation of the input - an ant that always chooses the same direction will perform a random walk rather than a straight line path.

An ant function is permitted to contain further functions within its body.

Input and output

Input

The orientation of the input will be chosen at random for each ant and for each turn. The input will be rotated by 0, 60, 120, 180, 240 or 300 degrees, but will never be reflected.

Cells are numbered in this order:

 0 1
5 6 2
 4 3

The ant function will receive an array called view, containing an object for each of the 7 visible cells. Each object will have the following:

color: a number from 1 to 8
food: 0 or 1
ant: null if there is no ant on that cell, or otherwise an ant object

[Is 8 colors perhaps too many?]

If a cell contains an ant, the ant object will have the following:

food: 0 or more (maximum 1 for a worker)
queen: true or false
friend: true or false
memory: memory string when friendly, otherwise undefined

[Should ants be able to read rivals' memories? This would cause rampant edit wars. Rejected.]

The ant can determine its own details by looking at the ant in the central cell, view[6].ant. For example, view[6].ant.memory contains the memory of the executing ant.

Output

Output is returned as an object representing the action to take. This can have any of the following:

cell: a number from 0 to 6 (mandatory)
color: a number from 1 to 8 (optional)
spawn: a string (optional)
memory: a string (optional)

If color and spawn are omitted or non-truthy, then cell indicates the cell to move to.

If color is a number, the indicated cell is set to that number.

If spawn is a string, a worker ant is created on the indicated cell. The new worker will have its memory initialized to that string. The string cannot be longer than 256 characters. Only a queen can create a new worker, and only if she has food, as this costs one piece of food per worker.

If memory is a string, the executing ant will have its memory immediately changed to that string. The string cannot be longer than 65,536 characters for the queen, and 256 characters for workers. An ant may change its memory while also performing a different action - changing memory does not take a turn.

[Should changing own memory take a turn?]

[Should ants be able to send a message directly to another ant's inbox? For example, a message could look like this: {title:"help", content:view_array_of_sender}. An ant should also be able to perform an action while sending a message, otherwise the described behavior could be emulated.]

[Should ants be able to see the age of an ant? This behavior will often be emulated with memory. Is there a reason not to do that?]

[Is 65,536 characters a good number to pick for the max length of memory? Thanks to @Draco18s's and @dzaima's advice, workers now have significantly less memory than a queen.]

Example outputs:

{cell:0}: move to cell 0
{cell:5, memory:"abc"}: move to cell 5 and set own memory to "abc"
{cell:6}: move to cell 6 (that is, do nothing, as 6 is the central cell)
{cell:6, color:8}: set own cell to color 8
{cell:2, color:1, memory:"hey"}: set cell 2 to color 1 and set own memory to "hey"
{cell:1, spawn:"def", memory:"5252"}: create a worker with its memory initialized to "def" on cell 1 and set own memory to "5252"
{cell:3, color:0}: equivalent to just `{cell:3}` - move rather than set color
{cell:1, spawn:0}: equivalent to just `{cell:1}` - move rather than create worker
{cell:4, color:0, spawn:0}: move to cell 4 - color 0 and type 0 are ignored

Invalid outputs:

{cell:7}: cell must be from 0 to 6
{cell:0, color:9}: color must be from 1 to 8
{cell:0, spawn:true}: spawn must be a string
{cell:6, spawn:"254"}: cannot create a worker on a non-empty cell
{cell:0, color:1, spawn:"77"}: cannot set color and create worker in the same turn
{cell:3, memory:true}: cannot set memory to non-string
{cell:2, spawn:true}: cannot create a worker with a non-string memory
{cell:0, memory:long_string}: (if long_string is a string of length > 65536) cannot set memory to a string of length greater than 65536

[Missed any?]

An ant moving onto a cell containing food will automatically pick up the piece of food. If that ant is a laden worker, it will move onto the cell without picking up the piece of food.

An unladen worker trying to move onto an enemy queen with food will steal one piece of food from her instead. A laden worker trying to move onto an unladen friendly worker or a friendly queen will give its food to their target instead.

Turn order

Ants take turns in a set order. At the start of a game the queens are assigned a random order which does not change for the rest of the game. When a queen creates a worker, that worker is inserted into the turn order at the position before its queen. This means that all other ants belonging to all players will move exactly once before the new worker takes its first turn.

Limit on number of players

Obviously an unlimited number of players cannot fit into the arena. If there are more than 8 answers, only 8 of them will play in any one game.

[Good max number of players?]

Time limit per turn

Each time the ant function is called, it should return within 20 milliseconds. Since the time limit may be exceeded due to fluctuations outside the ant function's control, an average will be calculated. If at any point the average is above 20 milliseconds and the total time taken by that particular ant function across all calls so far is more than 10 seconds, the relevant player will be disqualified.

[Enough time?]

Disqualification

This means the player will not be eligible to win and their ant function will not be called again during that game. They will also not be included in any further games. If a player is disqualified on the tournament machine during a leaderboard game then it will be excluded from all future leaderboard games until edited.

A player will be disqualified for any of the following for any of its ants (queen or worker):

  • Exceeding the time limit as described.
  • Returning an invalid move as described under Output.
  • The cell to move to contains an ant and the case isn't defined under Output.
  • The cell to produce a worker on contains an ant.
  • A worker is trying to produce a worker.

[Did I miss any?]

It may seem harsh to disqualify for invalid moves, rather than simply interpreting this as no move. However, I believe that enforcing correct implementations will lead to more interesting strategies over time. This is not intended to be an additional challenge, so a clear reason will be displayed when a player is disqualified, with the specific input and output alongside to aid in fixing the code.

Multiple answers and editing

You may provide multiple answers, provided that they do not team up against the others. Provided each answer is working solely towards its own victory, you are permitted to tailor your strategy to take advantage of weaknesses in specific other strategies, including changing the color of the cells to confuse or manipulate them. Bear in mind that as more answers come in, the likelihood of meeting any particular player in a given game will diminish.

You may also edit your answers whenever you choose. It is up to you whether you post a new answer or edit an existing one. Provided the game is not flooded with many near-identical variations, there should be no problem.

If you make a variation of another person's answer, please remember to give them credit by linking to their answer from yours.

Scoring

At the end of each game, a player's score is the number of other players who have less food carried by their queen. Food carried by workers is not counted. This score is added to the leaderboard, which is displayed in order of average score per game.

Joint places indicate that the order of players is not yet consistent between 6 subsets of the games played so far. The list of games is split into 6 subsets because this is the minimum number that will give a probability of less than 5% that a given pair of players will be assigned distinct places in the wrong order.

[Scoring mechanism subject to change.]

[New feature/modification recommendations are very welcome! I want this challenge to be as different from the original Formic as possible, while keeping its spirit.]

\$\endgroup\$
  • 2
    \$\begingroup\$ 8000 turns is too few, 65k of memory is way too much. \$\endgroup\$ – Draco18s Mar 7 '18 at 22:12
  • \$\begingroup\$ I feel like the food density being so high is compensation enough for 8k moves. This was also chosen out of speed concerns - no caching like the previous Formic. 65k memory was designed as a "use all you want". I wanted to allow doing some crazy stuff, like storing large portions of the map. After some consideration, however, limiting this to for example 1k could be a good idea. \$\endgroup\$ – Alion Mar 7 '18 at 22:21
  • 1
    \$\begingroup\$ One thing that might make this challenge stand out would be if food "respawns" over time. That is, every N turns Y food is added to the board. Also, I still don't like the hex layout for the reasons dzaima pointed out in chat. \$\endgroup\$ – Draco18s Mar 8 '18 at 0:38
  • \$\begingroup\$ That would encourage periodically re-searching parts of the board for more complex entries... It would be simple to do, considering you have a lot of memory, but... Isn't this just complexity tacked on for the sake of complexity? Hmm, I'm not sure how I feel about this. \$\endgroup\$ – Alion Mar 8 '18 at 9:17
  • 1
    \$\begingroup\$ I'd suggest that the queen has the 65k memory but the workers - maybe ~500. Also do consider that each character is (IIRC) 2 bytes as JS uses UTF-16 \$\endgroup\$ – dzaima Mar 8 '18 at 9:21
  • \$\begingroup\$ I was just thinking about more memory for the queen. Great idea! \$\endgroup\$ – Alion Mar 8 '18 at 9:22
  • 3
    \$\begingroup\$ Saying that a "grid of hexagonal cells" is "toroidal" and has a specific "height" and "width" is somewhat ambiguous. I think I understand now, but it bears some more detailed explanation. \$\endgroup\$ – Kamil Drakari Mar 8 '18 at 15:42
  • \$\begingroup\$ Oh, good point. I thought it was obvious enough. I'll find a way to explain it better. \$\endgroup\$ – Alion Mar 8 '18 at 16:41
  • \$\begingroup\$ @KamilDrakari Is it clear enough now? \$\endgroup\$ – Alion Mar 21 '18 at 16:48
3
\$\begingroup\$

How many times was the function called?

Inspired by this question.

Using your language of choice, write a function that takes no argument and returns the number of times it was called.

Specifics:

Your language needs to support something callable (multiple times) that takes no argument (or an empty unused argument) and returns a number or a string representing the number of times it was called, for example 1, 1.0 or "1". Standard I/O applies.

Samples:

f() returns 1
f();f() returns 1 2
f();f();f();f() returns 1 2 3 4

Note that f(f(f(f()))) (function composition with itself) is not in the scope of this challenge.

As this is code-golf, the winning solution in any language is the one that uses the fewest number of bytes in this language.

\$\endgroup\$
  • \$\begingroup\$ My first question ever - interested to know if is this too trivial or a duplicate. I am aware that a function-oriented challenge restricts the number of languages sadly. related but not a dupe of this one \$\endgroup\$ – JayCe Jun 9 '18 at 13:55
  • \$\begingroup\$ Can we use a program instead of a function? \$\endgroup\$ – user202729 Jun 10 '18 at 3:06
  • \$\begingroup\$ @user202729 I am just not sure how to state it with a program... \$\endgroup\$ – JayCe Jun 10 '18 at 3:22
  • \$\begingroup\$ Make the program take no input and output number of times it's called. (require file I/O or something) \$\endgroup\$ – user202729 Jun 10 '18 at 3:23
  • 1
    \$\begingroup\$ I'm left feeling like I have seen a question for a function which gives a different output each time it is run but I can't seem to find it. \$\endgroup\$ – fəˈnɛtɪk Jun 11 '18 at 22:20
  • \$\begingroup\$ @fəˈnɛtɪk maybe this ? \$\endgroup\$ – JayCe Jun 11 '18 at 23:29
  • \$\begingroup\$ @fəˈnɛtɪk or this one maybe \$\endgroup\$ – JayCe Jun 11 '18 at 23:36
  • \$\begingroup\$ How may we store the state between calls? Self-modifying code? File? Global variable? \$\endgroup\$ – Adám Jun 12 '18 at 9:26
  • 1
    \$\begingroup\$ So this is the one I thought it was a duplicate of \$\endgroup\$ – fəˈnɛtɪk Jun 24 '18 at 13:38
  • \$\begingroup\$ @fəˈnɛtɪk thanks i will take a look at this one and related questions. \$\endgroup\$ – JayCe Jun 24 '18 at 19:45
3
\$\begingroup\$

Mixed alphanumeric sort

Can't decide if you want to sort by letter or by number? Just do both!

Create a program that, given a series of strings composed of the characters _, 0-9, and a-z, sorts them and returns them in order.


Sorting is done according to the following algorithm:

  • A token is any character among _a-z or a contiguous series of numerals
  • The empty string is sorted first
  • Single token strings are sorted as follows:
    • _ is sorted before numbers, and numbers are sorted before letters
    • Numbers are sorted in numeric order, and letters are sorted from A to Z
    • If two numbers have the same value, the shorter one is sorted first
  • Multi token strings are sorted according to the first token. If the first token is the same, then use the second, then third, etc.

Here is an example of a sorted list. You can use newlines, commas, or whatever else to separate the items, or you can just use a standard array type.

_first
5
5x
5y
123
0123
124
ab_
ab5
ab10
abc
abc
abc00b
abc000a

Rules

  • Input list can contain empty strings, but is always at least 1 element long
  • Input and output may be a list, or a string with separator characters of choice
  • Output can also be in-place (modifying the input list), as long as the changes are readable from outside the program
  • You can choose to process uppercase characters instead of lowercase ones
  • Standard loopholes apply
  • Lowest byte count wins

Sandbox questions

  • Is the description clear enough, or could anything be added to it?
  • It turns out this is a near duplicate of this one, but with the addition of a character that must be sorted before numbers, which changes the strategy. Is this different enough to be its own question?
\$\endgroup\$
3
\$\begingroup\$

Diagonalize a Blackbox

todo: test cases

more math explaination?

better challenge definition?

The function \$f(x_1,x_2,x_3)=(3x_1,x_1+2x_2,x_1+x_2+x_3)\$ is a linear transformation on \$\mathbb{R}^3\to\mathbb{R}^3\$. We can prove this, because like all linear transformations, it satisfies:

  • \$f(x_1+y_1,x_2+y_2,x_3+y_3)=f(x_1,x_2,x_3)+f(y_1,y_2,y_3)\$
  • \$f(\alpha x_1,\alpha x_2,\alpha x_3)=\alpha f(x_1,x_2,x_3)\$

Or, more compactly:

  • \$f(\alpha x+\beta y) = \alpha f(x)+\beta f(y)\$

All linear transformations like this can be represented by a matrix multiplication, such as:

$$ M = [f(x)] = \begin{bmatrix} 3 & 0 & 0 \\ 1 & 2 & 0 \\ 1 & 1 & 1 \end{bmatrix} \begin{pmatrix} x_1 \\ x_2 \\ x_3 \end{pmatrix} = (x_1,x_1+x_2,x_1+x_2+x_3) $$ One way to find this matrix is by feeding each of the members of the standard basis for \$\mathbb{R}^3\$, which is \$B = \{(1,0,0),(0,1,0),(0,0,1)\}\$, into \$f(x)\$ to get the columns. This can be for any linear transformation and any basis to get a matrix which represents the transformation in that basis.

For some linear transformations, there is a basis \$B'\$ in which \$M'\$ is diagonal - this requires that \$M\$ in \$B\$ be diagonalizable which requires it have unique eigenvalues. However, in this challenge all transformations you have to deal with will fulfill these requirements.

Continuing with the same example, we can determine the eigenvalues of \$M\$ by finding solutions to \$|M-\lambda I_3|=0\$, and the eigenvectors by solving \$Mv=\lambda v\$ for each \$\lambda\$:

$$ |M-\lambda I_3| = (3-\lambda) \begin{vmatrix} 2 - \lambda & 0 \\ 1 & 1 - \lambda \end{vmatrix} = (3-\lambda)(-(2-\lambda)(1-\lambda))\\ (\lambda-3)(-(2-\lambda)(1-\lambda)) = 0 \implies \lambda_1,\lambda_2,\lambda_3 = 3,2,1$$ This gives us a diagonal matrix \$M' = \begin{bmatrix}3&0&0\\0&2&0\\0&0&1\end{bmatrix}\$ $$ \begin{bmatrix} 3 & 0 & 0 \\ 1 & 2 & 0 \\ 1 & 1 & 1 \end{bmatrix}\begin{pmatrix} a\\b\\c \end{pmatrix} = \begin{pmatrix}3a\\a+2b\\a+b+c\end{pmatrix}\\ \lambda_1\begin{pmatrix}a\\b\\c\end{pmatrix}=\begin{pmatrix}3a\\3b\\3c\end{pmatrix}=\begin{pmatrix}3a\\a+2b\\a+b+c\end{pmatrix}\implies v_1=(1,1,1)\\ \lambda_2\begin{pmatrix}a\\b\\c\end{pmatrix}=\begin{pmatrix}2a\\2b\\2c\end{pmatrix}=\begin{pmatrix}3a\\a+2b\\a+b+c\end{pmatrix}\implies v_2=(0,1,1)\\ \lambda_3\begin{pmatrix}a\\b\\c\end{pmatrix}=\begin{pmatrix}a\\b\\c\end{pmatrix}=\begin{pmatrix}3a\\a+2b\\a+b+c\end{pmatrix}\implies v_3=(0,0,1) $$ This gives us a basis \$B'=\{(1,1,1),(0,1,1),(0,0,1)\}\$ where the matrix \$M'\$ represents \$f(x)\$.

In this basis, a vector that would be \$(5,6,7)\$ in \$B\$ is instead \$(5,1,1)\$, as shown here: $$(5,1,1)_{B'} = 5(1,1,1)+1(0,1,1)+1(0,0,1) = (5,6,7)_B$$

This affects the transformation as well:

$$ \begin{bmatrix} 3&0&0\\ 1&2&0\\ 1&1&1 \end{bmatrix} \begin{pmatrix} 5\\6\\7 \end{pmatrix} =\begin{pmatrix} 15+0+0\\ 5+12+0\\ 5+6+7 \end{pmatrix} =(15,17,18)_B\\ \begin{bmatrix} 3&0&0\\ 0&2&0\\ 0&0&1 \end{bmatrix} \begin{pmatrix} 5\\1\\1 \end{pmatrix} =\begin{pmatrix} 15+0+0\\ 0+2+0\\ 0+0+1 \end{pmatrix} =(15,2,1)_{B'}\\ (15,2,1)_{B'}=15(1,1,1)+2(0,1,1)+1(0,0,1)=(15,17,18)_B $$

Caveats

Notice how when we were finding \$v_1\$ above we picked \$(1,1,1)\$ to simplify. Unfortunately \$v_1=(7,7,7)\$, \$v_2=(0,-3,-3)\$ (and infinitely many more) are also valid in this context.
To make every solution uniform, we normalize each of the vectors:

$$ v_1=\frac{(1,1,1)}{\sqrt{1^2+1^2+1^2}}=(\frac{1}{\sqrt{3}},\frac{1}{\sqrt{3}},\frac{1}{\sqrt{3}})\\ v_2=\frac{(0,1,1)}{\sqrt{1^2+1^2}}=(0,\frac{1}{\sqrt{2}},\frac{1}{\sqrt{2}})\\ v_3=\frac{(0,0,1)}{\sqrt{1^2}}=(0,0,1) $$

So we get a basis \$B'=\{(\frac{1}{\sqrt{3}},\frac{1}{\sqrt{3}},\frac{1}{\sqrt{3}}),(0,\frac{1}{\sqrt{2}},\frac{1}{\sqrt{2}}),(0,0,1)\}\$, which corresponds to:

$$(5,1,1)_{B'} = 5(\frac{1}{\sqrt{3}},\frac{1}{\sqrt{3}},\frac{1}{\sqrt{3}})+1(0,\frac{1}{\sqrt{2}},\frac{1}{\sqrt{2}})+1(0,0,1)\\ = (\frac{5}{\sqrt{3}},\frac{1}{\sqrt{2}}+\frac{5}{\sqrt{3}},1+\frac{1}{\sqrt{2}}+\frac{5}{\sqrt{3}})_B$$

Additionally, we also add a restriction so that the first non-zero element of each eigenvector must be positive, flipping the signs of the rest of the vector if it was initially negative.

The Challenge

Your task is to write a function or program which takes a black-box function or program and either:

  1. outputs a function or program which accepts arguments in a special basis \$B'\$ as described above, performs the transformation on them, and returns the result in the standard basis \$B\$

  2. outputs the result in \$B\$ directly and takes the secondary arguments in \$B'\$ itself

Input

You are given a function (via one of the standard IO methods applicable) taking a vector as input and returning another vector in the same form, as the same data type.

Alternatively, you can take a program (via the name of an executable in the current working directory, or a process ID) which takes a vector as input through one of the standard input methods for programs, and outputs a vector in a whitespace-separated string.
(The executable can be in a different language, so don't try to read it.)

The input and output vectors for this function or program are in \$\mathbb{R}^n\$ with basis \$B\$.
You are also given a number specifying the size of the lists to be used (\$n\$ in \$\mathbb{R}^n\$).

If you follow the second option you will additionally receive a vector in basis \$B'\$.

Output

Otherwise, output a function taking a vector as input and returning another vector, where the function you output uses the standard IO methods for your language. Your submission may output this function as a literal function, function pointer, or as source code for such a function in your language. Instead of a function, you may output a whole program as source code or compiled binary, which takes a vector as input and returns another vector via the standard IO methods for your language.

The input and output vectors for this function or program are in \$\mathbb{R}^n\$.
The input vectors have basis \$B'\$, and the output vectors have basis \$B\$.

If you follow the second option then the above statement applies to your submission instead of the output, and you do not need to output a function nor a program but instead the specified vector.

Criteria

As this is , the shortest code in bytes for each language, further subdivided by combination of function / program as input / submission / output, wins!

Test Cases

todo

Notes

While it's a bit math-y, there are multiple interesting routes to go for a solution to this:

  • Transform \$B'\to B\$ and pass to the input function or program
  • Follow the question closely and apply the transformation via \$M'\$
  • More I won't disclose
  • Probably more I haven't thought of
\$\endgroup\$
3
\$\begingroup\$

Double JSON

Input a JSON, double every values in it, and output.

Input

A String. It is guaranteed to be a valid[1] JSON.

Output

A String. It should be a valid JSON.

For each value in the inputed JSON:

  • If the value is number, double it
    • 42 -> 84
  • If the value is string, repeat it
    • "data" -> "datadata"
  • If the value is an array, double its items recursively, and repeat the array twice
    • [1,2,3] -> [2,4,6,2,4,6]
  • If the value is object, keep keys as is, double its values recursively
    • {"a":1} -> {"a":2}
  • If the value is not a type listed above, keep it as is

Test Cases

42 -> 84
-1 -> -2
"abc" -> "abcabc"
true -> true
null -> null
{} -> {}
[] -> []
{"abc":42} -> {"abc":84}
{"true":42,"42":true} -> {"true":84,"42":true}
{"length":1,"0":true} -> {"length":2,"0":true}
[false] -> [false,false]
[42] -> [84,84]
[[42,"abc"]] -> [[84,"abcabc",84,"abcabc"],[84,"abcabc",84,"abcabc"]]
[[[]]] -> [[[],[]],[[],[]]]
{"a":4,"b":[1,2,3],"c":{"a":5}} -> {"a":8,"b":[2,4,6,2,4,6],"c":{"a":10}}

Rules

  • This is code-golf.
  • Output JSON should be equivalent to the sample output
    • No missing / unnecessary / redundancy values allowed;
    • Order of keys in object does not matter. But order of items in an array does matter;
    • Whitespaces are allowed as long as the output is valid JSON;
    • Number may be represented in any valid format with in acceptable floating point errors (<1%);
  • To keep this challenge easy:
    • Strings and keys of objects in JSON may only contain printable ASCII;
    • Inputed numbers are always integers;
    • No need to worry about number overflow when double it;
    • No duplicate keys in Object; And your output should not contain duplicate keys either;
  • If you chose implementing a function, input / output should be a string instead of an object / a dictionary.
    • Because it is hard to define a proper data type for JSON across languages.

[1]: There are more than one JSON specifications. I don't think they could make anything here different. Just in case, you may chose any one as your like. And here we define a subset of your specification you need to handle:

  • JSON is a lightweight data-interchange format. A value in json may be one of the following types: number, string, boolean, null, object, array.
  • number: numbers are always decimal, in format /-?(0|[1-9][0-9]*)(\.[0-9]+)?([eE][-+]?[0-9]+)?/;
    • In this question, inputted number would always be integer in format /-?[1-9][0-9]*|0/;
  • string: Start and end with ", contain Unicode characters or escape sequences;
    • In this question, inputted string will only contain printable ASCII excluding " or \, without any escape sequence;
  • boolean: literally true or false;
  • null: literally null;
  • array: Starts with [, ends with ], contains zero or more values spited by ,;
  • object: A dictionary, starts with {, ends with }, contains zero or more key-value pairs. Keys are string, values are any valid JSON values. A : placed between each pair of key and value.
  • A valid json allow whitespaces characters between any tokens. But its guaranteed that input will only contain whitespace characters in string.
\$\endgroup\$
  • \$\begingroup\$ If the value is an object, should we keep the object as it is or go though the object properties as well? Example: {"a": 4, "b": [1, 2, 3], "c": {"a": 5}} => {"a": 8, "b": [1, 2, 3, 1, 2, 3], "c": {"a": 5}} or {"a": 8, "b": [1, 2, 3, 1, 2, 3], "c": {"a": 10}}? \$\endgroup\$ – Luis felipe De jesus Munoz Jul 23 '18 at 13:13
  • 1
    \$\begingroup\$ I like this challenge, but you're assuming everyone knows what JSON is down to the technical details, making the challenge not self-contained. I would explicitly define what the format of the input and the output might be right in the question itself. This isn't so hard - I believe the definition is recursive. That is also a better way to avoid the "more than one specification" problem than just saying "don't worry about it". \$\endgroup\$ – ngm Jul 23 '18 at 18:55
  • \$\begingroup\$ @LuisfelipeDejesusMunoz It should be {"a":8,"b":[2,4,6,2,4,6],"c":{"a":10}}. I would add it to testcase. \$\endgroup\$ – tsh Jul 24 '18 at 1:24
  • \$\begingroup\$ I agree with what ngm said, challenges should be self-contained especially in cases like this where possible ambiguity could arise. If not you should define what a JSON-specification is which is probably way more difficult. Also what happens with arrays of objects? \$\endgroup\$ – ბიმო Jul 26 '18 at 12:30
  • \$\begingroup\$ And a test-case with a string that contains a valid JSON-object which would be doubled should be added, eg. {"json": "{\"nine\":9}"} or something, or even {"json": "[1,2,3]" }. \$\endgroup\$ – ბიმო Jul 26 '18 at 12:33
  • \$\begingroup\$ (Just looking at the specs leads to many questions/test cases like the one about the array or a lot about numbers: 1e9, -1e9, 1.234, -1.234, 1e-18, 1E+10, 1.23E-8 etc.? What about floating-point precision issues? Other special test cases: [{}], {"true":"false"},"" or empty input) \$\endgroup\$ – ბიმო Jul 26 '18 at 12:43
  • \$\begingroup\$ @OMᗺ With the explanation in the question: Input numbers are always integers, so /-?[1-9]\d*|0/. But you are free to handle it as integer or float. If you handle it as float, output should in +-1%. Empty input is not a valid JSON. \$\endgroup\$ – tsh Jul 27 '18 at 1:13
3
\$\begingroup\$

Knight's tour


A knight's tour is a sequence of moves of a knight on a chessboard such that the knight visits every square only once. For those who are not aware of how knights in chess work, knights are capable of moving in an L shape:

knight's moves

Tours generally applies to a regular chessboard of size 8, however it can be calculated for other sizes. For example, for a chessboard of size 5, a possible knight's tour is:

5×5 knight's tour

To add more.

Challenge

Write a program/function that takes a grid size n and outputs the board of integers.

Specifications

  • Standard I/O rules apply.
  • Standard loopholes are forbidden.

    Possibly more specifications.

  • This challenge is not about finding the shortest approach in all languages, rather, it is about finding the shortest approach in each language.
  • Your code will be scored in bytes, usually in the encoding UTF-8, unless specified otherwise.
  • Built-in functions that compute this sequence are allowed but including a solution that doesn't rely on a built-in is encouraged.
  • Explanations, even for "practical" languages, are encouraged.

Test cases

Yet to come.

\$\endgroup\$
  • 4
    \$\begingroup\$ "Your code will be scored in bytes, usually in the encoding UTF-8, unless specified otherwise.": So a Jelly answer will need to specify "Jelly (Jelly codepage)" or else it needs to count bytes of a unicode encoded source? Why not leave it out and let the tag code-golf handle the rules. And instead of generating test-cases, you could just add a program that validates the result as there are a lot of possible answers . \$\endgroup\$ – ბიმო Sep 22 '18 at 14:19
  • \$\begingroup\$ What should be the output for n < 4? \$\endgroup\$ – lirtosiast Nov 21 '18 at 18:35
3
\$\begingroup\$

Classical construction golf: Wernick's list No. 47

Background

Compass-and-straightedge construction, a.k.a. classical construction, is the construction of lengths, angles, and other geometric figures using only an idealized ruler and compass. A ruler can only be used to draw a straight line passing through two given points; a compass can only be used to draw a circle with two given points (a center, and a point on the circle).

All compass and straightedge constructions consist of repeated application of five basic constructions using the points, lines and circles that have already been constructed. These are:

  • Creating the line through two existing points
  • Creating the circle through one point, with another point as the center
  • Creating the point which is the intersection of two existing, non-parallel lines
  • Creating the one or two points in the intersection of a line and a circle (if they intersect)
  • Creating the one or two points in the intersection of two circles (if they intersect).

Five basic constructions

In addition to these listed on Wikipedia, we have the sixth basic construction:

  • Creating an arbitrary point on the plane, possibly with a constraint:
    • On a line ("line" includes straight lines and circles)
    • Not on a line
    • On a closed or open part of a line, bounded by existing points on it
    • Inside a closed or open region, bounded by existing lines

In any geometric problem, we have an initial set of symbols (points and lines), an algorithm, and some results. From this perspective, geometry is equivalent to an axiomatic algebra, replacing its elements by symbols.

This is the basis of the new kind of : classical construction golf.

Challenge

Wernick's list is a collection of construction problems. The common objective is to recover the three vertices of a triangle, given three of its 16 characteristic points. They include:

  • \$A, B, C, O\$: three vertices and circumcenter,
  • \$M_a, M_b, M_c, G\$: the side midpoints and centroid,
  • \$H_a, H_b, H_c, H\$: three feet of altitudes and orthocenter,
  • \$T_a, T_b, T_c, I\$: three feet of internal angle bisectors and incenter.

Out of the 139 problems, some are solvable by construction, but some are not. The problem we'll tackle here is problem 47, where the given points are:

  • \$A\$: a vertex.
  • \$H_a\$: the foot of the altitude on side \$a\$; that is, the opposite side of the vertex \$A\$.
  • \$T_b\$: the foot of the bisector of angle \$B\$.

Given these three points, recover the other vertices \$B\$ and \$C\$.

enter image description here

Scoring & Winning criterion

Every usage of the six basic constructions (shown above) counts. For the line intersections, creating each point adds 1 score, e.g. if you need both intersections of two circles, you get 2 score from the step.

The solution with the lowest score wins.

Scoring example

Task: Construct the midpoint of two points \$A\$ and \$B\$.

Solution:

  • Draw circle \$C_1\$ with center \$A\$ going through \$B\$. (+1)
  • Draw circle \$C_2\$ with center \$B\$ going through \$A\$. (+1)
  • Draw two intersections \$X, Y\$ of two circles \$C_1\$ and \$C_2\$. (+2)
  • Draw line \$f\$ going through the two intersections. (+1)
  • Draw line \$g\$ going through the two given points. (+1)
  • Draw the intersection \$M\$ of \$f\$ and \$g\$. (+1)

The score of this construction is 7.

Example task

Tools

GeoGebra is a free online geometry tool. In addition to basic and advanced constructions, it has construction protocol feature which clearly shows the steps used to create the final image. For the above example task, the construction protocol looks like this:

Example construction protocol

Out of 9 steps in total, the points \$A\$ and \$B\$ are given, so we can confirm that seven steps are taken for this particular construction.

It also supports scripting (in GGBScript and JS) for those who want to view this challenge as or . Among many geometry commands, the Prove and ProveDetails commands may help you identify if a particular construction is indeed correct.

Notes

I'm using a relatively easy problem here, in order to see how this new challenge type is received. If it goes well, I'll propose some harder and open-ended problems later.


Meta

  • Is this actually on-topic on PPCG? I'm asking this since this is the first challenge of its kind. I'll assume on-topic unless someone says otherwise on this meta question.
  • Maybe we need to tweak the difficulty of the challenge at hand. Is it too easy or too hard? Any other suggestions? I picked Wernick's list because it's not something you may see on Euclidea or similar, and the optimal (or elegant) solutions for many of the problems are not yet known. I'll go for the task this time, and try to ramp up in subsequent challenges.
\$\endgroup\$
  • 2
    \$\begingroup\$ I think it would be a stretch to consider this on-topic: proofs in logic can be argued to be as good as programs by reference to the Curry-Howard correspondence, but I don't really see extending that to proofs in general. It might be more interesting to instead ask for a program which generates proofs and score by the length of the generated proofs (although since the linked paper talks about a 6000-line program to search for them, that may be outside the scope of a reasonable PPCG challenge). \$\endgroup\$ – Peter Taylor Jul 23 '18 at 11:35
  • \$\begingroup\$ On the difficulty of the given theorem: without much effort (5 minutes maximum) I have a solution scoring 16. It's certainly much easier than the existing proof-golf questions to get an answer, although I can believe that there may still be room to golf my solution. \$\endgroup\$ – Peter Taylor Jul 23 '18 at 11:38
  • \$\begingroup\$ (In fact I've spotted one unnecessary intersection, so 15). \$\endgroup\$ – Peter Taylor Jul 23 '18 at 11:49
  • \$\begingroup\$ Do you think this would be better here or on Puzzling? \$\endgroup\$ – user202729 Sep 30 '18 at 12:02
3
\$\begingroup\$

Making a Mountain out of a Molehill

\$\endgroup\$
  • \$\begingroup\$ I'm not clear where the molehills start and end. Based on the description I thought they'd just be /\ without any of the surroundings. \$\endgroup\$ – xnor Sep 28 '18 at 23:03
  • \$\begingroup\$ @xnor does the edit clarify it? \$\endgroup\$ – RamenChef Oct 1 '18 at 13:59
  • \$\begingroup\$ No, I'm still confused. Being flat counts as going down? Also, from the examples I take it that "down" is taken looking towards the mountain? And what if you have two molehills separated by a flat area, are both molehills considered to include that flat area? \$\endgroup\$ – xnor Oct 2 '18 at 0:03
  • \$\begingroup\$ @xnor no, being flat doesn't count as going down. Where did you get that notion? \$\endgroup\$ – RamenChef Oct 3 '18 at 11:45
3
\$\begingroup\$

Recognize the hardest context-free language


A context-free language is a class of strings that can be recognized by a pushdown automaton, or equivalently produced by a BNF grammar. In her 1973 paper, Sheila Greibach showed that there exists in some sense a "maximally complex" context-free language. In this challenge, your task is to recognize this language.

The language

The words of the language \$L\$ use the seven characters \$\mathtt{()[]ABC}\$. You may use any seven printable ASCII characters in their place, but we use these in the explanation and test cases. A string \$s\$ is in the language if:

  1. It can be broken into \$n\$ pieces: \$s = w_1 \mathtt{C} w_2 \mathtt{C} \cdots w_n \mathtt{C}\$ where the \$w_i\$ do not contain \$\mathtt{C}\$s.
  2. Each \$w_i\$ has a substring of the form \$\mathtt{B} x_i \mathtt{B}\$ where \$x_i\$ does not contain \$\mathtt{B}\$s.
  3. The concatenation \$x_1 x_2 \cdots x_n\$ has the form \$\mathtt{A} b\$, where \$b\$ is a balanced string over \$\mathtt{()[]}\$.

Note that each \$w_i\$ may have several substrings that begin and end with \$\mathtt{B}\$, but we require that the third condition holds for at least one choice of the \$x_i\$. Also, some of the \$x_i\$ may be empty.

Here is an example of a string in \$L\$ and an explantion for it:

]BA[]BA[](BCB[]BA]B()(BC]B][BB]BCB)BAAB))C
           C           C        C        C    Split by C
     BA[](B B[]B            BB   B)B          Find substring surrounded by B in each part
      A[](   []                   )           Their interiors give A + balanced string

Here is a BNF grammar for \$L\$: [TODO: verify that this is correct]

<L>        ::= <trash> "BB" <trash> "C" <L>
             | <trash> "BA" <balanced> "B" <trash> "C"
<balanced> ::= <skip-c> <balanced>
             | "(" <balanced> ")"
             | "[" <balanced> ")"
             | <balanced> <skip-cs> <balanced> <skip-cs>
<skip-cs>  ::= <skip-c> <skip-cs> | ""
<skip-c>   ::= "B" <trash> "C" <trash> "B"
<trash>    ::= <not-c> <trash> | ""
<not-c>    ::= "A" | "B" | "(" | ")" | "[" | "]"

The task

Your input is a non-empty string over the alphabet of \$L\$. As stated above, you may use any 7 printable ASCII characters. Your program/function shall do one of the following:

  • Output a truthy value if the input is in \$L\$, and a falsy value if not.
  • Output a consistent value if the input is in \$L\$, and a different consistent value if not.

The lowest byte count wins, and other standard rules apply.

Test cases

TODO

\$\endgroup\$
3
\$\begingroup\$

Number of Unit Squares Intersecting a Circle

https://i.stack.imgur.com/3KdLe.gif

(Credit to user202729 for the illustration)

OEIS sequence A234300 is defined thusly:

  • A radius range is either a single real number at which the circle centered at \$(0,0)\$ passes through some lattice point, or an interval between two such consecutive numbers.
  • The first radius range is the number \$0\$.
  • The \$n\$th term of the sequence is the number of unit squares on the upper right quadrant of the Cartesian grid whose interior contains some segment of the circle of radius \$r\$, where \$r\$ is in the \$n\$th radius range.

This table shows the radius range and corresponding sequence terms for the first 11 terms of the sequence.

Range       Term
0           0
(0,1)       1
1           1
(1,√2)      3
√2          2
(√2,2)      3
2           3
(2,√5)      5
√5          3
(√5,√8)     5
√8          4

Input

A positive integer n (or nonnegative for zero-indexed).

Output

Either the \$n\$th term of the sequence, or a list of the first \$n\$ terms. You may index from \$n=0\$ or \$n=1\$.

\$\endgroup\$
  • \$\begingroup\$ I made a picture. /// I still don't get why integral radius is important, that appears to be a special-case rather than a rule. \$\endgroup\$ – user202729 Dec 1 '18 at 3:31
  • \$\begingroup\$ @user202729 wow, what did you use to generate it? \$\endgroup\$ – lirtosiast Dec 1 '18 at 3:45
  • 1
    \$\begingroup\$ Logo (source code) \$\endgroup\$ – user202729 Dec 1 '18 at 4:14
  • \$\begingroup\$ I would be pedantic and qualify "on the Cartesian grid" as "in the upper-right quadrant of the Cartesian grid". \$\endgroup\$ – Peter Taylor Dec 1 '18 at 10:50
  • \$\begingroup\$ Surprisingly, this doesn't look like a dupe... \$\endgroup\$ – lirtosiast Dec 2 '18 at 21:19
3
\$\begingroup\$

Non-overlapping Matrix Sum

Given k arrays of length n, output the maximum sum possible using one element from each matrix such that no two elements are from the same position. It is guaranteed that k<=n.

Input

A nonempty list of nonempty arrays of integers.

Output

An integer that represents the maximum sum.

Examples

Input -> Output
[[1]] -> 1
[[1, 3], [1, 3]] -> 4
[[1, 4, 2], [5, 6, 1]] -> 9
[[-2, -21],[18, 2]] -> 0
[[1, 2, 3], [4, 5, 6], [7, 8, 9]] -> 15
[[1, 2, 3, 4], [5, 4, 3, 2], [6, 2, 7, 1]] -> 16
\$\endgroup\$
  • \$\begingroup\$ @lirtosiast I’m not quite sure what that means. \$\endgroup\$ – Quintec Dec 13 '18 at 18:59
  • \$\begingroup\$ @lirtosiast Sorry, still don't understand. If ((3,1),(4,1)) and ((5,9)(2,6)) are the arrays, the function should return 13, but it returns 20? \$\endgroup\$ – Quintec Dec 13 '18 at 20:01
  • \$\begingroup\$ I understand the challenge now. Test cases would definitely be useful. I would consider changing to a version with 1d vectors instead of matrices, as the matrix structure doesn't seem to add much. \$\endgroup\$ – lirtosiast Dec 13 '18 at 20:26
  • \$\begingroup\$ @lirtosiast Yeah, makes sense. This actually came up when thinking about programming AI for a game, which is why I wrote it as a matrix to start. I'll change it to 1d arrays \$\endgroup\$ – Quintec Dec 13 '18 at 21:52
3
\$\begingroup\$

Output Hello, World! ... sometimes

On PPCG, we typically do not allow programs to work only part of the time. That is, all programs must work with 100% probability unless otherwise stated.

This challenge is going to state otherwise. Your program must, with nonzero probability, output this exact string to STDOUT:

Hello, World!

However, a simple Hello, World! program will not do. Your program must also have nonzero probability to behave in any other way than outputting the above string. This could be printing another string, printing Hello, World! surrounded by junk text, outputting Hello, World! to STDERR instead of STDOUT, outputting nothing, crashing, etc. Your program may have many different behaviors than printing the desired string.

This is a , so the shortest program in bytes wins.

Example program

The following program in JavaScript is a valid submission. It will output Hello, World! half the time, and the other half of the time output a float >= 0.5.

const THRESHOLD = 0.5;
let randomFloat = Math.random();

let output;

if(randomFloat < THRESHOLD) {
    output = "Hello, World!";
}
else {
    output = randomFloat.toString();
}

console.log(output);

Try it online!

\$\endgroup\$
  • \$\begingroup\$ Good to have a catalog for IMO. \$\endgroup\$ – lirtosiast Dec 28 '18 at 3:38
  • \$\begingroup\$ Should there be a requirement that HW should be outputted with probability > 0.5 or some threshold? \$\endgroup\$ – user202729 Dec 28 '18 at 9:02
  • \$\begingroup\$ @user202729 Good idea. \$\endgroup\$ – Adám Dec 28 '18 at 12:06
  • \$\begingroup\$ I'm not sure how this would be different than codegolf.stackexchange.com/q/114520/42963 or codegolf.stackexchange.com/q/66922/42963 \$\endgroup\$ – AdmBorkBork Dec 28 '18 at 17:01
  • \$\begingroup\$ What's to stop me from outputting 13 random characters? There's a nonzero probability of that outputting "Hello, World!" \$\endgroup\$ – Beefster Dec 28 '18 at 19:25
  • \$\begingroup\$ @Beefster nothing, is there something wrong with that approach? \$\endgroup\$ – Conor O'Brien Dec 28 '18 at 21:29
  • \$\begingroup\$ @user202729 I don't see why enforcing a threshold is a good idea. \$\endgroup\$ – Conor O'Brien Dec 28 '18 at 21:29
  • \$\begingroup\$ @AdmBorkBork I'm not sure why they'd be considered the same as this challenge. \$\endgroup\$ – Conor O'Brien Dec 28 '18 at 21:31
  • 2
    \$\begingroup\$ Perhaps the requirement should be made that the desired output should appear more frequently than any other possible output. \$\endgroup\$ – Conor O'Brien Dec 28 '18 at 21:35
  • \$\begingroup\$ @ConorO'Brien That's another way (that way the challenge becomes strictly harder than HW for most languages) // About the threshold - depends on whether you want to avoid solutions that generate a random string. \$\endgroup\$ – user202729 Dec 29 '18 at 9:12
3
\$\begingroup\$

Universal Self-correcting Program

The idea here is to make a program that can tolerate errors in its own code, while still functioning correctly.

Since "error" is too broad, we will define it by a single bit flip. Of course, more tolerant versions, that could accept swapping any character with any other character would still be valid.

This program is universal in the sense that you can write any other self-correcting program (with the same tolerance) -- more on that later.

Importantly:

1) This program takes as input a triple-redundancy string of characters, and outputs a corrected string.

2) This program executes correctly with any bit flip in its own code.

Triple redundancy codes

A triple redundancy code consists of simply repeating each bit, character or byte 3 times. In this case we use characters.

Correction is done by taking the majority of the characters, so (A,A,B) is corrected to A, (A,B,B) is corrected to B and so on.

AAA => A
AAB => A
HHHEEELLXLLLXOO => HELLO

This is a very crude an inefficient code for correcting single bit errors, but it is the least complex, which is why I think may be the best choice here. Hamming codes are better but a little more complex.

Putting it together

The error-tolerant program receives as input a (possibly faulty) program, and outputs a error-free program. Therefore, if a single-bit error occurs anywhere in the system comprised of (decoder,input program), a corrected program will still be output.

Observation

I don't actually know if this is possible, quite possibly it won't be achievable in every language. If it is too hard, we may relax the tolerable errors.

Scoring

The score will reflect the reliability of your program to errors. Tolerance is simply the number of bit flips you code accepts anywhere. It must be at least 1 (accept 1 bit flip anywhere). Size is the length of your program in bytes.

The score is Score = Size / 2^Tolerance

Lowest score wins.

Note: Several other challenges are possibly solved by solving this one (which would make sense given its universality!) by hardcoding the input.

Detect if your program has been mutated

Write a program that always outputs “2012” - even if it's modified!

This solves the "Who Watches the Watchmen?" problem involved in error correcting programs, like in this challenge:

Meta radiation hardener

since the decoding program itself tolerates errors (what good would be an error correcting program that is itself in error? :p).

\$\endgroup\$
  • 2
    \$\begingroup\$ Check the radiation-hardening tag for duplicates and rules clarifications, too. \$\endgroup\$ – AdmBorkBork Mar 7 '18 at 19:17
  • \$\begingroup\$ @AdmBorkBork Thanks, I wasn't aware of that. It appears no one has proposed a Universal radiation hardener yet (this is universal only in the sense of bit flip errors; those are actually a good model for radiation though!). \$\endgroup\$ – Real Mar 7 '18 at 19:30
  • \$\begingroup\$ Again Lenguage win lol \$\endgroup\$ – l4m2 Jan 8 at 14:53
  • \$\begingroup\$ Even though your scoring involves code length you should use code-challenge instead of code-golf for challenges that are not solely scored by code length. \$\endgroup\$ – Laikoni Jan 10 at 20:14

You must log in to answer this question.

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