556
\$\begingroup\$

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

Sandbox FAQ

Posting

To post to the sandbox, scroll to the bottom of this page and click "Answer This Question". Click "OK" when it asks if you really want to add another answer.

Write your challenge just as you would when actually posting it, though you can optionally add a title at the top. You may also add some notes about specific things you would like to clarify before posting it. Other users will help you improve your challenge by rating and discussing it.

When you think your challenge is ready for the public, go ahead and post it, and replace the post here with a link to the challenge and delete the sandbox post.

Discussion

The purpose of the sandbox is to give and receive feedback on posts. If you want to, feel free to give feedback to any posts you see here. Important things to comment about can include:

  • Parts of the challenge you found unclear
  • Comments addressing specific points mentioned in the proposal
  • Problems that could make the challenge uninteresting or unfit for the site

You don't need any qualifications to review sandbox posts. The target audience of most of these challenges is code golfers like you, so anything you find unclear will probably be unclear to others.

If you think one of your posts requires more feedback, but it's been ignored, you can ask for feedback in The Nineteenth Byte. It's not only allowed, but highly recommended! Be patient and try not to nag people though, you might have to ask multiple times.

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

Other

Search the sandbox / Browse your pending proposals

The sandbox works best if you sort posts by active.

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

Get the Sandbox Viewer to view the sandbox more easily!

\$\endgroup\$
0

4041 Answers 4041

1
38 39
40
41 42
135
2
\$\begingroup\$

Decompress a Sparse Matrix (WIP)

The dual of this challenge.

Decompress a sparse matrix reversing the method here Compressed sparse row (CSR, CRS or Yale format).

There will be 4 inputs, either as separate variables or as a list of lists:

  • V, a list of the nonzero elements of the matrix in row-major form. This is of length NNZ (the number of nonzero elements in the original matrix)
  • NCOLS - the number of columns in the original matrix.
  • IA - a list that yields the number of nonzero elements in each row in the following way: IA[0] = 0, IA[i] = IA[i - 1] + <number of nonzero elements in row i>. The number of nonzero elements in row i is IA[i + 1] - IA[i].
  • JA - a list of the column indices of the elements in V, also of length NNZ. (zero-indexed)

Input will be a list of 3 lists and the number of columns in the original matrix, e.g. either

[
  [5, 8, 3, 6],
  [0, 0, 2, 3, 4],
  [0, 1, 2, 1],
  [4]
]

Or

V = [5, 8, 3, 6]
IA = [0, 0, 2, 3, 4]
JA = [0, 1, 2, 1]
NCOLS = 4

Output will be a decompressed matrix/list of lists:

[[0 0 0 0],
 [5 8 0 0],
 [0 0 3 0],
 [0 6 0 0]]

If your language doesn't support actual data structures, input and output may be text.

Process

  1. Create a 'matrix' of row width NCOLS.
  2. Populate the ith matrix row with N values from V if the corresponding array index (i + 1) of IA is non-zero, where N is the ith element of IA starting at the ith element of JA.
  3. repeat until V is empty
    i.e. above for the 0th matrix row IA[1] = 0, so this row has NCOLS=4 zeroes in it's first row. Then for matrix row 1, IA[2]=2 it takes 2 values from V starting at JA[1]=0. For matrix row 2, IA[3]=3 and IA[2]=2 so it takes the next (3 - 2 = 1) elements from V, starting at JA[2]=2. For matrix row 4 IA[4]=4 and IA[3]=3 so it takes the next (4 - 3 = 1) elements from V, starting at JA[3]=1.

Test cases

Input 1:

[ 5, 8, 3, 6 ]
[ 0, 0, 2, 3, 4 ]
[ 0, 1, 2, 1 ]
4

Output 1:

[[0 0 0 0],
 [5 8 0 0],
 [0 0 3 0],
 [0 6 0 0]]

Input 2

[ 10 20 30 40 50 60 70 80 ]
[  0  2  4  7  8 ]
[  0  1  1  3  2  3  4  5 ]
6

Output 2:

[[10 20 0 0 0 0],
 [0 30 0 40 0 0],
 [0 0 50 60 70 0],
 [0 0 0 0 0 80]]

Input 3:

[ ]
[ 0 0 0 0 ]
[ ]
3

Output 3:

[[0 0 0],
 [0 0 0],
 [0 0 0]]

Input 4:

[ 1 1 1 1 1 1 1 1 1 ]
[ 0 3 6 9 ]
[ 0 1 2 0 1 2 0 1 2 ]
3

Output 4:

[[1 1 1],
 [1 1 1],
 [1 1 1]]

Input 5:

[ 5, -9, 0.3, -400 ]
[ 0, 0, 2, 3, 4 ]
[ 0, 1, 2, 1, ]
4

Output 5:

[[0 0 0 0],
 [5 -9 0 0],
 [0 0 0.3 0],
 [0 -400 0 0]]

Assume inputs may contain any real number, you need not consider mathematical symbols or exponential representation (e.g. 5,000 will never be entered as 5e3). You will not need to handle inf, -inf, NaN or any other 'pseudo-numbers'. You may output a different representation of the number (5,000 may be output as 5e3 if you so choose).

Scoring

This is a , fewest bytes wins.

\$\endgroup\$
7
  • \$\begingroup\$ I'd suggest to at least briefly explain how the decompressing works in the post. The challenges should be self-contained as much as possible. \$\endgroup\$
    – Bubbler
    Apr 22, 2021 at 23:55
  • \$\begingroup\$ @bubbler, that's coming, but I need to figure out how to do that/explain it myself. I've left (WIP) on the question because of this. \$\endgroup\$ Apr 23, 2021 at 0:11
  • 1
    \$\begingroup\$ @Pureferret I think it would be better to allow only nonzero integers instead of any real number. It'd be easier for most languages that way \$\endgroup\$
    – user
    May 2, 2021 at 20:59
  • \$\begingroup\$ @user I think it's more interesting seeing those languages work around those difficulties. Also the original challenge required them, so it I my makes sense this one does too. \$\endgroup\$ May 2, 2021 at 21:14
  • \$\begingroup\$ @Pureferret I'm not sure many golfing languages support arbitrary precision floating point numbers. Would they be able to use strings, then? Edit: could you at least restrict it to rational numbers? Unlike Jon Skeet, most of us here don't know all the digits of pi :P \$\endgroup\$
    – user
    May 2, 2021 at 21:17
  • \$\begingroup\$ @user it needn't be arbitrary, just as long as it matches the test cases \$\endgroup\$ May 2, 2021 at 23:46
  • \$\begingroup\$ @Bubbler I think the process is correct? \$\endgroup\$ Jun 29 at 16:17
2
\$\begingroup\$

Round it up Nicely

When I work out, I often don't have a good plan for how many times to repeat an exercise, but in the interest of pushing myself I always keep going until I've done a "nice" number. Multiples of 5 are ideal, but multiples of 4 are acceptable too--unless they're 1 less than a multiple of 5, in which case I may as well do one more, or they're 1 more than a multiple of 5, in which case why didn't I already stop?

The challenge

Given an integer \$n\$ and a descending, pairwise coprime list of integers \$k_1, k_2, ..., k_m\$, output the least integer \$x \geq n\$ which is a multiple of some \$k_i\$ but is not 1 more or less than any multiple of any \$k_j\$ with \$j<i\$.

Test cases

n    k[1]...k[m]                        result
1    [5, 4]                             5
15   [5, 4]                             15
12   [5, 4]                             12
16   [5, 4]                             20
7    [5, 4]                             8
996  [5, 4]                             1000
1    [11, 7]                            7
15   [11, 7]                            22
133  [11, 7]                            140
1    [5, 3, 2]                          3
6    [5, 3, 2]                          10
6    [5, 3]                             10
11   [5, 3, 2]                          12
1    [100, 49, 9]                       9

Sandbox

  • Would it be more interesting without the descending/coprime guarantees?
  • Test cases are a WIP, but any additional suggestions?
  • Better title?
  • [How] should I note that the 1-above exclusion only matters if it would exclude the input itself? Should the task not be "rounding up" to make it more relevant?
\$\endgroup\$
2
  • 1
    \$\begingroup\$ the "dynamic goal" thing made me think it was going to be a challenge about determining how much excersize youd be doing in a given section, the sequence thing seems way out of left field and the requirements to be a workout number arbitrary, even in relation to the lore \$\endgroup\$ Feb 3 at 4:43
  • 1
    \$\begingroup\$ Could you please use words to describe the challenge? I do read quantifiers, but I suspect not all golfers do. \$\endgroup\$
    – pajonk
    Jun 30 at 6:25
2
\$\begingroup\$

Draw the Progress Pride flag

\$\endgroup\$
3
  • \$\begingroup\$ This is a really nice flag. It breaks one of the "golden rules of flag design" (no more than 3 colours) but that's the point. And harder to draw than it looks because you can't just draw a triangle for the brown and black. The spec is slightly inconsistent: the height calculated from the diagonal strip width is (340+170+170)*2 = 1360 which differs from the height calculated from the horizontal strip width 224 * 6 = 1344 so you might wat to fix that. \$\endgroup\$ Jun 24 at 21:04
  • 1
    \$\begingroup\$ I think the spec is reasonably clear but I have a few suggestions: 1. delete the word "obviously" - too patronizing. BTW this is covered by one of the standard loopholes here on Meta - it's always good to reference them. 2. So the minimum size is 1100 x 672? I recommend you state it explicitly rather than saying "only half" . "Exactly" is a strong word (especially when 170/sqrt 2 is actually 120.20815 ) - I recommend an error of 1 pixel. \$\endgroup\$ Jun 24 at 21:12
  • \$\begingroup\$ Thanks for the response I’ll fix this on Wednesday \$\endgroup\$
    – Oliver F
    Jun 26 at 19:01
2
\$\begingroup\$

Draw this fractal generated by applying Newton's method to cosh(x) - 1

\$\endgroup\$
1
  • 1
    \$\begingroup\$ ooh seems really fun \$\endgroup\$
    – mathcat
    Jul 1 at 18:13
2
\$\begingroup\$

Implement Binary Exponentiation

\$\endgroup\$
1
  • \$\begingroup\$ interestingly you can do the same thing with binary or peasant multiplication. actually any associative operation. \$\endgroup\$
    – qwr
    Jun 26 at 21:16
2
\$\begingroup\$

Is it an ordinal?

\$\endgroup\$
2
  • \$\begingroup\$ An interesting variation could be an open-ended-function sequence with the task being to generate every ordinal. Although I don't know if there would be a better way to answer that than smushing this decision problem and a "generate every ragged list" algorithm. \$\endgroup\$
    – pxeger
    Jun 30 at 10:54
  • \$\begingroup\$ @pxeger There's no way to generate every ordinal. There are uncountable ordinals, as well as countable but incomputable ordinals. \$\endgroup\$
    – Wheat Wizard Mod
    Jul 7 at 7:23
2
\$\begingroup\$

Draw the USA flag

\$\endgroup\$
1
  • 3
    \$\begingroup\$ "then your score is half of your program's length" is generally not welcomed here. \$\endgroup\$
    – tsh
    Jul 4 at 6:33
2
\$\begingroup\$

Generate a Tiefling's Traits

A Tiefling is a character race from Dungeons and Dragons, that have a list of possible traits:

  • small horns
  • fangs or sharp teeth
  • a forked tongue
  • catlike eyes
  • six fingers on each hand
  • goat-like legs
  • cloven hoofs
  • a forked tail
  • leathery or scaly skin
  • red or dark blue skin
  • cast no shadow or reflection
  • exude a smell of brimstone.

Given a list of Tiefling traits as input, randomly pick 1d4 + 1 (uniform distribution from 2-5) traits form that list and output them.

This challenge uses the standard definition of random, and the number and trait selection from the list must separately conform to definition 1 from here:

  • All possible [numbers] should be produced with the same probability;
  • All possible [traits] should be produced with the same probability;

You are allowed to pick randomly from the list by first shuffling it and taking the top 1d4+1 traits, so long as the shuffle does not favour any item in the list. Repeat selections if the same trait are not allowed.

Here is a non-golfed implementation in Javascript:

const dice = (n, s, a, doSum) => {
  const die = () => Math.floor(Math.random() * s) + 1;
  const dieResults = Array.from(Array(n)).map(each => {
    return die();
  });
  const sum = dieResults.reduce((sum, curr) => sum + curr + a, 0);
  // logging not required here
  console.log(`rolled '${dieResults.join(` + ${a}, `)} + ${a}${doSum ? ` = ${sum}`:''}'`);
  return doSum ? dieResults.reduce((sum, curr) => sum + curr + a, 0) : dieResults.map(each => each + a);
};

const shuffleSlice = (num, array) => array
  .map(value => ({
    value,
    sort: Math.random()
  }))
  .sort((a, b) => a.sort - b.sort)
  .map(({
    value
  }) => value).slice(0, num);

// you can take the list as a string or an actual list
const tieflingTraits = "small horns; fangs or sharp teeth; a forked tongue; catlike eyes; six fingers on each hand; goat-like legs; cloven hoofs; a forked tail; leathery or scaly skin; red or dark blue skin; cast no shadow or reflection; exude a smell of brimstone".split(/;\s+/);

// calling the function
console.log(shuffleSlice(dice(1, 4, 1, true), tieflingTraits))

// outputs like
//  ['goat-like legs', 'cast no shadow or reflection', 'a forked tongue']

This is so shortest in bytes wins.

\$\endgroup\$
4
  • \$\begingroup\$ Seems largely like a kolmogorov-complexity challenge, so maybe include that tag as well \$\endgroup\$ Jul 7 at 21:02
  • \$\begingroup\$ @mathjunkie It isn't, since you get the list as input \$\endgroup\$ Jul 18 at 4:01
  • \$\begingroup\$ Can we assume we will get this particular list, or should the program work in general for all lists? \$\endgroup\$ Jul 18 at 4:01
  • \$\begingroup\$ @CommandMaster you can assume you get that list \$\endgroup\$ Jul 18 at 8:30
2
\$\begingroup\$

Convert from Greeklish to modern Greek

\$\endgroup\$
4
  • 1
    \$\begingroup\$ I like natural language challenges, however it seems a bit boring. I feel like we must have a few challenges already that are a substitution cypher with digraphs, and it probably isn't really doing anything new there. \$\endgroup\$
    – Wheat Wizard Mod
    Jul 7 at 7:18
  • \$\begingroup\$ @WheatWizard I understand that character substitution challenges do exist in the site. However, from my search of the sandbox, there isn't one for Greek, so it's somewhat original. Therefore, I am considering to post this. If this goes any well, I will also consider posting a harder natural language Greek challenge ;) \$\endgroup\$
    – solid.py
    Jul 7 at 8:08
  • \$\begingroup\$ I just don't think that it being Greek actually makes the task any more interesting. Like it's neat, but the task is just a very simple substitution. If you have a harder challenge about Greek I'd say go with that one first. \$\endgroup\$
    – Wheat Wizard Mod
    Jul 7 at 8:26
  • \$\begingroup\$ @WheatWizard Since I made the effort to post and polish this a bit, I will post it. If it doesn't receive as much upvotes due to its unoriginality so be it. This site runs for many years and its hard to come up with something 100% original. Personally, I think its a solid challenge. Finally, I will also link to other related challenges, as I've seen quite recently on non-original challenges. \$\endgroup\$
    – solid.py
    Jul 7 at 8:41
2
\$\begingroup\$

Change the Temperature of Swatchlings

Warning: Contains Deltarune Chapter 2 Spoilers

Summary

Your challenge today is to determine the minimum number of turns needed to change the temperatures of an arbitrary amount of Swatchlings to all be the same.

Context

In the second chapter of Deltarune, there are enemies you encounter that are called Swatchlings (suit-wearing butler-like characters that serve the main antagonist of the chapter). These enemies always appear in battle in groups with at least one outlier in terms of suit colorsource. Swatchlings are defeated by making all Swatchlings in the group have the same suit colour.

Each Swatchling's color can be changed in stages, either becoming warmer (redder) or colder (bluer). While there are only five colours in the actual game, for this challenge, there will be an infinite amount, represented by positive integers.

During each turn of a battle, there are 3 ways to change the temperature of a Swatchling: increasing/decreasing the temperature by 2 stages, increasing the temperature by 1 stage or decreasing the temperature by 1 stage. You may perform up to 3 of these actions per turn, and no action twice in a turn.

Here's a video example of a Swatchling battle

Task and Worked Example

Given a list of Swatchling temperatures, determine the minimal number of turns needed to change the temperatures of all Swatchlings to be the same. Note that

For example, given the following temperatures:

[1, 5, 5]

The optimal solution would be:

Turn 1:
Increase Swatchling #1 by 2 stages: [3, 5, 5]

Turn 2:
Increase Swatchling #1 by 2 stages: [5, 5, 5]

Meaning a minimum of 2 turns are needed to change the temperatures of all Swatchlings to be the same.

Another example is:

[1, 5, 3, 4, 4, 2, 1]

One optimal solution might be:

Turn 1:
Increase Swatchling #1 by 2 stages: [3, 5, 3, 4, 4, 2, 1]
Decrease Swatchling #4 by 1 stage: [3, 5, 3, 3, 4, 2, 1]
Increase Swatchling #6 by 1 stage: [3, 5, 3, 3, 4, 3, 1]

Turn 2:
Decrease Swatchling #2 by 2 stages: [3, 3, 3, 3, 4, 3, 1]
Decrease Swatchling #5 by 1 stage: [3, 3, 3, 3, 3, 3, 1]

Turn 3:
Increase Swatchling #7 by 2 stages: [3, 3, 3, 3, 3, 3, 3]

Meaning a minimum of 2 turns are needed to change the temperatures of all Swatchlings to be the same.

Rules

  • Input will be a list of positive integers representing the temperatures of each Swatchling. The list will contain at least one Swatchling.
  • Output will be an integer representing the minimum number of turns needed to change the temperatures of all Swatchlings to be the same.

Test Cases

[1, 5, 5] => 2
[1, 2, 5] => 1
[1, 5, 3, 4, 4, 2, 1] => 3
[1, 7] => 2
[1, 10, 3] => 4

(More tests coming soon)

As this is , the aim of the game is to get y'all's byte count as low as possible, just like the turn count to make all the Swatchlings the same temperature.

Sandbox Meta

  • Is the explanation clear enough?
\$\endgroup\$
3
  • \$\begingroup\$ For your first case, can't you decrease #3 by 2, decrease it by 1 again, and increase #1 by 1? \$\endgroup\$
    – emanresu A
    Jul 2 at 0:09
  • \$\begingroup\$ @emanresuA huh, so you can. Just tested it in deltarune lol \$\endgroup\$
    – lyxal
    Jul 12 at 13:43
  • \$\begingroup\$ I'm assuming the line after the solution for [1, 5, 3, 4, 4, 2, 1] should say "Meaning a minimum of 3 turns are needed..." \$\endgroup\$ Jul 15 at 19:01
2
\$\begingroup\$

Solve a Card Suit Puzzle

\$\endgroup\$
2
\$\begingroup\$

Every possible pairing

\$\endgroup\$
1
  • \$\begingroup\$ Seems a little on the simple side I think. Might be a duplicate, but if it's not I think it's likely to score very well. :) \$\endgroup\$
    – Wheat Wizard Mod
    Jul 8 at 20:05
2
\$\begingroup\$

Infinite Fibonacci word

The famous Fibonacci sequence of integers is defined as follows:

\$ F_0 = 0 \\ F_1 = 1 \\ F_n = F_{n-1} + F_{n-2} \$

But what if we use this same recurrence relation to produce an infinite sequence of strings? Instead of addition, we'll use concatenation. We'll also change the base case slightly:

\$ F_0 = \$ 0
\$ F_1 = \$ 01
\$ F_n = F_{n-1}F_{n-2} \$

The first few strings are:

0
01
010
01001
01001010
0100101001001
...

Each of these "words" is a prefix of the next, so they are all prefixes of the single infinite word \$ F_\infty = \$

010010100100101001010010010100100101001010010010100101001001010010010100101001001010010010100101001...

Your task is to output this infinite string as a sequence; you may choose to use any two distinct values to use for 0 and 1.

As with standard challenges, you may choose to either:

  • Take an input \$ n \$ and output the \$ n \$th item in the sequence
  • Take an input \$ n \$ and output the first \$ n \$ item
  • Output the sequence indefinitely, e.g. using a generator

and you may use 0-based or 1-based indexing for \$ n \$.

This string can be defined in many different ways; its OEIS entry A003849 and Wikipedia page have more information.

Errors due to floating-point imprecision are not allowed.

This is , so the shortest code in bytes wins.

\$\endgroup\$
11
  • 1
    \$\begingroup\$ Seems very similar to the infinite quote escaping sequence \$\endgroup\$
    – mousetail
    Jul 15 at 13:05
  • 1
    \$\begingroup\$ It doesn't seem like it should be binary - 0 and 1 have no special meaning, they can be replaced by any symbol \$\endgroup\$ Jul 15 at 13:07
  • \$\begingroup\$ @mousetail Yes, in fact the Fibonacci word can also be formed using a string rewriting rule like the quote sequence. In this case it's replacing 0 with 01, and 1 with 0. \$\endgroup\$
    – pxeger
    Jul 15 at 13:11
  • \$\begingroup\$ This is a interesting challenge, however, of the 2 challenges I think the other one is slightly more interesting. \$\endgroup\$
    – mousetail
    Jul 15 at 13:13
  • 1
    \$\begingroup\$ @mousetail Who's to say we can't have both? I think they're definitely not duplicates, because both have multiple different approaches, only one of which somewhat overlaps. \$\endgroup\$
    – pxeger
    Jul 15 at 13:14
  • \$\begingroup\$ Fair enough, though I'd suggest to post it after the other challenge to acknowledge the inspiration \$\endgroup\$
    – mousetail
    Jul 15 at 13:24
  • \$\begingroup\$ @mousetail It was not deliberately inspired by that challenge at all. (Maybe subliminally, because I had seen that challenge perviously?). But I learnt about the Fibonacci sequence independently while browsing Wikipedia. \$\endgroup\$
    – pxeger
    Jul 15 at 13:26
  • \$\begingroup\$ I think you should specify if floating-point errors are allowed, since some approaches will probably use the golden ratio \$\endgroup\$ Jul 16 at 4:35
  • \$\begingroup\$ @CommandMaster I've added a note about that, but AFAICT there aren't any direct methods to make the string using φ \$\endgroup\$
    – pxeger
    Jul 16 at 7:43
  • 3
    \$\begingroup\$ Duplicate? \$\endgroup\$
    – pajonk
    Jul 16 at 8:57
  • \$\begingroup\$ @pxeger the OEIS entry says "a(n) = floor((n+2)*r) - floor((n+1)*r) where r=phi/(1+2*phi) and phi is the Golden Ratio." \$\endgroup\$ Jul 16 at 9:22
2
\$\begingroup\$

All Crossword Grids

In crossword terminology, the grid is the region into which the crossword answers are inserted, consisting of white and black squares. The crossword answers, called entries, are inserted into contiguous sequences of white squares in a row or column, separated by black squares.

Example of a crossword grid

For straight (American) crosswords, the grids usually follow a specific set of rules:

  • They should have 180 degree rotational symmetry (if there is a black square in the \$x\$th row and \$y\$th column, there should be a black square in the \$x\$th-to-last row and \$y\$th-to-last column).
  • All entries must be at least 3 squares long.
  • All white squares must be joined in a single region.
  • No row/column can be completely filled with black squares.

Some examples of invalid and valid crossword grids:

Valid and invalid crossword grids

Your challenge: given a grid consisting of two unique values representing black and white squares, determine if it's a valid crossword grid. Assume that it's a square grid with \$n\$ rows and columns (so there are \$n^2\$ white/black cells), where \$n \geq 3\$. For example, if \$n=3\$ there is only one valid grid (I'm using . for white cells and # for black cells):

...
...
...

If \$n=4\$, there are 3 valid grids:

....  #...  ...#
....  ....  ....
....  ....  ....
....  ...#  #...

If \$n=5\$, there are 12 valid grids:

.....  #....  ##...  #....  ##...  ##...  
.....  .....  .....  #....  #....  ##...  
.....  .....  .....  .....  .....  .....  
.....  .....  .....  ....#  ....#  ...##  
.....  ....#  ...##  ....#  ...##  ...##  

....#  ...##  ....#  ...##  ...##  #...#  
.....  .....  ....#  ....#  ...##  .....  
.....  .....  .....  .....  .....  .....  
.....  .....  #....  #....  ##...  .....  
#....  ##...  #....  ##...  ##...  #...#  

Examples:

Input Output Explanation
......... True Valid grid
#..............# True Valid grid
...#........#... True Valid grid
...#........#... True Valid grid
......... True Valid grid
#...#......#...# True Valid grid
......................... True Valid grid
##...#.............#...## True Valid grid
................................................. True Valid grid
........................#........................ True Valid grid
....###.....##......##.....##......##.....###.... True Valid grid
................................................................ True Valid grid
##....####....##...........##......##...........##....####....## True Valid grid
...##.......#...........##.....##.....##...........#.......##... True Valid grid
#............... False No 180 degree symmetry
#..##..##..##..# False 2-letter entries, filled-in columns
#........................ False No 180 degree symmetry
.......#...###...#....... False 1-letter and 1-letter entries
######....#....#....#.... False No 180 degree symmetry, filled-in column & row
######...##...##...###### False Filled-in columns & rows
...#......#......#......#......#......#......#... False White squares not contiguous, filled-in column
.................###....#....###................. False 1-letter entries
...#......#...............##..................... False No 180-degree symmetry
....#.......#.......#........######........#.......#.......#.... False White squares not contiguous
..#.........#.......#......##......#.......#.......#.........#.. False 1-letter and 2-letter entries
.#......#..............................................#......#. False 1-letter entries, white squares not contiguous
...........................##......#............................ False No 180-degree symmetry
####............................................................ False No 180-degree symmetry
#......##......##......##......##......##......##......##......# False Filled-in columns

Standard loopholes are forbidden. Shortest code wins.

Sandbox Questions

I may have misused some crossword terminology above, let me know if I can improve the explanation.

I also don't know if the final rule should be included, since it's not usually explicitly stated when constructing crosswords.

I'm considering adding an optional parameter \$n\$ which describes the number of rows/columns to make the input easier to parse, but I don't know how people feel about optional parameters.

\$\endgroup\$
4
  • \$\begingroup\$ Suggested tags: crossword, grid \$\endgroup\$
    – pajonk
    Jul 27 at 5:45
  • 3
    \$\begingroup\$ I don't see any clever algorithm for grid generation (that doesn't mean that there isn't one), so the answers are most likely use the brute-force method of generating all grids and checking their crosswordness - why not make it decision-problem then? \$\endgroup\$
    – pajonk
    Jul 27 at 5:51
  • \$\begingroup\$ @pajonk I've modified the question as per your suggestion, but that makes it very similar to a previously posed question, so I'm unsure about this. I think there are some meaningful shortcuts to make the generation easier. \$\endgroup\$ Jul 27 at 18:56
  • \$\begingroup\$ if you see shortcuts that make generation easier than brute-force, then ignore my previous comment. \$\endgroup\$
    – pajonk
    Jul 28 at 9:36
2
\$\begingroup\$

Add parentheses to Polish notation

\$\endgroup\$
4
  • \$\begingroup\$ Suggested test-case with multi-digit numbers. Also, are the numbers guaranteed to be positive? \$\endgroup\$
    – pajonk
    Aug 4 at 12:50
  • \$\begingroup\$ I think they should be limited to being positive. \$\endgroup\$ Aug 4 at 14:47
  • 2
    \$\begingroup\$ I'd suggest removing the edge case that extra trash at the end needs removed (such as the + 1 2 3 test case). Of course, it's your challenge, just a suggestion. I prefer sticking to the actual problem, and not adding extra edge cases. \$\endgroup\$
    – Steffan
    Aug 4 at 17:23
  • \$\begingroup\$ That was just a typo, sorry about that \$\endgroup\$ Aug 4 at 18:29
2
\$\begingroup\$

Change The Quotations as if in Microsoft Word

META: Posted

\$\endgroup\$
6
  • \$\begingroup\$ What to do with consecutive quotation marks? Or this won't ever be an input? \$\endgroup\$
    – pajonk
    Aug 7 at 15:17
  • \$\begingroup\$ I've added a rule for that. \$\endgroup\$ Aug 8 at 5:58
  • \$\begingroup\$ What will be the output for ''' and ''''? I other words, what is the precedence of the rules? \$\endgroup\$
    – pajonk
    Aug 8 at 6:02
  • \$\begingroup\$ I've edited the rule I just added to accommodate these strings. Check it out. \$\endgroup\$ Aug 8 at 6:08
  • \$\begingroup\$ How come makes a brief appearance in rule 5 and nowhere else? \$\endgroup\$ Aug 8 at 12:40
  • \$\begingroup\$ Oops, didn't delete that. \$\endgroup\$ Aug 12 at 7:39
2
\$\begingroup\$

Carry-less sum given a base b

posted

\$\endgroup\$
2
\$\begingroup\$

Are these numbers from the repeated application of this function?

Given a list of at least 3 positive integers \$L\$ and a function \$F\$ which takes a positive integer and returns a positive integer, determine if \$L\$ can be sorted such that each element of the list is the result of applying \$F\$ to the previous element (besides the first of course).

Rules

  • You may, of course, assume that \$F\$ always halts.
  • You may also assume that \$F\$ will have no side-effects and is deterministic.
  • You may take the \$F\$ as a black box function in any reasonable format.
  • Instead of taking \$F\$ as an input, you may take a second list \$M\$, which is the result of applying \$F\$ to each element of \$L\$.
  • This is , shortest solution in bytes wins.

Very simple worked out example

Inputting \$F(x)=x+1\$ and \$L=[5,4,3,2,1]\$ should output truthy, because \$L\$ can be rearranged into \$[1,2,3,4,5]\$, for which each element is the result of applying \$F\$ to the previous element: \$F(1)=2\$, \$F(2)=3\$, \$F(3)=4\$, and \$F(4)=5\$.

More examples:

Truthy

F(x) = 2x,           L = [4,2,1,8]
F(x) = ceil(10/x),   L = [2,2,2,5,5,5]
F(X) = 3x+1,         L = [5,16,49,148]
F(x) = length(x),    L = [1,2,10,9876543210,1]
F(x) = 13            L = [13,13,13,13,14]

Falsy

F(x) = 2x,           L = [2,4,6,8]
F(x) = ceil(10/x),   L = [5,2,5,2,5,2,5,5]
F(X) = 3x+1,         L = [5,16,8,4,2,1,4]
F(x) = length(x),    L = [3,1,10,2]
F(x) = 13            L = [13,13,13,14,15]

META

Is this ready to post or is it missing something / bad somewhere

\$\endgroup\$
7
  • 1
    \$\begingroup\$ You might want to clarify that black-box functions are allowed .See: 1 2 3 4 \$\endgroup\$
    – Steffan
    Aug 23 at 23:16
  • \$\begingroup\$ Almost certainly this has very little to do with functional programming (other than the fact that the program should take a function as input). On the other hand, there is a proposed guideline for decision problem outputs. \$\endgroup\$
    – Bubbler
    Aug 24 at 5:42
  • 1
    \$\begingroup\$ You can refer to these for black box function input methods. Currently the top two are accepted (predefined named functions and function arguments are both OK). \$\endgroup\$
    – Bubbler
    Aug 24 at 5:47
  • 1
    \$\begingroup\$ Is there a reason the function is part of the input, instead of the input being something like L[i], F(L[i])? \$\endgroup\$ Aug 24 at 11:32
  • \$\begingroup\$ @CommandMaster Interesting, I suppose that has about the same effect. I will probably edit this to allow both input formats, though I'll have to think about it \$\endgroup\$ Aug 24 at 12:31
  • \$\begingroup\$ Doesn't that trivialize the task though? It's just checking whether L[1:] == M[:-1] if I understand correctly. \$\endgroup\$
    – Steffan
    Aug 26 at 1:41
  • \$\begingroup\$ @Steffan you cant assume the order of the elements \$\endgroup\$ Aug 26 at 1:48
2
\$\begingroup\$

Implement level-index addition

\$\endgroup\$
2
\$\begingroup\$

Zip two arrays

Given a list of arrays of the same dimension, zip them at the lowest level. That is, you should output an array of the same dimension, for which the value at each index is a list of the corresponding elements in the input arrays.

For example, for two 3x3 arrays

[[123]  [[abc]    [[[1a][2b][3c]]
 [456] , [def]  →  [[4d][5e][6f]]
 [789]]  [ghi]]    [[7g][8h][9i]]]

and for the three 4x4 arrays

[[19  47  4   69 ]  [[103 67  17  28 ]  [[7   9   48  204]
 [156 120 54  104]   [167 80  99  62 ]   [26  125 230 212]
 [30  70  212 96 ] , [102 165 246 192] , [61  118 137 101]
 [62  80  152 205]]  [118 193 222 65 ]]  [125 247 209 31 ]]
 ↓
[[[19  103 7  ] [47  67  9  ] [4   17  48 ] [69  28  204]]
 [[156 167 26 ] [120 80  125] [54  99  230] [104 62  212]]
 [[30  102 61 ] [70  165 118] [212 246 137] [96  192 101]]
 [[62  118 125] [80  193 247] [152 222 209] [205 65  31 ]]]

Test cases

todo

Sandbox notes

  • This feels like something that should've already been posted.
  • Name/wording suggestions?
\$\endgroup\$
3
  • 1
    \$\begingroup\$ To me, it makes more sense to say "Zip arrays at the lowest level" or "Transpose array at the lowest level" or "Multi-dimensional transpose" instead of "Combine" \$\endgroup\$
    – Steffan
    Sep 1 at 0:20
  • \$\begingroup\$ It is one special case of APL dyadic transpose (challenge), and precisely BQN transpose. \$\endgroup\$
    – Bubbler
    Sep 1 at 0:27
  • \$\begingroup\$ @Bubbler Indeed ;) \$\endgroup\$
    – att
    Sep 1 at 0:53
2
\$\begingroup\$

This is less of a challenge proposal, and more of a idea for how to mesh the two title tags.

A series of targeted fights

Consider a heads-up, 1v1 "game" between two king-of-the-hill style bots. However, unlike a general king-of-the-hill, where every bot plays against every other bot, we instead build bots that target specific bots to win against. An example of an existing bot would be Low Blow from Cooperative Counting, which aimed to identify it's opponent, then play counter to that bot. However, in this challenge, the bot wouldn't have to identify its opponent: it would only play one bot, the bot it was designed to beat.

The aspect comes from this targeting:

  • User A posts Bot A, targeting a provided example bot.
  • User B then posts Bot B, targeting Bot A.
  • User C then posts Bot C, targeting a second example bot.
  • User D then posts Bot D, also targeting Bot A.

And so on, creating a "tree" of answers, each targeting a previous answer. Note that new answers don't have to target the latest, but can instead target any previous answer.

However, to prevent bots that "target", but don't actual perform well against their target, we'd need to require that it beats its target in \$X\%\$ of \$Y\$ battles, or else it is disqualified. Obviously, this prevents bots from being edited to improve themselves once targeted.

This begs the question: what is our scoring criteria? Clearly, depth from the root bots (provided in the challenge) must be a central part, as it's harder to create a bot the further down the chain you go. However, this doesn't differentiate between Bot B and Bot D in our example, despite the fact that Bot D beats Bot A \$82\%\$ of the time, vs Bot B's meager win rate of \$61\%\$. Clearly, we should take winning rate into account. One potential score:

$$\text{Score} = \text{Win rate} \times \text{Depth}$$

where \$\text{Win rate}\$ is between \$0\$ (never wins) and \$1\$ (always wins).


Thoughts?

\$\endgroup\$
2
  • \$\begingroup\$ I don't know if this is a legitimate concern, but I'd be worried about rock-paper-scissors-like loops where A is always defeated by B, B is always defeated by C, and C is always defeated by A. In that case, it would always be advantageous to post a counter to the most recent post of A/B/C, which means that the score could go to infinity while resulting in very uninteresting bots. You could limit this by saying "no repeat answers", and people probably wouldn't do this in practice because it's boring, but it points to a possible failure mode. \$\endgroup\$ Sep 10 at 17:53
  • \$\begingroup\$ @97.100.97.109 I don't think that's something to worry about. Ideally, the game would be designed such that, if Bot B beats Bot A the majority of the time, then, if Bot C defeats Bot B, it also must defeat Bot A. For example, in RPS, the "loop" style only occurs by defining the specific win/loss relationship. A 1v1 game with a points based scoring wouldn't encounter such a loop \$\endgroup\$ Sep 10 at 18:25
2
\$\begingroup\$

Solve a jigsaw puzzle

\$\endgroup\$
3
  • \$\begingroup\$ I am always in favour of loose I/O criteria, so I'd definitely include the first three dots and also leave up to answerers the value fir edges (not restricting to numbers, some may use NA or Inf, or even "a", but I'd keep it consistent). Anyway, I suggest placing the example between paragraphs 2 and 3 (so that I/O rules are after the example). Also, you may want to specify what to do with multiple solutions (if such inputs are possible). \$\endgroup\$
    – pajonk
    Aug 1 at 18:30
  • \$\begingroup\$ I have I feeling that I saw a challenge like this before, but I cannot find it. So maybe there isn't one. \$\endgroup\$
    – pajonk
    Aug 1 at 18:32
  • \$\begingroup\$ @pajonk I think this counts as a duplicate: codegolf.stackexchange.com/questions/48819/… \$\endgroup\$ Aug 23 at 16:54
2
\$\begingroup\$

write the "index by number" sequence

Imagine writing out positive integer numbers, and indexing each character in a 1-indexed array (indices read vertically on the top two rows, numbers read horizontally on the third):

000000000111111111122222222223333333333444444444
123456789012345678901234567890123456789012345678
one two three four five six seven eight nine ten

Now, imagine if we skipped some numbers so we write the index at the point we start the next number:

000000000111111111122222222223333333333444444444
123456789012345678901234567890123456789012345678
one five ten fourteen twenty three thirty six fo

now, imagine that the first number doesn't have to be "one":

000000000111111111122222222223333333333444444444
123456789012345678901234567890123456789012345678
      seven thirteen twenty two thirty three for

Input

A single number from 1..999, in any format you like ("1", '1', 1, "one" etc.)

This forms the starting number for the sequence

Output

A sequence of numbers, written long-hand in UK English ("one hundred and one" - no other differences), from (input)..(999) inclusive.

Code golf, usual rules.

\$\endgroup\$
9
  • \$\begingroup\$ 101 is "one hundred one" right? \$\endgroup\$ Sep 4 at 1:36
  • \$\begingroup\$ @thejonymyster one hundred and one \$\endgroup\$ Sep 5 at 6:33
  • \$\begingroup\$ Maybe you need include how to read number in UK English in your post. \$\endgroup\$
    – tsh
    Sep 9 at 9:40
  • \$\begingroup\$ @tsh updated to try and clarify \$\endgroup\$ Sep 9 at 10:15
  • 1
    \$\begingroup\$ 40 is "forty" in all standard English variants. \$\endgroup\$
    – pxeger
    Sep 9 at 12:14
  • \$\begingroup\$ @pxeger TIL. Corrected in spec. Thanks \$\endgroup\$ Sep 9 at 13:24
  • \$\begingroup\$ So we go up to the last number that starts before or exactly at 9999 even if it goes beyond 9999 once it's 'written'? 9999 is pretty high, btw. I think the challenge would be just as interesting but much easier to debug/verify with 999 (still high) or even 99 as the upper bound. \$\endgroup\$
    – Arnauld
    Sep 19 at 20:35
  • \$\begingroup\$ @Arnauld I don't want to end up creating an edge case that needs to be coded separately, so I'm happy to take guidance on how that would work - if the input is 9999 the output would be either nine thousand nine hundred and ninety nine or n (i.e. writing index #9999 then nothing above that) - which is better? Or best left optional? \$\endgroup\$ Sep 20 at 7:46
  • \$\begingroup\$ @Arnauld aside from that, I'll lower the bounds to 999 \$\endgroup\$ Sep 20 at 7:46
2
\$\begingroup\$

Generate a different sudoku


Task

Given a valid sudoku board, generate another sudoku board that isn't equivalent to the one inputted.

What do we consider as equivalent sudoku boards?

  • they are the same,
  • the digits are relabeled (eg. 2<->7 or 2->5->8->2),
  • three-column or thee-row bands are permuted,
  • the rows or columns within a band are permuted,
  • one is a reflection of the other (horizontally, vertically or along any of the diagonals),
  • one is a rotation of the other,
  • or any combination of the above.

According to Ed Russell and Frazer Jarvis there are 5 472 730 538 essentially different sudoku classes.

What is a valid sudoku?

(borrowed from here)

  • Each row contains the digits from 1 to 9 exactly once.
  • Each column contains the digits from 1 to 9 exactly once.
  • Each of the nine 3x3 subgrids contains the digits from 1 to 9 exactly once.

Rules

You may take input and output in any reasonable format, like a 9x9 matrix, list of rows/columns, a string of 81 digits etc.

Taking digits 0-8 instead of 1-9 is allowed, but please be consistent.

Test cases

Input:
7 2 5 8 9 3 4 6 1
8 4 1 6 5 7 3 9 2
3 9 6 1 4 2 7 5 8
4 7 3 5 1 6 8 2 9
1 6 8 4 2 9 5 3 7
9 5 2 3 7 8 1 4 6
2 3 4 7 6 1 9 8 5
6 8 7 9 3 5 2 1 4
5 1 9 2 8 4 6 7 3
Example output:
1 2 3 4 5 6 7 8 9 
4 5 6 7 8 9 1 2 3 
7 8 9 1 2 3 4 5 6 
2 3 1 5 6 4 8 9 7 
5 6 4 8 9 7 2 3 1
8 9 7 2 3 1 5 6 4 
3 1 2 6 4 5 9 7 8
6 4 5 9 7 8 3 1 2 
9 7 8 3 1 2 6 4 5

Input:

Example output:

Meta

  • Any mistakes in the test-cases?
  • Is it sufficiently diffent to existing challenges?
  • Is it better as or a challenge to check whether two given grids are equivalent?
\$\endgroup\$
6
  • \$\begingroup\$ I think the decision-problem version would be better, since that doesn't actually involve validating a sudoku board, which i believe is already a challenge. IMO anyway. \$\endgroup\$ Sep 21 at 19:51
  • \$\begingroup\$ Are there any other possible sudoku equivalencies? Or is it safe to say that's it / that's all we care about ? \$\endgroup\$ Sep 21 at 19:52
  • \$\begingroup\$ You might want to use the word "permuted" instead of "swapped" (I'm pretty sure that's what you mean) \$\endgroup\$
    – Pandu
    Sep 22 at 3:35
  • \$\begingroup\$ Since you were asking if you should do a related decision-problem question instead: In case you want it, here's another related question. I don't know it's that great is as is for CGCC -- feels so specific it's maybe too overspecified, but just in case it's useful: "Generate a specified equivalent sudoku given inputs originalSudoku, symbolPermutation, rowPermutations, columnPermutations, bandPermutation, stackPermutation, shouldReflect." Happy to elaborate on this if needed. \$\endgroup\$
    – Pandu
    Sep 22 at 3:56
  • 1
    \$\begingroup\$ @thejonymyster in the open-ended-function challenge I was hoping for a smart solution using some transformation not listed. These transformations are actually what pops up in literature (wikipedia link) - your previous comment prompted me to research this closer. But if it isn't a case, you're right that decision-problem may be better. \$\endgroup\$
    – pajonk
    Sep 22 at 4:33
  • \$\begingroup\$ @Pandu thanks for help in the wording. Regarding the challenge idea, I think you're right that it may be overspecified. \$\endgroup\$
    – pajonk
    Sep 22 at 4:35
2
\$\begingroup\$

Print every Fool's Mate

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

I've Got The Key, I've Got The Secret

A cryptography challenge in 2 parts.

Part 1

Implement a pair of programs in any language (the two programs could be in different languages if you wanted) to encode and decode a string of plaintext.

Input and Output

The encoder must take the plaintext (and an optional key) and return an encoded string. The decoder must take the cyphertext (and an optional key) and return the plaintext exactly as it was given to the encoder.

Restrictions

  • The encoding and decoding code must be entirely implemented in the language - no libraries or cryptography functions may be used.
  • The code (encoder+decoder) cannot be longer than 1024 characters.

Part 2

Implement programs (multiple programs per answer, one answer per entrant) which crack your opponents encryption algorithms.

Input

The cyphertext.

Output

The plaintext that generated the ciphertext.

Scoring

I will upvote all answers to part 1 which have working encryption and have obviously made an attempt at golfing their answer.

In order to be eligible to win, an entrant will have to have taken part in both parts of the question. Overall score will be (length of shortest program that cracks your code-(length of encoder+length of decoder)). Highest score wins and winning entrant's entries will be accepted on both questions.

\$\endgroup\$
10
  • 1
    \$\begingroup\$ The obvious place for this to fall flat on its face is if someone is able to implement AES or something similar within the 1024 character restriction. \$\endgroup\$
    – Gareth
    Jun 13, 2012 at 13:06
  • 1
    \$\begingroup\$ Probably better if the methods of the part one programs are disclosed in non-obfuscated language, though with the short length restriction this may not be necessary. \$\endgroup\$ Jun 13, 2012 at 15:23
  • 2
    \$\begingroup\$ Forget AES: RSA is easily doable. That aside, you need to define "crack" in part 2. \$\endgroup\$ Jun 13, 2012 at 15:35
  • 1
    \$\begingroup\$ Also, it's not clear whether "optional key" means that it's optional to make the algorithm unkeyed (doesn't make much sense, I admit) or optional to supply it, in which case it uses a default key. \$\endgroup\$ Jun 13, 2012 at 15:42
  • 1
    \$\begingroup\$ @PeterTaylor I just put optional in to leave it up to the implementer whether or not they wanted to have the key input or hard-coded (or use no key). I'd have thought everyone would have the key input into their program, but I didn't want anyone to feel forced into it by the spec. Hmm, if RSA is doable within the character restriction I'll end up with a load of unbreakable codes which would make for a pretty crap part 2. By crack I meant cyphertext goes in, some time later plaintext comes out. Would restricting the character count further help, or is this question beyond help? \$\endgroup\$
    – Gareth
    Jun 13, 2012 at 16:05
  • 3
    \$\begingroup\$ On that definition of crack, I can brute force for the length of the decoder plus a few bytes to iterate over all keys of the right length and some heuristics to check plausibility of the plaintext. The brute force cracker might even be shorter than the decoder if the decoder wasn't written in GolfScript... I think this question may be beyond help. \$\endgroup\$ Jun 13, 2012 at 16:28
  • 3
    \$\begingroup\$ @PeterTaylor Okay, thanks. I like the 'build your own - knock everyone else's down' aspect of this question though. I'll have to find another area where it could apply. \$\endgroup\$
    – Gareth
    Jun 13, 2012 at 16:34
  • 2
    \$\begingroup\$ @Gareth I too like the competitive nature of this idea. I'm looking forward to a question with this plan in mind! \$\endgroup\$
    – Gaffi
    Jun 13, 2012 at 19:31
  • 2
    \$\begingroup\$ I think it would be better to split this into a "cops" post and a "robbers" post. \$\endgroup\$
    – wizzwizz4
    Feb 16, 2017 at 9:46
  • 1
    \$\begingroup\$ @wizzwizz4 Wow, this is another blast from the past. I think this pre-dates the cops-and-robbers tag. I always seem to be ahead of my time. :-) \$\endgroup\$
    – Gareth
    Feb 16, 2017 at 9:49
1
\$\begingroup\$

Countability of Sets of Finite Sets

The aim of this challenge is to code-golf a program which returns an iterator that will iterate over all possible non-empty finite sets of positive integers.

So if running long enough, this iterator should eventually touch on {1}, {2, 5}, {3, 6, 112} (ie none of these should occur "at infinity")

You may choose the order in which you iterate over these sets, but the order must satisfy the following requirement:

Under a particular ordering, if S is the i'th set to be returned by the iterator, then we shall call i the index of set S.

Let a restriction (k,T) be an assertion about a set S that says S has size k and T is a subset of S.

For a given restriction (k,T) and iterator IT, let the restricted iterator be the iterator which takes sets returned by IT and filters out sets that don't satisfy the assertion, iterating only over the ones that do. In other words, if IT iterates over the sequence of all sets, the restricted iterator iterates over the subsequence satisfying (k,T). Now if S is the n'th set returned by the restricted iterator, then we'll call n the restricted index of S with respect to (k,T)

Your ordering must satisfy the property that for any restriction there exists a polynomial P(x) such that for any set satisfying the restriction (with index i and restricted index n), i < P(n)

Note that the following ordering is not acceptable:

{1} {2} {1, 2} {3} {1, 3} {2, 3} {1, 2, 3} {4} {1, 4} {2, 4}...

This is the sequence that comes from counting 1, 2, 3, 4, 5, 6... and listing the set bits in the binary representation of each number.

This is because the restriction (1, {}) satisfies only the sets {1}, {2}, {3}, {4}... whose index i as a function of their restricted index is i=2^(n-1) which is not bounded by any polynomial


Sandbox Questions

The reason for the strange requirement at the end is to disqualify any variants on the most natural ordering which simply counts upwards from 1 and enumerates the set bits in each number. In this ordering, the n'th set of length-one occurs at index 2^n which is non-polynomial.

I posted this problem originally, but didn't think of the obvious solution and so I left out the final restriction. I'd like to re-post it with the extra restriction. But first I'd like to know what people think. Is there a better way I can word that restriction or a more natural restriction I could impose instead?

\$\endgroup\$
4
  • 1
    \$\begingroup\$ I don't understand the extra restriction, so I can't suggest a rewording, but I can say that it needs one. (In particular: what is k? And what function does T serve? Is it really a parameter of the property?) \$\endgroup\$ Jun 18, 2012 at 8:25
  • 1
    \$\begingroup\$ I don't understand it either. Maybe a sample of an ordering, satisfying the requirement, and another one, violating it, would help. \$\endgroup\$ Jun 18, 2012 at 15:31
  • 1
    \$\begingroup\$ I understand the restriction now, although I haven't worked through the full implications. Does allowing T to be non-empty make a significant difference at all? \$\endgroup\$ Jun 19, 2012 at 6:52
  • 1
    \$\begingroup\$ I don't know. It may not. I guess the size part is the important part. I was just thinking that the ordering should be such that you run into all kinds of sets frequently. \$\endgroup\$
    – dspyz
    Jun 20, 2012 at 7:17
1
\$\begingroup\$

The One with Two Parts

The aim of this challenge is to create a pair of functions which scramble and unscramble any given piece of text.

Part 1

In part one you post your scrambling function, along with the length in characters and language of your unscrambling function (but NOT its code). The length of the scrambler does not affect your score so you needn't golf it unless you want to. The two functions may be written in different languages if you wish.

Input/Output

The scrambling function should take one argument only - a string containing the input text - and return a string containing the scrambled text. The unscrambling function should also take only one argument - the scrambled text - and return the original text. The input text will be limited to characters in the ASCII set range from 0 to 127.

Part 2

In part two you try to beat your opponents' scores for their unscrambling functions. You MUST use the language they specify for their unscrambler in part one. Please give just one answer to this question containing all your unscrambling functions making it clear which question in part one each function unscrambles (maybe each answer in part one should give its scrambler a name for identification?).

Once the closing date (TBA) has passed all participants should post their unscrambling functions in their answer to part one to prove the length, language and functionality of their function.

Scoring The participants score will be calculated as follows: (unscrambler length from part one) - (shortest unscrambler length from part two). The participant with the lowest score wins and will have their answers accepted on both parts of the challenge. To be eligible to win a participant must have taken part in both parts of the question.

Example

In part 1:

  • Bob posts a Python answer and says his unscrambler is a 165 character Python function.
  • Fred posts a GolfScript answer and says his unscrambler is a 59 character GolfScript function.
  • Joe posts a JavaScript answer and says his unscrambler is a 180 character PHP function.
  • Jim posts a Ruby answer and says his unscrambler is 163 character Ruby function.

In part 2:

  • Bob posts an 82 character GolfScript function to unscramble Fred's scrambled text. He also posts a 175 character PHP function to unscramble Joe's scrambled text.
  • Fred posts a 181 character PHP function to unscramble Joe's scrambled text.
  • Joe posts a 150 character Python function to unscramble Bob's scrambled text.
  • Jim posts a 156 character Python function to unscramble Bob's scrambled text. He also posts a 91 character GolfScript function to unscramble Fred's scrambled text.

The scores:

  • Bob scores 165 - 150 = 15
  • Fred scores 59 - 82 = -23
  • Joe scores 180 - 175 = 5
  • Jim scores 163 - 0 = 163

so Fred wins.

Miscellaneous

I suggest that the closing date be two weeks after the challenge begins, and that unscramblers be posted to part one within 48 hours of closing date in order to be eligible.

\$\endgroup\$
6
  • \$\begingroup\$ Are there any rules regarding scrambling? i.e. is "Stockholm"->"Stockhoml" a valid scramble? (it may not matter, but I'm curious. And to be clear, the scoring is the difference between your opponent's unscrambler length and your own for the same language? \$\endgroup\$
    – Gaffi
    Jul 16, 2012 at 16:39
  • \$\begingroup\$ @Gaffi No, you scramble however you want. If you want to just output the text as given that's ok, but you probably won't win with that strategy. The aim is to do it in a way that is easy for you to unscramble but difficult for all the others. That way your score will be smaller. Yes, the score is the difference between your score and the score of the best of your opponents' attempts. I'll add an example to make that bit clearer I think. \$\endgroup\$
    – Gareth
    Jul 16, 2012 at 21:27
  • \$\begingroup\$ I think this gives an advantage to people who use (relatively) obscure languages. If the scrambler is written in J and the descrambler in GolfScript then only people who know both can realistically attempt a descrambler. (NB the rules don't say how the score works if no-one attempts a particular unscrambler). \$\endgroup\$ Jul 17, 2012 at 6:59
  • \$\begingroup\$ I did consider saying that programs that had no attempts at beating them were not eligible to win, but then I thought that if they were scored as though the shortest attempt to beat them was 0 then they wouldn't have much of an advantage. I'll add that into the example scoring. What do you think? I want to encourage answers that are clever or well obfuscated rather than written in Malbolge or something like that. \$\endgroup\$
    – Gareth
    Jul 17, 2012 at 7:28
  • 1
    \$\begingroup\$ Does it mean that since no one attempts to solve Jim's Ruby challenge his chances are minimal that he'll win? That would discourage complicated scramblers or difficult languages. \$\endgroup\$
    – Howard
    Jul 17, 2012 at 17:12
  • \$\begingroup\$ @Howard As it stands, yes that's how it would work. The alternative, as Peter Taylor points out, is that people using obscure languages have an advantage. I'm not sure how else I might score unscramblers that no-one has attempted to beat. Maybe give them a score of 0? Please, if you or anyone else has any suggestions for making the challenge as inclusive as possible, let me know. \$\endgroup\$
    – Gareth
    Jul 17, 2012 at 17:51
1
\$\begingroup\$

Compile BF to TM

Your task is to write a compiler accepting a Brainfuck program (previous challenge: Interpret Brainfuck, wikipedia: Brainfuck) as input and outputting a Turing Machine which produces identical output when supplied with the same (correct) input.

You may select the output format from among the various formats accepted by the answers to Turing Machine Simulator.

The following links may also be useful.
An introduction to programming in BF
BF is Turing-complete
Programming a Turing Machine
Programming Praxis: Turing Machine Simulator

Equivalently, you may write a Brainfuck interpreter in TM, or any partial compilation/interpretation which results in a TM program as described above.

If we consider squares of the TM tape to represent bits (blank=0, mark=1) of the BF memory, then eight squares represent a cell. Each BF instruction translates to a minimum of 8 states of the Turing Machine.

'>' "advance" (++ptr) could be implemented by eight states (sixteen transitions):

adv8 _ adv7 R _
adv8 1 adv7 R 1
adv7 _ adv6 R _
adv7 1 adv6 R 1
adv6 _ adv5 R _
adv6 1 adv5 R 1
adv5 _ adv4 R _
adv5 1 adv4 R 1
adv4 _ adv3 R _
adv4 1 adv3 R 1
adv3 _ adv2 R _
adv3 1 adv2 R 1
adv2 _ adv1 R _
adv2 1 adv1 R 1
adv1 _ link R _
adv1 1 link R 1

where 'link' represents the first state of the following instruction.

'<' "rewind" (--ptr) can be implemented similarly by making leftward movements and rewriting the same symbol just read.

'+' "increment" (++*ptr) can be implemented by a ripple-carry from the Least Significant Bit to the Most Significant Bit, borrowing "rewind" states to back-up to normal position. If the LSB is on the left, it would look something like this:

inc8 _ link N 1
inc8 1 inc7 R _
inc7 _ rew1 N 1
inc7 1 inc6 R _
inc6 _ rew2 N 1
inc6 1 inc5 R _
inc5 _ rew3 N 1
inc5 1 inc4 R _
inc4 _ rew4 N 1
inc4 1 inc3 R _
inc3 _ rew5 N 1
inc3 1 inc2 R _
inc2 _ rew6 N 1
inc2 1 inc1 R _
inc1 _ rew7 N 1
inc1 1 overflow N 1

where overflow is a HALT state.

For I/O, the simplest way I can think is to place all input on the tape after the memory area, and expand the alphabet to include a symbol indicating the dividing line between the memory portion and the input portion of the tape. In fact, by expanding the cell size to nine squares, this symbol can serve as an input pointer, advancing as the input is consumed. (So "advance" and "rewind" now need 9 states each.) And another new symbol is written in front of the current memory cell to serve as the memory pointer. Inputting a byte therefore consists of schleping each bit over the entire space between the two tape positions with something like this:

input _ set-memptr L _
input 1 set-memptr L 1
set-memptr _ find-inptr R *
find-inptr _ find-inptr R _
find-inptr 1 find-inptr R 1
find-inptr $ schlep-bit R $
schlep-bit _ schlep-blank L _
schlep-bit 1 schlep-one L 1
schlep-blank $ schlep-blank L $
schlep-blank _ schlep-blank L _
schlep-blank 1 schlep-blank L 1
schlep-blank * deposit-blank R *
schlep-one $ schlep-one L $
schlep-one _ schlep-one L _
schlep-one 1 schlep-one L 1
schlep-one * deposit-one R *
deposit-blank _ etc R _
deposit-blank 1 etc R _
deposit-one _ etc R 1
deposit-one 1 etc R 1

where "etc" represents going to get the next bit in similar fashion.

To perform a loop (all BF loops are "while" loops, so the exit control is at the beginning and the end has a simple goto back to the beginning), we need first to check is the current cell is zero,

zero8 _ zero7 R _
zero8 1 body R 1
zero7 _ zero6 R _
zero7 1 left1 L 1
zero6 _ zero5 R _
zero6 1 left2 L 1
zero5 _ zero4 R _
zero5 1 left3 L 1
zero4 _ zero3 R _
zero4 1 left4 L 1
zero3 _ zero2 R _
zero3 1 left5 L 1
zero2 _ zero1 R _
zero2 1 left6 L 1
zero1 _ exit-loop R _
zero1 1 left7 L 1
left7 _ left6 L _
left7 1 left6 L 1
left6 _ left5 L _
left6 1 left5 L 1
left5 _ left4 L _
left5 1 left4 L 1
left4 _ left3 L _
left4 1 left3 L 1
left4 _ left3 L _
left4 1 left3 L 1
left3 _ left2 L _
left3 1 left2 L 1
left2 _ left1 L _
left2 1 left1 L 1
left2 _ loop-body L _
left2 1 loop-body L 1
...
loop-body-final _ zero8 N _
loop-body-final 1 zero8 N 1

So assuming the machine starts at tape-location 0, and the input is on the tape starting at 0 and going to the right, the "startup code" for this arrangement would be

startup _ place$ L _
startup 1 place$ L 1
place$ _ left270000 L $
left270000 _ left269999 L _
...

Jeez! The output is going to be HUGE! It might be better to treat the BF memory as negative-indexed and reverse all the _L_s and _R_s in 'advance', 'rewind', 'increment', and 'decrement'.


Questions:

Bonuses for optimizations? If I can implement this myself and provide a complete example output, The bonus could be "subtract the difference between your program's output for the example input with the example output". So eliminating states would be far more valuable than shrinking the code. One could possibly achieve a negative score!


Edit: Actually I think this is unreasonable unless the Turing Machine is augmented with non-reading (movement-only or epsilon) transitions. Duplicating every letter of the alphabet just to move over one square is just ridiculously painful. That means this challenge won't link-up nicely with the other one. :(

What about, instead of implementing the compiler, just devise a translation scheme (as above) that leads to a smaller output for a trivial sample program (based on calculating, rather than coding)? "Back of the envelope" compiler.

\$\endgroup\$
8
  • \$\begingroup\$ "How much detail on BF do I need to supply? Can I simply reference the BF question?" A link to almost any site that describes the language will do. \$\endgroup\$ Nov 5, 2012 at 16:52
  • \$\begingroup\$ Winning condition? \$\endgroup\$ Nov 6, 2012 at 13:43
  • \$\begingroup\$ "Longest prefix containing syntactically-correct Malbolge!" :) ... I'd say have none at all. Perhaps the questioner should be required to accept their own example answer? \$\endgroup\$ Nov 6, 2012 at 18:08
  • \$\begingroup\$ @PeterTaylor Apologies for my last comment. I thought we were on my other answer about the [fun] tag. . . . This one would be a golf: shortest code by character count. But I think a clever system of bonuses could make it interesting. \$\endgroup\$ Nov 7, 2012 at 10:06
  • \$\begingroup\$ The "Equivalently, you may write a Brainfuck interpreter in TM" option doesn't play very well with being a code golf - how are you going to count the length of the TM? \$\endgroup\$ Nov 7, 2012 at 11:15
  • \$\begingroup\$ @PeterTaylor Since the TM question specified 5-tuples, I think it's sufficient to count the tuples (== transitions). You can reduce states by increasing the alphabet (or vice versa), but the transitions would remain constant, I think. \$\endgroup\$ Nov 8, 2012 at 5:25
  • \$\begingroup\$ I'd like to adopt (work on and post) this challenge if you don't want to. Would I be able to? If you do not respond to this message within two weeks, by community guidelines, I am allowed to take it over. \$\endgroup\$
    – MD XF
    Aug 18, 2017 at 3:23
  • \$\begingroup\$ Yes, please. If you can do something with it, strike while the iron is hot. \$\endgroup\$ Aug 18, 2017 at 4:19
1
\$\begingroup\$

Graphical Output -- Esoteric Artifacts -- The Glass Bead Game

Draw the Cabalistic Tree of Life

Simply described, the Tree of Life is an undirected network of nodes representing the conduit between matter and higher forms of spiritual energy. It has an upper face arranged in a hexagon, and a lower fact built from equilateral triangles adjacent to the lower two edges of the upper face. Don't label the paths, paths may overlap however you wish, may be single (thick) lines, even. Code Golf. Bonus -100 for labels on the Sephiroth (nodes); Bonus -150 for Hebrew labels.

Tree of Life after Kirtcher

Draw a Mandala for each Natural Number

Draw a circle with interesting visual patterns using the input N [ 1 .. \inf ) to determine the number of points around the circle to anchor figures whose shape is also modified by the input N. Actually, 12 seems like a good max: they're pretty much a blur after that no matter what.

Eg. http://code.google.com/p/xpost/downloads/detail?name=ve6a.ps
//lotsoflines n = 1 ..12

Mandalas 1 - 12

(doesn't need to be this elaborate, This is >600 lines of showing-off.).

. . . need good images for these . . .

Draw the Ptolemeic System of the Universe

All the stuff I could find is animated already. Maybe this one's done-to-death. :(

Update: Found good stuff on Alchemy. The "Keplar Platonic" model could be fun (3D and all). This one looks good, too. And this.

Draw the Pythagorean Monochord

aka pre-classical nomogram. I misplaced my Pythagoras books, I know I've got a picture somewhere.

This is the one I was thinking of.

But I think this one's even cooler

Draw the I-Ching Hexagrams in King Wen Sequence.

I suppose I need to implement this first to avoid copyright issues! :)

\$\endgroup\$
3
  • \$\begingroup\$ The I-Ching one would have to be in standard order to be remotely interesting, and then becomes as much about kolmogorov-complexity as graphical-output \$\endgroup\$ Nov 22, 2012 at 21:24
  • \$\begingroup\$ For the others: images, please! \$\endgroup\$ Nov 22, 2012 at 21:25
  • \$\begingroup\$ I've emailed the owner of the Alchemy pages asking for permission to use his copyrighted images. Awaiting response. \$\endgroup\$ Jan 28, 2013 at 8:25
1
38 39
40
41 42
135

You must log in to answer this question.

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