476
\$\begingroup\$

What is the Sandbox?

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

To post to the Sandbox, scroll to the bottom of this page or click on the "Add Proposal" link below, and click "Answer This Question". Click "OK" when it asks if you really want to add another answer. Write your challenge just as you would when actually posting it. You may also add some notes about specific things you would like to clarify before posting it. Other users will help you improve your challenge by rating and discussing it. When you think your challenge is ready for the public, go ahead and post it, replace the post here with a link to the challenge and delete it.

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

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

Add Proposal

Search the Sandbox

Browse your pending proposals

Get the Sandbox Viewer to view the sandbox more easily

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

| | | | | |
\$\endgroup\$
  • \$\begingroup\$ How are tags added to questions? \$\endgroup\$ – guest271314 Jan 9 '19 at 7:51
  • \$\begingroup\$ @guest271314 You can use this markup to create a tag in a draft: [tag:code-golf] \$\endgroup\$ – James Aug 29 '19 at 15:19
  • 3
    \$\begingroup\$ @JL2210 We now have a permanent info box that links to the Sandbox, so the featured tag isn't necessary \$\endgroup\$ – caird coinheringaahing Sep 29 '19 at 13:43

2833 Answers 2833

1
46 47
48
49 50
95
1
\$\begingroup\$

Modular distance

You are given 3 non-negative integers: the domain d, the beginning index b, and the ending index e.

What is a modular distance?

Assume d=5 here. First, generate a range from 0 to 5-1:

0 1 2 3 4

We start from the beginning index. Assuming that is 3:

0 1 2 3 4
      ^

We continually go right, circling every number we've passed, until we met the ending index e.

0 1 2 O O
        ^

If the pointer is at the right end, it wraps around to the left.

Assuming e=0:

O 1 2 O O
^

We filter out every item we've circled:

0 3 4

Then, find how many items there are in this list:

3

Subtract it by 1 and it's our result:

2

Specification

  • You can always assume that b<d and e<d.

Test cases

6 2 5 -> 3
5 3 0 -> 2
| | | | | |
\$\endgroup\$
  • \$\begingroup\$ Do you mean to say "we filter out every item we haven't circled"? \$\endgroup\$ – Lyxal May 5 at 8:30
  • 2
    \$\begingroup\$ Is the modular distance just \$ (e - b) \bmod d\$ ? \$\endgroup\$ – dingledooper May 5 at 20:57
1
\$\begingroup\$

Posted.

| | | | | |
\$\endgroup\$
  • \$\begingroup\$ Is there a non-brute force solution? \$\endgroup\$ – my pronoun is monicareinstate May 1 at 11:21
  • \$\begingroup\$ @mypronounismonicareinstate I haven't created a program for test cases yet, but I'm guessing the answer is no. If that is the case, maybe fastest-code would be a better challenge? \$\endgroup\$ – dingledooper May 1 at 16:08
  • \$\begingroup\$ I do not have a proof that this is computationally difficult :) This would be interesting as [fastest-code], but can this be changed to an optimization problem? (I'm talking about "write a program that splits a grid of size [constant]; your score is the score of your grid"). I'm not sure this doesn't get trivial as size increases though (perhaps larger optimal solutions become simply a bunch of vertical and horizontal lines?). \$\endgroup\$ – my pronoun is monicareinstate May 1 at 16:16
  • \$\begingroup\$ I suppose an optimization problem would be a good idea. Maybe a \$ 10 \times 10 \$ grid? I'll edit it later when I have the time. \$\endgroup\$ – dingledooper May 1 at 22:03
  • \$\begingroup\$ I think 10x10 is still too small (and 100x100 is too big) \$\endgroup\$ – my pronoun is monicareinstate May 2 at 2:33
  • \$\begingroup\$ Do you know the optimal solution? \$\endgroup\$ – S.S. Anne May 2 at 18:26
  • \$\begingroup\$ @S.S.Anne I have no idea what the optimal solution might be. Though it's possible that there is some sort of optimal pattern for this. \$\endgroup\$ – dingledooper May 2 at 18:38
  • \$\begingroup\$ Then don't make that the winning criterion (or the accepted answer). You already have a winning criterion. \$\endgroup\$ – S.S. Anne May 2 at 18:38
  • \$\begingroup\$ @S.S.Anne I don't quite understand what you mean. Are you suggesting that it shouldn't be a code-challenge, or something else? \$\endgroup\$ – dingledooper May 2 at 18:45
  • \$\begingroup\$ I'm suggesting that you remove this winning criterion: "If someone happens to find and prove the optimal solution for the 20×20 graph, I will accept their solution." Although this may fit well with the other, you don't know the optimal solution, so how could you accept an answer? \$\endgroup\$ – S.S. Anne May 2 at 18:49
  • \$\begingroup\$ I suppose I sort of understand what you mean; I've taken your advice. \$\endgroup\$ – dingledooper May 2 at 18:58
  • \$\begingroup\$ There's no reason not to accept if they prove it optimal, though. (I'd use a 30x30 grid) \$\endgroup\$ – my pronoun is monicareinstate May 3 at 3:23
  • \$\begingroup\$ @mypronounismonicareinstate I don't think that increasing the grid size is a bad idea, but I'm wondering why do you think that it is too small, since a fully brute-force solution wouldn't really work on this kind of question. \$\endgroup\$ – dingledooper May 3 at 3:50
1
\$\begingroup\$

Parse vietnamese infinite decimal notation

I wanted to express infinite decimals in text, but overlines are hard.

You need to take a decimal in vietnamese notation, and output the first 10 or more digits of the normal variant.

The notation

The way it works is that you have 0.ab(cd) and it means 0.abcdcdcd.... Of course, you can have any amount of digits in each spot, even zero. You can also omit the infinite part to represent finite decimals.

Notes

It's allowed to not accept 0.2 or 0.2() as input, and it's also allowed to output 0.2000000000 if you do accept them as input.

| | | | | |
\$\endgroup\$
  • 1
    \$\begingroup\$ Can we output the variant infinitely, instead of outputting the first 10 digits? \$\endgroup\$ – Λ̸̸ May 6 at 6:52
  • \$\begingroup\$ An existing keyboard-friendly notation is 0.ab(cd) (Wikipedia reference). \$\endgroup\$ – Bubbler May 6 at 6:57
  • \$\begingroup\$ @Λ̸̸ Sure. I'll edit the question. \$\endgroup\$ – PkmnQ May 6 at 8:22
  • \$\begingroup\$ So is the challenge just to split at the ( and then append the first part to the stuff in the brackets repeated 10 times? \$\endgroup\$ – math junkie May 6 at 16:21
  • \$\begingroup\$ Is this a good time to post the question? \$\endgroup\$ – PkmnQ May 10 at 9:22
1
\$\begingroup\$

Produce a range

Your task is to take a list of integers and find inputs to a Python range call to produce that list. That is, output three values (start, stop, step) so that range(start, stop, step) equals the given list.

You can assume that this is possible, which that consecutive numbers in the list all have the same nonzero difference. Be careful that your code works for negative step sizes, as well as for empty or singleton inputs.

How range works

Python's built-in range produces a list* of equally-spaced numbers. Called as range(start, stop, step), it counts from the start value in increments of step like

[start, start + step, start + 2 * step, ...]

This list continues as long as the value is below stop given positive step, or above stop given negative step. If the start value already fails this test, an empty list is produced. Note that the stop value itself is never included in the list, giving a half-open interval.

range(0, 5, 1)   = [0, 1, 2, 3, 4]
range(0, -5, -1) = [0, -1, -2, -3, -4]
range(0, 2, -1)  = []
range(0, -2, 1)  = []
range(3, 4, 10)  = [3, 7]
range(3, 4, 11)  = [3, 7]
range(3, 4, 12)  = [3, 7, 11]
range(1, -2, 0)  = [1]

*In Python 3, it actually makes a range object, but that doesn't matter here.

Test cases

Note that there can be multiple valid inputs. Different stop values can cut off the result at the same point when the step is not ±1. A singleton or empty list can be produced in many ways.

TODO

| | | | | |
\$\endgroup\$
  • \$\begingroup\$ Is this return {a[0], a[-1]+sign(a[1]-a[0]), a[1]-a[0]}? \$\endgroup\$ – my pronoun is monicareinstate May 7 at 15:43
  • \$\begingroup\$ @mypronounismonicareinstate I think that works for inputs with 2+ elements, though the empty list and singleton list also need to be handled. Is this too simple for a challenge? \$\endgroup\$ – xnor May 7 at 19:32
  • \$\begingroup\$ (I just noticed this might work in languages with modular indexing) This is probably not too simple, and I like the idea, but it seems like most of the complexity here comes from these special cases. \$\endgroup\$ – my pronoun is monicareinstate May 8 at 2:46
1
\$\begingroup\$

Magic Square, Magic Code

A magic square is an \$ n \times n \$ square grid, such that the sum of the integers on each row and column are equal. Note that the definition which will be used in this challenge is different than the one used by Wikipedia, since

  • diagonal sums are not accounted for
  • the numbers are not required to be distinct and in the range \$ 1, 2, ..., n^2 \$

Task

Given an \$ n \times n \$ square, return Truthy if it is a magic square, and Falsey otherwise. There is a catch, however. The source code itself must also form a magic square, where each codepoint in the source code corresponds to an integer.

Input Format

  • You may take input in the following ways:
    • A list of lists (2D array) of the numbers
    • \$ n \$ lines each consisting of \$ n \$ space-separated integers
    • Along with one of the formats above, an optional integer \$ n \$ (the dimensions of the square)
  • You are welcome to use a non-UTF-8 encoding, such as SBCS

This is , so the shortest code in bytes wins!

Sandbox

  • Is the question clear?
  • Opinion on other scoring criteria (sum of codepoints in source code, sum of codepoints in a single row/column of the source code, etc.)
| | | | | |
\$\endgroup\$
  • \$\begingroup\$ Duplicate? \$\endgroup\$ – xnor Apr 30 at 4:04
  • \$\begingroup\$ @xnor it's more closely related, as this has the additional source restriction that programs must be a magic square. Also, diagonals don't matter. \$\endgroup\$ – Lyxal Apr 30 at 4:21
  • \$\begingroup\$ @dingledooper here's another example of when source code was required to be a magic square. I think your current scoring method is fine. \$\endgroup\$ – Lyxal Apr 30 at 4:23
  • \$\begingroup\$ Ah, my mistake. I'd suggest using saying other than Magic Square in the title given that the differences are substantial. \$\endgroup\$ – xnor Apr 30 at 4:48
  • \$\begingroup\$ @xnor Ok, I'll think of a better title! \$\endgroup\$ – dingledooper Apr 30 at 4:58
  • \$\begingroup\$ Can I use custom SBCS for the codepoints? Also, I don't see any reason to ban null bytes (and banning it will be banning a random feature in a golfing language). \$\endgroup\$ – Bubbler May 8 at 5:43
  • \$\begingroup\$ @Bubbler Sure, I've edited the question. \$\endgroup\$ – dingledooper May 8 at 6:03
1
\$\begingroup\$

Arithmetic Square

Note: Credit goes to CCC 2019 S3 for the problem

You are given a \$ 3 \times 3 \$ grid which contains integers. Some of the \$ 9 \$ elements in the grid already have a value, and some of them remain unknown.

Your task is to fill in values for the unknown elements such that for each row, when read left-to-right, produces an arithmetic sequence, and that for each column, when read top-to-bottom, is also an arithmetic sequence.

Recall that an arithmetic sequence of length \$ 3 \$ is a sequence of integers in the form

$$ a, a + d, a + 2d $$

for integer values of \$ a \$ and \$ d \$. Note that \$ d \$ may be any integer, including zero and negatives.

Input Specification

  • You may input the \$ 3 \times 3 \$ grid in any sensible format
  • The unknown values may be represented by any character, so long that it is not a number (i.e. \$ 0-9 \$)

Output Specification

  • The output must be in the same format as the input, with the exception of unknown values becoming integers
  • All rows and columns must form arithmetic sequences
  • There is guaranteed to be at least one solution, and you may output any of them

Test Cases

(This is the only solution)
 8  9 10       8  9 10
16  X 20  ->  16 18 20
24  X 30      24 27 30

(This is one of many solutions)
14  X  X      14 20 26
 X  X 18  ->  18 18 18
 X 16  X      22 16 10

(This is the only solution)
 X -1 -2       0 -1 -2
 5  X  3  ->   5  4  3
 X  X  X      10  9  8

(This is one of many solutions)
 X  X  X       0  0  0
 X  X  X  ->   0  0  0
 X  X  X       0  0  0

This is , so the shortest code in bytes wins!

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

Generate a "Poem"

Given a strictly positive integer, N, produce an output satisfying the following:

  • Produce an array of length N.
  • Every string (i.e. "word") in the array is of length N.
  • Every letter in the word is unique.
  • Every first letter of the words are unique between each other.
  • The remaining items of each word are equal to each other.

Example output

For an input of e.g. 3:

cba
dba
eba

Specification

  • Trailing whitespace is totally allowed.
  • The "letters" don't have to be from the lowercase alphabet, as long as they aren't whitespace.
  • The maximum N you need to support is 13, since there are 26 letters in the lowercase alphabet.
  • The separator of your array can be anything, as long as you will never involve that character for every possible input from 1 to 13. You can also just output a literal array.
| | | | | |
\$\endgroup\$
  • 1
    \$\begingroup\$ is there a maximum N we need to support? \$\endgroup\$ – Lyxal May 12 at 0:56
  • \$\begingroup\$ Yes, the maximum N here is 13. \$\endgroup\$ – Λ̸̸ May 15 at 10:15
1
\$\begingroup\$

Is this a Freeman Dyson Number?

Background

From this Popular Mechanics article

One day, in a gathering of top scientists, one of them wondered out loud whether there exists an integer that you could exactly double by moving its last digit to its front. For instance, 265 would satisfy this if 526 were its exact double – which it isn’t. After apparently just five seconds, Dyson responded, “Of course there is, but the smallest such number has 18 digits.”

Challenge Write a program that, when given a base ten number that is at least 18 digits long, moves the last digit to the front and checks if it is doubled as a result.

I/O
Input can be any 18 (or longer) digit integer. Any leading digit must be larger than zero.

Output
The original number with the Dyson transform (last digit moved to the front) and any truthy/falsey value (if that's a digit, it must have a delimiter).

Test Cases/Sample I/O

111111111111111111 -> 111111111111111111,false
100000000000000002 -> 210000000000000000 **F**
123456789123456789 -> [912345678912345678,0]
42105263157894736842 -> 24210526315789473684👎
808080808080808080808080808016 - 680808080808080808080808080801-NO
246802468024680246802468024680246802 -> false224680246802468024680246802468024680
105263157894736842 -> true,210526315789473684
315789473684210526 -> (T:5315789473684210526)
26315789473684210526315789473684210 -> 52631578947368421052631578947368421👍

etc...

, so shortest answer in bytes (by language) wins.

| | | | | |
\$\endgroup\$
  • \$\begingroup\$ I would specify that you are talking about decimal digits. \$\endgroup\$ – Jonathan Frech Mar 22 at 17:46
  • \$\begingroup\$ @JonathanFrech, Do you mean base 10? \$\endgroup\$ – ouflak Mar 22 at 19:32
  • \$\begingroup\$ I think one issue here is how to verify that the specific action of moving the digit from back-to-front, and then subsequently checking for doubling, actually happened. Not sure how to get around that. \$\endgroup\$ – ouflak Mar 22 at 20:10
  • \$\begingroup\$ Yes, you should specify that this is in base 10. \$\endgroup\$ – S.S. Anne Mar 22 at 20:46
  • \$\begingroup\$ @ouflak Yes, I mean base ten. One often hears for example "binary digits", so the term "digits" is in my opinion not clearly defined to mean base ten. \$\endgroup\$ – Jonathan Frech Mar 22 at 21:55
  • \$\begingroup\$ @JonathanFrech, @ S.S. Anne, The reason why I haven't immediately made the change is because I hadn't considered the idea of different number bases, and I'm really liking the idea of a challenge that in fact does include either various number bases, or a specific challenge for binary and this separate challenge for base ten. Mulling it over now. This would mean I'd have to figure out some binary test cases.... \$\endgroup\$ – ouflak Mar 23 at 6:44
  • 1
    \$\begingroup\$ In binary doubling a number is adding 0 to the end of it, so unless you allow leading 0s it's not possible, otherwise it's correct iff the number starts with a 0 \$\endgroup\$ – Command Master Mar 24 at 19:43
  • \$\begingroup\$ @CommandMaster, Yes! For binary, you would have to allow, even implicitly, a leading zero. The most obvious example is '1', which is really '01', which when the '1' is moved to the front becomes '10'. Don't see how you can get around that. It would be a different challenge. The number base thing has got me thinking. \$\endgroup\$ – ouflak Mar 25 at 8:35
  • 2
    \$\begingroup\$ Here are some suggestions: Make it a decision-problem (e.g. returning the Dyson transform and the Truthy/Falsey value is a bit unnecessary). Keep the sample IO consistent (I get that you want to show the variation in possible output formats, but it would be easier to verify cases if the format were consistent). \$\endgroup\$ – dingledooper May 12 at 19:55
1
\$\begingroup\$

Posted

Tile the plane with squashed hexagons

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

There are \$a\$ honest man(always tell the truth), \$b\$ dishonest man(always tell lie), and \$c\$ random man(tell random Y/N). How many times at least should you ask one of them a yes/no question to guarantee you get knowledge of who they are? You may assume that it's possible.

Test cases:

(a,b,c) -> ans
(1,1,0) -> 1
(1,1,1) -> 3
(0,0,2) -> 0

Notes:

  • I don't know if there's clever way, but anyway brute-force work
  • It's enough if you can only ask an expression about who they are. If you ask them "what will A answer if I ask B" the answer is just "(A is liar) xor B". "Did A tell lie when answering B" is just "(A's answer) xor B". Questions about the current ask or future ask may lead to paradox and are not allowed.
  • Actually it's possible to identify them iff there are less than half of random answerer, or an edge case that all are random answerers. Only considering honest and random, if there are more honest than random, ask them same question and do a majority vote gets answer to the question. If there are same honest and random, and random tell as if they are honest and real honest are random, you can't tell the difference.
| | | | | |
\$\endgroup\$
  • \$\begingroup\$ I think the wording is a little confusing. Will there always be one of each? Will your program be given a list of a, b, and cs as input? Also, you may want to look at this question to check if it's similar to yours. \$\endgroup\$ – Redwolf Programs May 14 at 21:23
  • 1
    \$\begingroup\$ @RedwolfPrograms Yes a,b,c are given, and possibly zero. Link don't match this problem well \$\endgroup\$ – l4m2 May 15 at 2:48
  • \$\begingroup\$ Wouldn't it require at least 4 questions for the test case (1, 1, 1)? How to solve in 3? \$\endgroup\$ – user202729 May 16 at 3:46
  • \$\begingroup\$ @user202729 brainden.com/forum/topic/… (not wiki answer as it assume answer from random is either true or false) \$\endgroup\$ – l4m2 May 16 at 3:47
  • \$\begingroup\$ Oh wiki also has a standard solution \$\endgroup\$ – l4m2 May 16 at 3:53
  • 1
    \$\begingroup\$ @RedwolfPrograms Formal description (according to my understanding of the statement) \$\endgroup\$ – user202729 May 16 at 4:48
1
\$\begingroup\$

Compress a grandmaster chess position

Background

Compress a position from a grandmaster chess game to as few bits as possible on average. A strong submission will probably use that these positions come from real games by top players, and so will make chess sense and strategic sense, rather than just being random legal chess positions. As illustration, a study found that grandmasters do well at memorizing positions from real games using "chunking" but with only perform at novice level memorizing random boards.

The is related to but different from Smallest chess board compression, which scores on the worst-case scenario, and Smallest chess game compression, which compresses full games. (Sandbox: Let me know if this is too similar)

Task

You must write a compressor, which maps a chess position onto a sequence of bits, and a decompressor that returns its to the original position. You can vary the length of the bit sequence by position, and this will likely be important to getting a good score.

The position to compress will just be a the placement of pieces on the chess board. You do not to encode whose move it is, castling rights, or en-passant. It will be given in FEN string format with only the piece placement part, for example:

2krn2r/pppb4/4pq2/3pN2p/5P2/2PBP3/PP4P1/R2QK2R

The chess position for this FEN

Each letter corresponds to a piece (pawn="P", knight="N", bishop="B", rook="R", queen="Q", and king="K"). White's pieces use uppercase letters and Black's are lowercase. Slashes separate the descriptions of each of the rows from top to bottom, that is the 8 files doing from 8 (where black's pieces start) to down to 1. Numbers are used for blocks of that many empty spaces that are horizontally adjacent.

Scoring

You will be scored on the average length of your compressed bit sequence on 10,000 random game positions. They will chosen at random from games played by grandmasters, restricted to move 5 or later. [Will work out more details when generating this data.]

This Pastebin (TODO) contains 10,000 FEN strings to use as a training set that you can use to get a preliminary score. The final score will be based on a separate secret test set of 10,000 FEN strings.

Your code must correctly decode every game in the position. Be sure that it can handle all positions, such as ones with weird underpromotions, which might appear in the test set but not the training set. (Sandbox: How to handle submissions that break this? A default penalty score for games failed? Ask to resubmit?)

Your compression and decompression must complete within 5 minutes on all the games. (Sandbox: Allow to compress all games at once? Do one game at a time but store state to allow "learning"? Include a memory limit?)

The length of your code is immaterial to this challenge.

| | | | | |
\$\endgroup\$
  • \$\begingroup\$ How long (in number of positions) would a naive program that hardcodes all of the (recorded) existing grandmasters games be? (if that's not large enough, it would make the challenge trivial) \$\endgroup\$ – user202729 May 17 at 11:49
  • \$\begingroup\$ @user202729 That's a good question, I definitely don't want code to be use that the test set comes from an actual database, so I'd either needed to make that non-viable or ban it. \$\endgroup\$ – xnor May 17 at 12:31
  • \$\begingroup\$ Does the time requirement have to be as strict as 30 games per second? (a certain question of the part also mentions "every game in the position", I assume that's a mistake) (I have no idea how to prevent storing a database of grandmaster games though) \$\endgroup\$ – my pronoun is monicareinstate May 17 at 16:00
  • \$\begingroup\$ @myp I think that this requirement means that it can compress each game in 5 minutes. \$\endgroup\$ – user202729 May 18 at 0:50
  • \$\begingroup\$ @user202729 I had meant total for all the games, but I'll probably loosen it. \$\endgroup\$ – xnor May 18 at 2:19
1
\$\begingroup\$

Permutation primes

A permutation prime is a prime such that at least one of its uniquified permutations (not equal to itself) of its digits is a prime.

Given a number, check if this number is a permutation prime.

Reference program

Here is a reference program I made.

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

The golfing skills are strong with this one

Task

Consider the base string s = "The golfing skills are strong with this one", an adaptation of the quote "The force is strong with this one" by Darth Vader, an infamous character of the Star Wars saga (sandbox, am I correct?).

You have to output the string s with as many characters as there are bytes in your source code. If your code is longer than s, extend s by concatenating it repeatedly as many times as needed.

Your program must be non-empty.

Input

You may or may not take the string s as input for your program. (Sandbox, maybe it is more interesting to not allow the string as input?)

Output

A string as specified in the Task.

| | | | | |
\$\endgroup\$
  • 1
    \$\begingroup\$ Many languages, 0 bytes. PHP and /// polyglot, 1 byte: T. If the code is too long, is the string really intended to be The golfing skills are strong with this oneThe golfing skills are strong with this oneThe golfing skills are strong with this one? \$\endgroup\$ – my pronoun is monicareinstate May 20 at 16:42
  • \$\begingroup\$ @mypronounismonicareinstate do you see a problem with the string being like that? What would you suggest? Also, probably should not allow the string to be used as input and require a non-empty program \$\endgroup\$ – RGS May 20 at 16:46
  • 1
    \$\begingroup\$ That is perfectly acceptable, it's just that the transitions aren't very smooth (oneThe). If you can take the string as input, solutions won't have to depend on this specific string, so it would probably be a bad idea. (I mean, a[:5] isn't a very interesting answer) \$\endgroup\$ – my pronoun is monicareinstate May 20 at 16:51
  • \$\begingroup\$ @mypronounismonicareinstate I failed to understand what variation you think is a bad idea. Do you think it is a bad idea to accept it as input or a bad idea to not accept it as input? \$\endgroup\$ – RGS May 20 at 16:52
  • \$\begingroup\$ I think it is a bad idea to accept it as input. \$\endgroup\$ – my pronoun is monicareinstate May 20 at 16:53
1
\$\begingroup\$

Halting problem for simplified Brainfuck

Given a simplified Brainfuck program, you must determine whether it halts. Your program must always halt in finite time on valid inputs.

Simplified Brainfuck is a language that operates on a zero-initialized tape that is infinite in both directions. All cells contain integers from 0 to 255, and operations are performed modulo 256. There are the following instructions:

+ increment the current cell
- decrement the current cell
< move 1 cell to the left along the tape
> move 1 cell to the right along the tape
[ if the current cell is zero, skip past the next ]
] go to the previous [

Loops ([]) can't be nested.

This is tagged , so the shortest answer wins.

| | | | | |
\$\endgroup\$
  • \$\begingroup\$ Do you mean "Given a simplified Brainfuck program and an input of such program"? \$\endgroup\$ – Domenico Modica May 21 at 5:00
  • \$\begingroup\$ @DomenicoModica No, this language has no IO. Do you think I should mention that explicitly? \$\endgroup\$ – my pronoun is monicareinstate May 21 at 5:02
  • \$\begingroup\$ Oh, I don't know, I was too hasty ahahah... Anyway If the tape was finite surely it would be solvable \$\endgroup\$ – Domenico Modica May 21 at 5:07
  • \$\begingroup\$ I think it is indeed solvable with doubly infinite tape, since the region that the pointer touches within an iteration of a loop is limited (which means we have finite number of states in that region). It's pretty hard to describe the algorithm though. \$\endgroup\$ – Bubbler May 21 at 5:56
  • \$\begingroup\$ That is what I had in mind. Handling two loops in different directions is also non-trivial. \$\endgroup\$ – my pronoun is monicareinstate May 21 at 6:00
  • \$\begingroup\$ I don't think handling multiple loops is that non-trivial. Consider first loop first, the answer is false if it is infinite loop, otherwise run it to the end and run all commands before the second loop. Then consider the second loop just like the first, etc. \$\endgroup\$ – Bubbler May 21 at 6:49
  • 1
    \$\begingroup\$ Actually I think the challenge is not very interesting as[code-golf], because it's necessary to simulate the algorithm anyway and it can be proven (I think) that the number of steps the program takes (if it halts) is no more than \$2^{2^{2^{2^n}}}\$ (where n is the program length), so it will be no longer than an interpreter but takes impractically long to run. \$\endgroup\$ – user202729 May 22 at 8:48
1
\$\begingroup\$

Posted: SELECT ALL FROM SelectQL WHERE (answer="short" OR NOT length=10000)

| | | | | |
\$\endgroup\$
  • \$\begingroup\$ What happens if the specified table doesn't exist? \$\endgroup\$ – Lyxal May 15 at 4:37
  • \$\begingroup\$ The usual SQL statement is SELECT * FROM data, where * is the wildcard operator. Also, the set of parentheses after "WHERE" is not mandatory in usual SQL. I guess these changes make the challenge easier to parse. \$\endgroup\$ – Λ̸̸ May 15 at 4:56
  • \$\begingroup\$ @Λ̸̸ Yeah, it's to make it slightly easier. However, I could change it. Which I will! \$\endgroup\$ – bigyihsuan May 15 at 23:54
  • \$\begingroup\$ @Lyxal undefined, the programs should assume that the table is in the database \$\endgroup\$ – bigyihsuan May 15 at 23:55
  • 2
    \$\begingroup\$ Consider deleting this post, as the challenge is already on main \$\endgroup\$ – RGS May 20 at 16:50
1
\$\begingroup\$

Posted: Stepping Through Time

| | | | | |
New contributor
Vaelus is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.
\$\endgroup\$
1
\$\begingroup\$

Enforce Social Distancing!

Related to Maintain Social Distancing!.

As in that challenge, there is a 2-dimensional array of 1s and 0s representing people. In it, social distancing is maintained if and only if all 1s are at least 6 squares apart, where distance metric used is \$|\Delta x| + |\Delta y|\$ (rectilinear or Manhattan).

The challenge here is to move some people in a given 2D array so that social distancing is maintained. It's guaranteed that it's possible to do so. Your program's score on a given input is the total distance moved by all people.

Your program's running time must not exceed 10 seconds on any of the test cases.

This is tagged , so there is a large set of inputs your programs will be tested on [TODO: actually create it]. The program with the lowest total score on all of these inputs wins.

Sandbox stuff

  • Is this currently a bad idea for the reasons specified by Shaggy in the following comment?

    I am sorry but I have downvoted this for what others may perceive to be a trivial reason: Code Golf is one of the few things I have left where I can escape how fucked my world has become; I absolutely do not want to come here to be reminded that I can't hug my family and friends.

  • Is there an optimal algorithm? (I hope not)
| | | | | |
\$\endgroup\$
1
\$\begingroup\$

Quickly calculate \$ n! \bmod p \$

The idea is extremely simple: Given two positive integers \$ n \$ and \$ p \$, calculate the result of \$ n! \bmod p \$, where \$ p \$ is a prime.

Scoring

Your score is the highest \$ p \$ you can achieve within \$ 10 \$ seconds, by running the program \$ 10 \$ separate times. More specifically, each run-through will contain two inputs \$ n \$ and \$ p \$. You are to solve \$ n! \bmod p \$, where \$ n \$ is a random number in the range \$[1, p]\$.

You must use this program to generate the \$ 10 \$ test cases. So for example, if \$ p = 13 \$, the test case would look like this:

n, p
9, 13
3, 13
10, 13
13, 13
7, 13
13, 13
8, 13
9, 13
6, 13
4, 13

Rules

  • Make sure that each test case is run separately, meaning you are not allowed to make use of previous test cases
  • Multi-threading is disallowed
  • Official times will be tested on my machine; make sure to include specifcations on how to run it

This is , so the highest score wins!

Sandbox

  • Any loopholes that need to be addressed?
  • Is there an easy, trivial solution to this?
| | | | | |
\$\endgroup\$
  • 1
    \$\begingroup\$ To force independent calculation you should invoke the program 10 separate times. Although it remains possible to store data in files or similar, it would be pretty obvious. \$\endgroup\$ – user202729 May 22 at 8:58
  • 1
    \$\begingroup\$ As far as I know the best-known time complexity is asymptotically \$ \widetilde O (\sqrt p)\$, although the implementation is rather tedious and uninteresting. \$\endgroup\$ – user202729 May 22 at 9:00
  • 1
    \$\begingroup\$ Your example test case has p=10 which isn't prime \$\endgroup\$ – xnor May 22 at 10:31
  • \$\begingroup\$ @xnor Fixed, thanks. \$\endgroup\$ – dingledooper 2 days ago
1
\$\begingroup\$

Inspired by Draw this planar graph.

Your input represents an ascending sequence, e.g. 1 2 3 4. You can require the sequence as input, or you can just input the length. The explanation assumes 1-indexing but you can use 0-indexed or even a-indexed input if you adjust the algorithm appropriately.

At each step, you can exchange any digit of value n with the digit n places to its right. So the valid second steps are 2 1 3 4 and 1 4 3 2. Eventually you want to end up at the reverse sequence 4 3 2 1, which is the only permutation that has no legal steps.

Please output all possible sequences of steps from the input sequence to its reverse.

You should support sequences of up to at least 10 elements.

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

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

Shorten the numbers

These numbers are taking up far too many bytes on my computer. Create a function/program to shorten any number using only Alphanumeric characters as the output.

Scoring

Scoring is based on optimized-output. Shortest number of characters produced for the following randomly generated numbers (plus one special number with repetition) wins. Add the number of output characters output for the 5 test numbers together for total score.

  • 94949267912781
  • 75477115147709
  • 79547324913976
  • 12345678998765
  • 11111122222222

The score of the non-optimized numbers = 70. (14 * 5)

Sandbox questions

  • does scoring make sense?
  • should I include a sample script, output, or both?
  • should I be more clear the answers should work on any number? (ie. "replacing each test number with one character is disallowed")?
| | | | | |
New contributor
Andrew Grothe is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.
\$\endgroup\$
  • 2
    \$\begingroup\$ Base conversion from base 10 to base-255? \$\endgroup\$ – Λ̸̸ 2 days ago
  • 1
    \$\begingroup\$ As long as you're scoring on those five test numbers, the winning score is going to be the absolute smallest thing you haven't explicitly forbidden. Not allowing solutions to be tailored to those five is what we'd call a non-observable requirement, and considering how many different ways it could be approached I'm not sure how well a human could even really try to judge it. On the other hand, if you try to score it over the natural numbers, we just do base conversion. I feel like this can't work as an output optimization challenge. \$\endgroup\$ – Unrelated String 2 days ago
1
\$\begingroup\$

Inspired by Wizard creating a jewelry.

Given an input list of positive integers, calculate the minimum cost of creating the list from the following operations:

  1. Appending a positive integer costs the value of the integer.
  2. Incrementing the entire list costs 2.
  3. Exchanging two consecutive elements of the list costs 1.

Example: The list 1 4 9 16 25 could be constructed as follows:

  • Append 1
  • Append 8
  • Append 17
  • Increment
  • Increment
  • Increment
  • Increment
  • Increment
  • Append 1
  • Swap 22 with 1
  • Swap 13 with 1
  • Swap 6 with 1
  • Increment
  • Increment
  • Increment
  • Append 1
  • Swap 25 with 1
  • Swap 16 with 1
  • Swap 9 with 1
  • Swap 4 with 1

This costs 51, which is an improvement over simply appending the integers, as that is a cost of 54.

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

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

Cheat activated

Background

The game Grand Theft Auto: San Andreas went down to history also thanks to its wide selection of cheats. They're almost 90 and anyone who has ever touched this game, no doubt he tried them all!
One cheat is activated (on PC) typing in-game a secret keyword, and then boom, a jet pops out of thin air or perhaps all pedestrians look like Elvis Presley or some other rowdy effect...

They always come with this confirmation message:

enter image description here

Rockstar choosed to store them hashed, so due to collision, in addition to the intended ones there are many other strings that trigger every cheat.

Therefore I propose to solve this downside!

Task

Write a full program that prints CHEAT ACTIVATED if and only if the last part of a string is a cheat code.

Cheat codes

THUGSARMOURY
PROFESSIONALSKIT
NUTTERSTOYS
INEEDSOMEHELP
TURNUPTHEHEAT
TURNDOWNTHEHEAT
PLEASANTLYWARM
TOODAMNHOT
DULLDULLDAY
STAYINANDWATCHTV
CANTSEEWHEREIMGOING
TIMEJUSTFLIESBY
SPEEDITUP
SLOWITDOWN
ROUGHNEIGHBOURHOOD
STOPPICKINGONME
SURROUNDEDBYNUTTERS
TIMETOKICKASS
OLDSPEEDDEMON
DOUGHNUTHANDICAP
NOTFORPUBLICROADS
JUSTTRYANDSTOPME
WHERESTHEFUNERAL
CELEBRITYSTATUS
TRUEGRIME
ALLCARSGOBOOM
WHEELSONLYPLEASE
STICKLIKEGLUE
GOODBYECRUELWORLD
DONTTRYANDSTOPME
ALLDRIVERSARECRIMINALS
PINKISTHENEWCOOL
SOLONGASITSBLACK
FLYINGFISH
WHOATEALLTHEPIES
BUFFMEUP
LEANANDMEAN
BLUESUEDESHOES
ATTACKOFTHEVILLAGEPEOPLE
LIFESABEACH
ONLYHOMIESALLOWED
BETTERSTAYINDOORS
NINJATOWN
LOVECONQUERSALL
EVERYONEISPOOR
EVERYONEISRICH
CHITTYCHITTYBANGBANG
CJPHONEHOME
JUMPJET
IWANTTOHOVER
TOUCHMYCARYOUDIE
SPEEDFREAK
BUBBLECARS
NIGHTPROWLER
DONTBRINGONTHENIGHT
SCOTTISHSUMMER
SANDINMYEARS
KANGAROO
NOONECANHURTME
MANFROMATLANTIS
LETSGOBASEJUMPING
ROCKETMAN
IDOASIPLEASE
BRINGITON
STINGLIKEABEE
IAMNEVERHUNGRY
STATEOFEMERGENCY
CRAZYTOWN
TAKEACHILLPILL
FULLCLIP
IWANNADRIVEBY
GHOSTTOWN
HICKSVILLE
WANNABEINMYGANG
NOONECANSTOPUS
ROCKETMAYHEM
WORSHIPME
HELLOLADIES
ICANGOALLNIGHT
PROFESSIONALKILLER
NATURALTALENT
OHDUDE
FOURWHEELFUN
HITTHEROADJACK
ITSALLBULL
FLYINGTOSTUNT
MONSTERMASH

Input

  • A string \$s\$ over the alphabet:
    [A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z]

Output

  • Print CHEAT ACTIVATED if there exist a cheat code \$c\$ such that \$c\$ is a suffix of \$s\$
  • Nothing otherwise

This is , so the shortest code wins.

| | | | | |
\$\endgroup\$
  • \$\begingroup\$ Do we have to output the specific Cheat activated string, or just a truthy/falsy value indicating whether or not a valid cheat code exists? (I also don't think \$i\$ is a good name for a string; is that intentional?) \$\endgroup\$ – my pronoun is monicareinstate May 21 at 4:27
  • \$\begingroup\$ @my pronoun is monicareinstate Yes, that specific string, it's a little simulation. And yes, you're right \$s\$ is the canonical name, I choose "i" for input, but never mind \$\endgroup\$ – Domenico Modica May 21 at 4:39
  • 1
    \$\begingroup\$ I think that restricting the output to Cheat activated is unnecessary since it doesn't really add anything to the challenge. Consider allowing just a truthy or falsey value as output. \$\endgroup\$ – math junkie May 21 at 19:01
  • \$\begingroup\$ @math junkie I'm aware that in terms of logic it's useless. But that comes if only the "recognition part" is considered being the intended challenge. From my idea, generating Cheat activated it's also a part of it... I worded it badly in the task part \$\endgroup\$ – Domenico Modica May 21 at 20:08
  • 1
    \$\begingroup\$ 18HOLES is in the cheat codes list, yet the input states that there will be no number. Is this intended? \$\endgroup\$ – dingledooper 2 days ago
  • \$\begingroup\$ @dingledooper No, my mistake, I thought I had removed it in the last edit \$\endgroup\$ – Domenico Modica 2 days ago
1
\$\begingroup\$

Reduce the entropy of the input...

Spec

Given two arguments:

  • A list containing 2 or more positive integers (from 0 to artificial limit of 2^32)
  • A positive number defining the 'entropy allowance'

Return a sublist containing elements up until the entropy allowance is used up.

For this challenge, we define 'entropy' as the difference in bits between numbers in the list; also known as the Hamming distance.

Note that no 'entropy' is used up when flipping the bits in the first number, only used when flipping subsequent bits.

Examples

Worked example (MSB...LSB), keeping the numbers low to keep things simple:

Example 1:

List: [1, 2, 3, 4, 5, 6] Allowance: 4

1 => 0000 0001 - ignore implicit change from 0, total used = 0
2 => 0000 0010 - change of 2 bits, total used = 2
3 => 0000 0011 - change of 1 bit, total used = 3 
4 => 0000 0100 - change of 3 bits, total used = 6 (would exceed allowance)
5 => 0000 0101 - change of 1 bit, total used = 7
6 => 0000 0110 - change of 2 bits, total used = 9

Output: [1, 2, 3]

Example 2:

List: [255, 0, 127, 64, 32, 100] Allowance: 23

255 => 1111 1111 - ignore implicit change from 0, total used = 0
0   => 0000 0000 - change of 8 bits, total used = 8
127 => 0111 1111 - change of 7 bit, total used = 15
64  => 0100 0100 - change of 6 bits, total used = 21
32  => 0010 0000 - change of 2 bit, total used = 23
100 => 0110 0100 - change of 2 bits, total used = 25

Output: [255, 0, 127, 64, 32]

Meta

Is this interesting enough a challenge? Is it just a chameleon (is it just the hamming distance with extra steps)? Thoughts?

If it's not shot down for being a plain, any ideas for a better title?

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

Make true and false global!

We all know true and false, but what do speakers around the globe say?

+----------------------+------------+------------+
| Language             | True       | False      |
+----------------------+------------+------------+
| Arabic               | sahih      | zaif       |
| Armenian             | irakan     | kelc       |
| Assamese             | asol       | misa       |
| Breton               | gwir       | gaou       |
| Bulgarian            | veren      | neveren    |
| Catalan              | veritable  | fals       |
| Cornish              | gwir       | gaw        |
| Czech                | pravdivy   | nepravdivy |
| Danish               | sand       | falsk      |
| Dutch                | waar       | onwaar     |
| English              | true       | false      |
| Esperanto            | vera       | malvera    |
| Finnish              | tosi       | epatosi    |
| French               | vrai       | faux       |
| Galician, Portuguese | verdadeiro | falso      |
| Georgian             | namdvili   | cru        |
| German               | wahr       | falsch     |
| Greek                | alithis    | psevdis    |
| Hebrew               | hiyuvi     | shikri     |
| Hindi, Urdu          | thik       | jhutha     |
| Hungarian            | igaz       | hamis      |
| Icelandic            | sannur     | rangur     |
| Indonesian, Malay    | benar      | salah      |
| Irish                | fior       | breagach   |
| Italian              | vero       | falso      |
| Japanese             | shin       | nise       |
| Korean               | chamida    | geojit     |
| Latin                | verus      | falsus     |
| Latvian              | patiess    | nepareizs  |
| Mandarin Chinese     | zhen       | jia        |
| Maori                | pono       | pate       |
| Persian              | dorost     | galat      |
| Polish               | prawdziwy  | falszywy   |
| Romanian             | adevarat   | fals       |
| Russian              | vernyj     | falsivyj   |
| Sardinian            | beru       | falsu      |
| Scottish Gaelic      | fior       | breugach   |
| Spanish              | verdadero  | falso      |
| Swedish              | sann       | falskt     |
| Sylheti              | hasa       | misa       |
| Turkish              | dogru      | yanlis     |
| Volapuk              | veratik    | dobik      |
| Welsh                | gwir       | anwir      |
+----------------------+------------+------------+

All words ASCIIfied from Wiktionary: true, false. Preference given to first entry under 'state in Boolean logic' if available, otherwise first entry under 'concurring with a given set of facts' or 'untrue, not factual, wrong', respectively. I apologise if your favourite language is not included or the word choice for your language is not optimal. No correspondence will be entered into.

Write a program or function that takes one word from the table above as input and outputs truthy if the word means 'true' and falsy otherwise. Your code must produce the correct output for all 79 possible inputs. Shortest code (in bytes) in each language wins.

Sorted list of unique words meaning 'true':

adevarat,alithis,asol,benar,beru,chamida,dogru,dorost,fior,gwir,hasa,hiyuvi,igaz,irakan,namdvili,patiess,pono,pravdivy,prawdziwy,sahih,sand,sann,sannur,shin,thik,tosi,true,vera,veratik,verdadeiro,verdadero,veren,veritable,vernyj,vero,verus,vrai,waar,wahr,zhen

Sorted list of unique words meaning 'false':

anwir,breagach,breugach,cru,dobik,epatosi,fals,falsch,false,falsivyj,falsk,falskt,falso,falsu,falsus,falszywy,faux,galat,gaou,gaw,geojit,hamis,jhutha,jia,kelc,malvera,misa,nepareizs,nepravdivy,neveren,nise,onwaar,pate,psevdis,rangur,salah,shikri,yanlis,zaif

Meta

Has something similar been asked before?

| | | | | |
New contributor
Dingus is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.
\$\endgroup\$
  • \$\begingroup\$ Mathematica has WordTranslation[x, All -> "English"], but it doesn't support all languages necessary :(. \$\endgroup\$ – my pronoun is monicareinstate 20 hours ago
1
\$\begingroup\$

Find all Belphegor primes

Inspired by The Most Evil Number - Numberphile

A Belphegor number is a number of the form \$(10^{n+3}+666)*10^{n+1}+1\$ (1{n zeroes}666{n zeroes}1) where \$n\$ is an non-negative integer. A Belphegor prime is a Belphegor number that is also prime.

The \$n\$ values of the first few Belphegor primes are 0, 13, 42, 506 (A232448)

Task

Write a program that that outputs all Belphegor primes or their \$n\$ values. A reference python implementation can be found here.

You may use probabilistic primality tests as there is no known counter case.

Scoring

This is so shortest bytes wins.

| | | | | |
\$\endgroup\$
  • 1
    \$\begingroup\$ I am not certain, but it seems like the reference implementation uses the Miller-Rabin primality test with one of the best known base choices for numbers up to 2^64. While it works for numbers up to 2^64, it can produce incorrect results for larger numbers, making the implementation seemingly invalid. However, I'm not sure about that, because the BPSW test is also probabilistic but it also happens to have not a single known pseudoprime and is often used by default isprime functions and is usually considered acceptable in answers... \$\endgroup\$ – my pronoun is monicareinstate yesterday
  • \$\begingroup\$ Updated the question to allow probabilistic primality tests \$\endgroup\$ – Mukundan yesterday
0
\$\begingroup\$

Write a compiler/interpreter for ...

Inspired by the lisp challenge here.
It is a series of puzzles.

I don't like to see a simple eval solution, so:

  • interpreting the language is fine
  • translating the language to a different language is fine.

I think this is specific for each language.

Only the syntax and the basic commands.
Also specific.

Winning criteria should not be code golf.
The goal should be that you can "learn" an other language by looking at the code.

Languages that might be good candidates:

  • Lisp
  • APL
  • J
  • Brainfuck (already posted)
  • Whitespace
  • Forth
| | | | | |
\$\endgroup\$
  • 1
    \$\begingroup\$ This only works for languages which are small and well defined. BF fits those criteria. Whitespace does too. The others may not. Lisp and Forth have so many dialects that you would have to specify exactly which dialect to support; Lisp, Forth, APL and J might have too many built-ins to fit in an answer: there are character limits. \$\endgroup\$ – Peter Taylor May 12 '13 at 15:16
  • \$\begingroup\$ You don't have to provide all the built-ins, but that is why it is here. \$\endgroup\$ – Johannes Kuhn May 12 '13 at 15:38
  • \$\begingroup\$ What defines the "basic commands"? \$\endgroup\$ – ASCIIThenANSI Aug 31 '15 at 17:54
  • \$\begingroup\$ I don't know? Maybe that you can do the basic stuff with it like +,-,print,... \$\endgroup\$ – Johannes Kuhn Aug 31 '15 at 18:22
  • 1
    \$\begingroup\$ I suggest a programmer can implement the tiniest subset of those languages in order to be Turing-complete, as these are non-trivial subsets that can theoretically simulate the rest of the language... \$\endgroup\$ – user85052 Jun 28 '19 at 4:17
  • \$\begingroup\$ Which human is learning the programming language by looking at the code? \$\endgroup\$ – MilkyWay90 Aug 26 '19 at 3:23
0
\$\begingroup\$

Find Maximum number of 4+ letter words from Scabble Tiles

The challenge is to find the most words with 4 or more letters you can make with one set of scrabble tiles.

The tile distribution is as follows:

2 Blank Tiles
A 9  N 6    +====+===========+
B 2  O 8    | 01 | K J X Q Z |
C 2  P 2    | 02 | B C M P F |
D 4  Q 1    | 02 | H V W Y * |
E 12 R 6    | 03 | G         |
F 2  S 4    | 04 | L S U D   |
G 3  T 6    | 06 | N R T     |
H 2  U 4    | 08 | O         |
I 9  V 2    | 09 | A I       |
J 1  W 2    | 12 | E         |
K 1  X 1    +====+===========+
L 4  Y 2
M 2  Z 1

Valid words are any words that are 4+ that are available in this file, the official scrabble dictionary.

Tiles cannot be used twice. This means you can only have 1 word with a K, J, X, Q, and/or Z unless you use a blank tile to represent one of these letters.

I'm not sure how I'd do scoring on this. I want shorter code to score better, but I don't want a short piece of code that finds a lot less words to score better than a longer piece that finds many more words.

| | | | | |
\$\endgroup\$
  • \$\begingroup\$ Meh. I don't like dependency on external files; are we allowed to load it, or even embed it into the source code? \$\endgroup\$ – John Dvorak Dec 17 '13 at 20:00
  • \$\begingroup\$ as for finding more vs. shorter code, you could demand all words be found \$\endgroup\$ – John Dvorak Dec 17 '13 at 20:19
  • \$\begingroup\$ @JanDvorak Any way to use it. It's a text version of the official scrabble dictionary, it seemed to be the most fitting word list for the task. "All words being found" might be hard, considering there are probably many combinations of words that would deplete all the tiles. It's a maximum of 25 words, (25 words, 4 letters each, 100 tiles), but I don't know if it's possible to use all tiles with just 4 letter words. After so many words, you might not have enough tiles to make an actual word, which means you'd either have to go back or accept that you're not using all the tiles. \$\endgroup\$ – Rob Dec 17 '13 at 20:23
  • 5
    \$\begingroup\$ As currently described, this is a no-input task, which means that the answer can be precomputed and then the program only needs to decompress it. Consider rewriting it to take input (either of the word list or of the tiles available). \$\endgroup\$ – Peter Taylor Dec 18 '13 at 8:01
  • \$\begingroup\$ I suggest taking a list of tiles as input, loading the list of words from a predefined file and requiring all combinations / best combination to be found. Of course, if the input is the full list of tiles, the computation is going to take ages. I might allow preprocessing the word list outside the program itself (up to a certain point; a linearithmic growth?) \$\endgroup\$ – John Dvorak Dec 18 '13 at 8:32
  • \$\begingroup\$ I suggest modifying this so that input is a list of tiles, limited to a full rack or less (therefore 4-7 tiles, since our minimum word length is 4). Input should be assumed to be valid based on the standard set of tiles (e.g.: it wont' have something like 3 J's or 4 G's). This would have some practical use for a player in a scrabble game to figure out their next move (though it does not take into account tiles available to them which are already on the board). \$\endgroup\$ – Iszi Dec 18 '13 at 21:14
  • \$\begingroup\$ Alternative mode: Input is a list of tiles, maximum 96 (so that at least 4 are remaining in the set). Output only includes words (minimum 4 letters) which can be created without those tiles. This would be interesting as it provides words that may yet be created (though, again, not taking into account usable tiles on the board) at a given point in the game. \$\endgroup\$ – Iszi Dec 18 '13 at 21:15
  • \$\begingroup\$ Output needs to be decided as either a list of all possible words, or only the highest-scoring word(s). Another enhancement may be to require that the list be sorted descending in order of score (if output is all words), then ascending alphabetically. There's no reason to take each program's output into account for scoring. Since everyone is expected to use the same dictionary, all programs' outputs should be identical (except perhaps in sorting, if that's left out of the spec). So, this should be Code Golf. \$\endgroup\$ – Iszi Dec 18 '13 at 21:15
  • \$\begingroup\$ It's also worth noting that, as currently written, the task could just be to filter the given dictionary down to words which have 4 or more letters. By its very nature, the Scrabble dictionary should already exclude any words that cannot be made with a Scrabble set. \$\endgroup\$ – Iszi Dec 18 '13 at 21:18
  • \$\begingroup\$ @Iszi it's not "what are all the words you can make", it's "what are all the words you can make, where every letter used depletes a tile". There's a max of 25 words if you can use all 100 tiles. \$\endgroup\$ – Rob Dec 19 '13 at 16:40
  • \$\begingroup\$ I think I misunderstood the problem, then. I thought it was "all the words possible using a set of tiles" not "all the words possible, using only one set of tiles". Still, my point about code golf remains. There is an absolute maximum to the number of words (each with 4 or more letters) you can make with a single Scrabble set, and a finite number of permutations which can be used to hit that maximum. Every program written with this goal should end up with the same (or nominally similar) output. \$\endgroup\$ – Iszi Dec 19 '13 at 16:56
0
\$\begingroup\$

Test for Irreducible Complexity (Check for Redundant Characters)

I may need some additional help coming up with the full spec for this competition. As of right now, this is just a concept.

Many interesting questions, such as the "42" question in this sandbox, involve finding the longest program which is not reducible. This means that no set of characters can be removed and still allow the program to function as desired.

The basic idea is that your program will test a Base Program to make sure that it contains no redundant characters. The input will consist of:

  • Base Program (in the same language as your answer)
  • Expected Output

Your program will simply evaluate all possible subsequences of the Base Program and verify that none of them give the Expected Output.

This challenge actually has a utility value to several other challenges. For example, it verifies the results of a "longest non-reducible"-type challenge. In addition, it could make sure that a golfed solution cannot be golfed further.

I assume that the winning criteria will be fastest program, as cycling through all the possibilities takes a long time.

Problems

A sequence of length N has 2^N subsequences. Even if each evaluation is done very quickly, it might be unfeasible to test any program with more than 20 or so characters in a reasonable amount of time.

| | | | | |
\$\endgroup\$
  • \$\begingroup\$ Problem: some subsequences of legitimate answers may be pretty dangerous to the environment. You don't want to eval just everything. \$\endgroup\$ – John Dvorak Dec 23 '13 at 16:59
  • \$\begingroup\$ @JanDvorak Yes that actually is a serious problem. To what extent is it possible to fix that? \$\endgroup\$ – PhiNotPi Dec 23 '13 at 17:04
  • 1
    \$\begingroup\$ Forbidding any program with dangerous subsequences? :-) \$\endgroup\$ – John Dvorak Dec 23 '13 at 17:05
  • 1
    \$\begingroup\$ A more reasonable (but very difficult) solution would be the requirement to implement a sandbox. \$\endgroup\$ – John Dvorak Dec 23 '13 at 17:07
  • \$\begingroup\$ Even without dangerous behavior, the halting problem will be an issue: it's hard to tell whether a shortened program will terminate at all, especially for every conceivable input. \$\endgroup\$ – MvG Jan 7 '14 at 23:49
0
\$\begingroup\$

Popularity Contest: Implementation of a Hash Table

Create a class in some OOP language for a hash table that supports getting, setting, and removing values. You can't use the built in hash table/dictionary/map implementation. Highest votes in one week wins.

A key is any valid string. A value is any valid string, number, or boolean.

Example functionality:

hash.set("key","value");
hash.get("key"); // returns "value"
hash.set("key", 1234);
hash.get("key"); // returns 1234
hash.set("key2",hash.get("key"));
hash.get("key2"); // returns 1234
hash.delete("key");
hash.get("key"); // returns null/undefined/none/etc. or throws an error
hash.get("key2"); // still returns 1234

Definition of a hash table (from Wikipedia):

In computing, a hash table (also hash map) is a data structure used to implement an associative array, a structure that can map keys to values. A hash table uses a hash function to compute an index into an array of buckets or slots, from which the correct value can be found.

The hash table cannot be simply an array that is searched in linear time. It must be an actual hash table that uses a hash function to map the keys to the value.

| | | | | |
\$\endgroup\$
  • 1
    \$\begingroup\$ Popularity contest and shortest don't mix. That aside, the spec is too vague. What is a "value"? What assumptions can be made about hashcodes? If the language makes all types nullable, should null be permitted as a key? What should the type be in languages which have co- and contravariance? And for that matter, what qualifies as a "hash table", bearing in mind that people will try to exploit any loophole? \$\endgroup\$ – Peter Taylor Jan 2 '14 at 23:16
  • \$\begingroup\$ @PeterTaylor Thank you for the feedback! Please see my edits, and let me know what you think. Could you meant about co/contravaraince? I looked at the wikipedia article about it but I'm not really sure how that has anything to do with this question. \$\endgroup\$ – hkk Jan 2 '14 at 23:37
  • \$\begingroup\$ I think it's still vulnerable to the loophole of "I have a hashtable with one bucket" (i.e. it's really a list of (key, value) pairs which I traverse in linear time). The thing about variance is to do with static typing of the elements of the map. E.g. in Java Map<String, Integer>'s get method has signature public Integer get(Object); in C#, a Dictionary<string, int>'s Get method has signature public int Get(string). The edited version makes it clear enough that the hashtable isn't expected to be genericised. \$\endgroup\$ – Peter Taylor Jan 3 '14 at 0:08
0
\$\begingroup\$

Wordlist detector

You are to write a program which, given a list of words, constructs a regular expression to match all these words but nothing else. Both your program and the constructed regular expressions are to be as short as possible.

Input and Output

Input comes on standard input and consists of one line giving n, the total number of words, followed by n lines with one word each. The number of words will be less than 1000, the length of each word less than 30. Words will consist only of lower case ASCII letters, i.e. a-z. You may choose to ignore the first line and use EOF instead to end the list.

Output shall be written to standard output. It consists of a single line, giving a POSIX extended regular expression to match these words and no others. Since input for this regex is not restricted to letters only, elements like . or [^…] won't make too much sense, which limits the language in a natural way. You may choose whether you want to terminate the line with a newline or not. Programs may choose to print multiple lines of output, in which case only the last one will be used for scoring. So you might print intermediate results and continue searching for improvements.

Test cases

Each submission may be accompanied by one regular expression. When scoring the submissions, I'll use this regular expression to reconstruct a word list from it. The code to do this reconstruction can be found at the end of this post. The reconstructed word list must fit the input specification above in terms of word count and length. It would be nice if your own program would be able to regenerate that regular expression from the word list, but that is not a strict requirement. But please don't paste bogus programs just to submit a challenging regular expression, though.

These test cases will be collected and fed to all programs for scoring.

Scoring

The final score of each program will be the program size plus the size of all its generated regular expressions for the inputs collected from submitted answers, including the example from this question. So short code which produces too long results might get beaten by longer code which generates shorter expressions.

Does this still qualify as ?

Submissions which generate an incorrect regular expression for one of the test cases will be disqualified, as will those which don't terminate in the allotted time. You can use the input reconstruction program below to check whether a produced regular expression does encode the correct word list.

Requirements

All submissions are welcome, but in order to include your submission in the tournament, it must be executable with reasonable effort on my Linux machine. It shouldn't depend on any exotic libraries, or any specialized ones which take too much work away from your own program. It must operate in reasonable time, say no more than five minutes per input. Your output must be reproducible, so if you use randomization at some point, please seed the randomizer, and please don't terminate an improove loop by a timer measuring execution time or some such.

Tournament times

I'll run the first major tournament two weeks after posting this question. I'll include a table of the results in this question. I'll try to run tournaments repeatedly as late submissions arrive, but I'll not promise any regular schedule.

Example

An very simple example application would be in Python 3 (53 chars):

print('|'.join(input() for i in range(int(input()))))

And here is a test case which could be posted along with the program, although this program obviously doesn't generate exactly this concise output:

bann?ana|ap(fel|ple)|s[ou]n|[hs](a|ou)nd

The expansion of that expression could be turned into the following example input, which need not be posted as part of an answer since it can be deduced from the regular expression:

10
banana
bannana
apfel
apple
son
sun
hand
hound
sand
sound

Regex expander program

And here is a program to turn regular expressions into word lists, again written in Python 3.

#!/bin/env python3
concat = set(('',))
altin = set(('',))
altout = set()
prev = None
stack = []
regex = iter(input())
for ch in regex:
    if ch == '(':
        stack.append((concat, altin, altout))
        altin = concat
        altout = set()
        prev = None
    elif ch == ')':
        concat.update(altout)
        prev, altin, altout = stack.pop()
    elif ch == '|':
        altout.update(concat)
        concat = altin
    elif ch == '[':
        ch = regex.__next__()
        cls = []
        while ch != ']':
            if ch == '-':
                crange = range(ord(cls[-1]), ord(regex.__next__()) + 1)
                cls.extend(map(chr, crange))
            else:
                cls.append(ch)
            ch = regex.__next__()
        prev = concat
        concat = set(w + c for w in prev for c in cls)
    elif ch == '?':
        concat.update(prev)
        prev = None
    elif ch >= 'a' and ch <= 'z':
        prev = concat
        concat = set(w + ch for w in prev)
    else:
        raise Exception("Illegal input")
if stack:
    raise Exception("Unclosed group")
concat.update(altout)
words = sorted(concat)
print(len(words))
print('\n'.join(words))

This is restricted to the part of regular expression syntax which I expect for this answer. If you have good reason to use something I did not consider, feel free to do so although I will likely have to update this code to cope with it. If you find a bug, please let me know.

| | | | | |
\$\endgroup\$
  • 1
    \$\begingroup\$ This is just Meta regex golf under the constraint that the two lists between them cover all possible words. Given that some people are tackling that existing question on that basis, this would qualify for closing as a duplicate. \$\endgroup\$ – Peter Taylor Jan 8 '14 at 8:45
1
46 47
48
49 50
95

You must log in to answer this question.

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