571
\$\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".

\$\endgroup\$
1
  • \$\begingroup\$ What if I posted on the sandbox a long time ago and get no response? \$\endgroup\$
    – None1
    May 15 at 14:05

4689 Answers 4689

1
45 46
47
48 49
157
2
\$\begingroup\$

Idea:

Given a polyomino shape figure out the minimum number of cuts required to fill it with a herring-bone pattern of 2×1 tiles.

Gylda is a contractor who installs decks. She receives the deck plan from an architect who always chooses it to be shaped as a polyomino, that is a single connected piece cut from a square grid. The deck surface is manufactured in 2×1 rectangular tiles. Gylda installs the tiles in a herringbone pattern because it looks nice, and is stable. However not all shapes can be made perfectly with a herringbone pattern, sometimes Gylda is forced to cut a tile in half. Sometimes Gylda is forced to cut a lot of tiles in half. However how many cuts are needed, depends on exactly where the pattern is placed relative to the boundaries of the deck.

Now Gylda wants to minimize the number of cuts she has to make so she wants a computer program which will take a deck shape and will tell her the minimum number of cuts required. This is the number of cuts, not the number of half pieces used in the final construction. Each cut produces two 1×1 pieces which can both be used.

There is one catch. If a herringbone pattern would produce a layout where two half pieces are adjacent by an edge, Gylda will instead place a single 2×1 tile, even though it breaks the herringbone pattern. For example in the following layout:

 ====||
 ||====
 ||||==

There are two half pieces in the bottom right so instead we would lay out a single whole piece:

====||
||====
||====

This means the 3×3 square polyomino only requires 1 cut, not 2.

Gylda wants the program to take this special rule into account.

Task

Take a polyomino as input in any reasonable format. Output the minimum number of cuts Gylda needs to install that deck.

This is so the goal is to minimize the size of your source code as measured in bytes.

\$\endgroup\$
2
  • \$\begingroup\$ It would be helpful if you could define a herringbone pattern, and highlight the tiles in the example. \$\endgroup\$ Mar 18, 2023 at 7:53
  • \$\begingroup\$ @CommandMaster Yeah, this challenge is unfinished right now, so it's missing a deal of the specification. \$\endgroup\$
    – Wheat Wizard Mod
    Mar 18, 2023 at 15:42
2
\$\begingroup\$

Isolate the binary signals

There are n binary signals, with intervals of 1 through n. For example, for n=3 the lists could be [1], [0, 1], [1, 0, 1]. Each list represents a repeating pattern. So [0,1] is really [0, 1, 0, 1, 0, 1, ...]

The signals all start at the same time, but they are sent over the same channel. So you only know the sum of all the signals at a given time.

Given a list of length at least LCM(1..n) representing the sum of the values at each item of each signal.

If there are multiple possible options, you may output any of them.

Test Cases

List n Expected Result
[1, 3, 1, 2, 2, 2] 3 [1], [0,1], [1,0,1]
[2, 3, 3, 3, 1, 4, 3, 2, 2, 4, 2, 3] 4 [[1], [0, 1], [1, 0, 1], [0, 1, 1, 0]]
\$\endgroup\$
1
  • \$\begingroup\$ Is n part of the input? Or can you output any valid n as long as LCM(1..n) isn't greater than the input length? \$\endgroup\$ Mar 23, 2023 at 8:32
2
\$\begingroup\$

Draw the GKMS aperiodic tile

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

Play Rock Paper Scissors 25

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

Make a Custom Bayer Matrix

\$\endgroup\$
6
  • \$\begingroup\$ I think this part "successive numbers are as distant from each other as possible" needs more precise definition, as it's the main part of the challenge, as I get it. Also, as the input will be only 2,4,8 or 16, there is possibility that some approaches will just hardcode the outputs (no judgment, maybe it's intended). \$\endgroup\$
    – pajonk
    Feb 8, 2023 at 17:16
  • \$\begingroup\$ @pajonk I will try to make that part more clear. Yes, there is the option of hardcoding the output, but I would expect that in most programming languages that would not be the shortest possible answer. \$\endgroup\$
    – Yousername
    Feb 8, 2023 at 22:45
  • \$\begingroup\$ Is [0 3;2 1] valid? \$\endgroup\$
    – l4m2
    Feb 10, 2023 at 9:14
  • \$\begingroup\$ @l4m2 As long as your output format stays consitent with orher inputs, yes. \$\endgroup\$
    – Yousername
    Feb 10, 2023 at 14:07
  • \$\begingroup\$ It's not format, it's order when tie distance \$\endgroup\$
    – l4m2
    Feb 10, 2023 at 20:48
  • \$\begingroup\$ @l4m2 Yes, that is allowed (the third rule). \$\endgroup\$
    – Yousername
    Feb 10, 2023 at 21:10
2
\$\begingroup\$

Selection and Prediction

Your challenge: to select the strings A and B and predict others' selections in an -style .

All entries should be Python 3.10ish META: version? also possibly JS if I have time ._..

Part 1: Selection

You are tasked with selecting the strings A and B as randomly as possible. You are given the previous selections you have made and the guesses your 'opponent' has made. Each input is a string of A and B. For example, 'ABBAB' and 'ABABA' may be arguments passed to your program.

Your program should output either of A or B deterministically, meaning the same input should result in the same output. This means no calling random.choice() or similar, or using the date and time as seeds for a random number generator. META: maybe I should choose the first letter for them, since this constraint results in them always starting with the same letter You may also output a tuple (letter_str, state) and the state will be passed in as a keyword argument next round.

An example entry (this will compete):

Selector: AAAAAA, 3 bytes

Not much to say. This program loves the letter A

def aaaaaa(selections, guesses):
    return "A"

Part 2: Prediction

Your task is to predict the most likely move that your opponent will make. Same input, output and constraints as above.

Another example entry: (this will compete too)

Predictor: Anti-repeater, 3 bytes

Assumes you tend to repeat your previous selection.

def anti_repeater(selections, guesses):
    # It's fine to modify the lists
    return selections.pop()

Part 3: Scoring

Each Selector submission will go against each Predictor submission for a total of 110 rounds. They will select and predict for the first round, then select and predict again, and again, until all rounds have finished.

For each round correctly predicted (excluding the first 10 rounds, since they may be hard to predict) the Predictor submission wins 1 point. For each round incorrectly predicted (also excluding the first 10 rounds) the Selector submission wins 1 point.

The winners are the submissions with the most total points from all Selector and Predictor submissions. Since there are two winners no answer will be accepted.

If you type hint you get 0 extra points. my respect!

(Part 4: meta)

EDIT: added scoring

What do you call a where every cop goes against every robber and vice versa?

EDIT: Change 'key' to 'string' and fix up typo

EDIT: Some other stuff added

\$\endgroup\$
7
  • \$\begingroup\$ How will submissions be scored? \$\endgroup\$
    – mousetail
    Dec 18, 2022 at 12:06
  • \$\begingroup\$ It's a KOTH - they go against each other \$\endgroup\$
    – W D
    Dec 18, 2022 at 19:56
  • \$\begingroup\$ Who wins the KOTH though? \$\endgroup\$
    – mousetail
    Dec 18, 2022 at 20:26
  • \$\begingroup\$ forgot that >_< Added now \$\endgroup\$
    – W D
    Dec 19, 2022 at 20:33
  • \$\begingroup\$ Isn't it supposed to be random.choice()? \$\endgroup\$ Dec 20, 2022 at 12:57
  • \$\begingroup\$ Thanks @UndoneStudios don't know how I missed that \$\endgroup\$
    – W D
    Dec 20, 2022 at 23:00
  • \$\begingroup\$ Maybe you can allow seeded random.choice() as it still deterministic . \$\endgroup\$
    – tsh
    Jan 4, 2023 at 3:30
2
\$\begingroup\$

Posted

\$\endgroup\$
2
  • \$\begingroup\$ It's not exactly clear to me which doors are opened by which guards. I see the example of "i, 2, i..." but that doesn't form a clear pattern to me and I'm not sure why i is listed twice. \$\endgroup\$
    – Bbrk24
    Apr 1, 2023 at 15:16
  • \$\begingroup\$ @Bbrk24 Yes, make it more clear! \$\endgroup\$
    – lesobrod
    Apr 1, 2023 at 16:53
2
\$\begingroup\$

Enumeration of free polyominoes

Posted here

\$\endgroup\$
4
  • 2
    \$\begingroup\$ What makes a polyomino "free"? \$\endgroup\$
    – Bbrk24
    Mar 17, 2023 at 18:47
  • 3
    \$\begingroup\$ What is a "rigid transformation"? Is it an isometry, an orientation preserving isometry, a translation, something else ...? \$\endgroup\$
    – Wheat Wizard Mod
    Mar 17, 2023 at 23:16
  • 1
    \$\begingroup\$ @Wheat Wizard hope it's more clear now \$\endgroup\$
    – math scat
    Mar 18, 2023 at 7:55
  • \$\begingroup\$ I suggest listing drawings/ascii art of the polyominoes for the first few n. \$\endgroup\$
    – pajonk
    Mar 19, 2023 at 9:23
2
\$\begingroup\$

Shortest Path Around Obstacle

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

The number of solutions to Hertzsprung's Problem

Tags:

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

Generate a random finite floating-point number

Your challenge is to write a program or function that when invoked outputs a IEEE float32 value.

  • Any particular floating point value may not have more than a chance of 1 in 1,000,000,000 of being output. (There are 4,278,190,079 possible different outputs so this should not be too onerous a restriction.)
  • You may convert the float32 value to double precision or a reasonable string format, but e.g. -0 and 0.0 count as the same float value, and JavaScript's Math.random would not be acceptable as it can only generate a few million different float32 values - indeed the number of different values it generates that truncate to the same float32 value is greater than the number of different resulting float32 values.

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

\$\endgroup\$
3
  • \$\begingroup\$ Are nan and +-inf float values? \$\endgroup\$
    – AndrovT
    Apr 20, 2023 at 9:10
  • \$\begingroup\$ @AndrovT Should I have repeated the word finite? \$\endgroup\$
    – Neil
    Apr 20, 2023 at 13:01
  • \$\begingroup\$ I don't know how I missed that. \$\endgroup\$
    – AndrovT
    Apr 20, 2023 at 13:29
2
\$\begingroup\$

Find the Geometric Mean of a set of Numbers

Introduction

There isn't a geometric mean challenge here yet so I decided to post one.

Challenge

Calculate the geometric mean of a set of numbers without using a built in function for it because that's boring.

  • See here for input and output methods.
  • Input should be some sort of set of numbers (either as a list/array passed to a function or a list/array built by the program from user inputs).
  • You do not need to cope with negative numbers.

The winner will be determined by the shortest (functional) code length in bytes, in the case of 2 answers having the same number of bytes then the winner will be determined by score.

Example Input and Output

Input Output
[2,2,2] 2.00 or 2
[1,2,3] 1.82
[0,5,4,7] 0.00 or 0
[8,5,4,7] 0.79
[1.7,2,0.3] 1.00 or 1
[3,8] 4.9 or 4.90
[12,21] 15.87
[0.5] 0.5, or 0.50
[3,9,2,5,7] 4.52

Ungolfed Desmos example program:

f\left(l\right)=\sqrt[\operatorname{length}\left(l\right)]{\prod_{i=1}^{\operatorname{length}\left(l\right)}l\left[i\right]}
\$\endgroup\$
5
  • 2
    \$\begingroup\$ Consider defining what the geometric mean is for anyone unfamiliar \$\endgroup\$
    – emirps
    May 2, 2023 at 20:12
  • 5
    \$\begingroup\$ Banning Builtins is hard to enforce, I'd recommend allowing them, but encouraging non-builtin solutions to be included aswell. \$\endgroup\$
    – ATaco
    May 3, 2023 at 1:25
  • \$\begingroup\$ I mean like, you'ren't allowed to just go def f(x): return geomean(x) \$\endgroup\$ May 3, 2023 at 13:38
  • \$\begingroup\$ @emirps I'm not the OP but: To take the geometric mean of \$n\$ numbers, you multiply them all together, then raise this to the \$\frac1n\$th power, or take the \$n\$th root. \$\endgroup\$ May 4, 2023 at 16:40
  • 3
    \$\begingroup\$ Related, related. In addition to saying again that banning something as vague as a "built in function" is a bad idea, breaking ties by (vote?) score doesn't sound like it is a great idea. Ties are usually broken by earlier posting, but honestly determining the "winner" is not too important - the rules about scoring exist to be able to say if a score is better than another. Adding this score rule will add a weird ambiguity to what makes a submission good. \$\endgroup\$ May 5, 2023 at 16:03
2
\$\begingroup\$

Sort int64 with float64 values

Your challenge is to create the following total ordering of int64 and float64 values:

  • Apart from -0.0 which sorts before 0.0, two values of the same type sort according to which one is less than the other.
  • Where two values of different types are exactly equal, the float64 sorts before the int64 if negative or after if positive. Note that -0.0 counts as a negative float64 and 0.0 counts as a positive float64, and the int64 0 compares between the two.
  • int64 values that fall between the representations of two float64 values must sort between those two values. Similarly, float64 values that have fractional parts must sort between the nearest two integer values, although the previous rule allows you to simply truncate the float64 value towards zero to compare it to an int64 value.

Here are some int64 and float64 values in the correct order:

-9223372036854775808.0
-9223372036854775808
-9223372036854775807
-9223372036854774786
-9223372036854774785
-9223372036854774784.0
-9223372036854774784
-9223372036854774783
-9007199254740994.0
-9007199254740994
-9007199254740993
-9007199254740992.0
-9007199254740992
-4503599627370496.0
-4503599627370496
-4503599627370495.5
-4503599627370495.0
-4503599627370495
-4503599627370494.5
-1.5
-1.0
-1
-0.5
-0.0
0
0.0
0.5
1
1.0
1.5
4503599627370494.5
4503599627370495
4503599627370495.0
4503599627370495.5
4503599627370496
4503599627370496.0
9007199254740992
9007199254740992.0
9007199254740993
9007199254740994
9007199254740994.0
9223372036854774783
9223372036854774784
9223372036854774784.0
9223372036854774785
9223372036854774786
9223372036854775807
9223372036854775808.0

Your code can either implement a sort function for a list of elements or it can be a comparator for use with your language's built-in sort function or some other suitable way of indicating the sort ordering.

You can earn brownie points for supporting nonfinite float64 values and arbitrary precision integers.

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

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

Create an equation for a convex polygon

It turns out that it's possible to create an equation for any convex polygon. Here is a simple example:

$$ \sqrt { 1 - x } \sqrt { 1 - y } \sqrt { x + y } = 0 $$

I don't know how to create a link to a graph, but I was able to use the graphing calculator at https://www.mathway.com/Graph to draw this equation by pasting the text \sqrt { 1 - x } \sqrt { 1 - y } \sqrt { x + y } = 0 into its equation box. As you can see the result is a simple triangle, but it's possible to extend this idea to any convex polygon.

Please write a program or function that will take a list of points representing the vertices of a convex polygon and output an equation for that polygon in an acceptable format, typically TeX, but other formats would be acceptable if you can find a resource that will draw the polygon.

You can make reasonable assumptions regarding the input e.g. you can require the first point to be the one with the highest y-coordinate and the remaining points to follow the polygon in a clockwise direction.

Examples:

(-1, 1), (1, 1), (1, -1) => \sqrt { 1 - x } \sqrt { 1 - y } \sqrt { x + y } = 0
(0,1),(1,0),(0,-1),(-1,0) => \sqrt{1+x+y}\sqrt{1+x-y}\sqrt{1-x-y}\sqrt{1-x+y}=0

(I tried to write some more complex examples but even Mathway's calculator gave up at that point.)

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

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

Complexity of a binary matrix

This is a \$4\times 4\$ binary matrix:

$$ \begin{matrix} 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 \\ 1 & 0 & 0 & 1 \\ 0 & 0 & 0 & 1 \\ \end{matrix} $$

A row-add operation takes one row and adds it to another one where addition is done mod 2. For example adding the second row to the third would give the following matrix:

$$ \begin{matrix} 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 \\ 1 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 \\ \end{matrix} $$

It's possible to add a row to itself. This is the same as zeroing that row.

Task

Given a \$n\times n\$ binary matrix your task is to figure out how many row-addition steps it would take to get to that matrix starting from the identity matrix. I call this the "complexity" of the matrix.

For example if we were given the following matrix as input

$$ \begin{matrix} 0 & 1 & 1 \\ 1 & 0 & 0 \\ 0 & 0 & 0 \\ \end{matrix} $$

Then your program would output \$5\$ since there's no shorter sequence than the following:

$$ \begin{matrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \\ \end{matrix} $$ $$ 1\leftarrow 2 $$ $$ \begin{matrix} 1 & 1 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \\ \end{matrix} $$ $$ 2\leftarrow 1 $$ $$ \begin{matrix} 1 & 1 & 0 \\ 1 & 0 & 0 \\ 0 & 0 & 1 \\ \end{matrix} $$ $$ 1\leftarrow 2 $$ $$ \begin{matrix} 0 & 1 & 0 \\ 1 & 0 & 0 \\ 0 & 0 & 1 \\ \end{matrix} $$ $$ 1\leftarrow 3 $$ $$ \begin{matrix} 0 & 1 & 1 \\ 1 & 0 & 0 \\ 0 & 0 & 1 \\ \end{matrix} $$ $$ 3\leftarrow 3 $$ $$ \begin{matrix} 0 & 1 & 1 \\ 1 & 0 & 0 \\ 0 & 0 & 0 \\ \end{matrix} $$

It's is always possible to get to any matrix from the identity matrix (proof left as an exercise to the reader)

Scoring

This is . I'll be running submissions on a Ryzen 1800X limited to 16GB of RAM (using ulimit).

Your code will take as input an infinite stream of matrices over stdin. A matrix is encoded as its size followed by the rows of the matrix. The input starts with 10 matrices of size 3 followed by 10 of size 4 and so on.

You must output (in order) to stdin the complexities of the matrices.

See this code for an example input. I'll use this code to generate the input (but using a secret seed).

I will run each submission for 5 minutes. The submission that manages to process the most matrices will win. Ties will be resolved by the time it took to output the last matrix.

TODO: add test inputs.

Bonus points

In case two submissions are tied to the nanosecond I might use these as a tiebreaker :D

Find a block diagonal matrix whose complexity is less than the sum of the complexities of the blocks on the diagonal.

Is there a block matrix whose complexity is less than one of the blocks on the diagonal?

\$\endgroup\$
2
  • \$\begingroup\$ So row addition is just XOR? \$\endgroup\$
    – mousetail
    Jun 1, 2023 at 13:29
  • \$\begingroup\$ @mousetail yep! \$\endgroup\$
    – AnttiP
    Jun 1, 2023 at 13:30
2
\$\begingroup\$

How powerful must this e approximation be?

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

Generate a naïve isEven()

We've all seen the memes of a beginner programmer writing an isEven() function that looks something like this:

def isEven(num):
    if (num == 0):
        return True
    elif (num == 1):
        return False
    # and so on

You and I know this is tedious to do by hand, so let's write a program to make this function for us.

Task

Write a program that accepts a positive integer n and outputs a valid naïve isEven() function that can check all integers from 0 up to and including n. The resulting function can be in any language, so long as it:

  1. Is named isEven, and
  2. Accepts a single parameter, num (integer), and
  3. Explicitly checks whether num is equal to each integer from 0 to n, inclusive (i.e. no else for the last case), and
  4. Uses 1 if statement and n - 1 else if statements (or the equivalent for your resulting language, but not ternary operators) across n lines, and
  5. Returns a truthy or falsey value for the language of the resulting function on a new line after each check. This must be an explicit value, not a calculation (e.g. True not num%2).

You can assume n and num are both valid positive integers (i.e. no error checking necessary).

Your resulting function will be at least 2(n+1) + 1 lines, since each value up to n requires 2 lines; one for the check, and one for the return. The +1 in parenthesis comes from the need to check 0, and the + 1 outside the parenthesis comes from the function declaration.

Scoring

This is , so fewest bytes win. Also, standard rules apply, and standard exclusions are forbidden.

Please put the resulting language in your title (e.g. Jelly --> C++, n bytes).

Test cases

Resulting language: Python

# n = 1
def isEven(num):
    if num == 0:
        return True
    elif num == 1:
        return False
# n = 10
def isEven(num):
    if num == 0:
        return True
    elif num == 1:
        return False
    elif num == 2:
        return True
    elif num == 3:
        return False
    elif num == 4:
        return True
    elif num == 5:
        return False
    elif num == 6:
        return True
    elif num == 7:
        return False
    elif num == 8:
        return True
    elif num == 9:
        return False
    elif num == 10:
        return True

Edit: remove parenthesis from test case

Edit: remove parenthesis from function name

Edit: add condition about explicit true/false return

Edit: fix typo in second condition

\$\endgroup\$
8
  • \$\begingroup\$ What if the target language doesn't use trailing () in functions? \$\endgroup\$
    – Adám
    May 24, 2023 at 6:17
  • \$\begingroup\$ Instead of return True and return True would it be permitted to write return num%2? \$\endgroup\$
    – Adám
    May 24, 2023 at 6:21
  • \$\begingroup\$ The trailing () don't really matter since the byte count of the resulting function doesn't count toward the score. Python technically doesn't require parenthesis around the conditional. Edit: I think you meant around the function declaration? So long as the function symbol is isEven, it doesn't matter. \$\endgroup\$
    – QueueBot
    May 24, 2023 at 6:37
  • \$\begingroup\$ No, it must be a truthy or falsey value, not a truthy or falsey calculation. \$\endgroup\$
    – QueueBot
    May 24, 2023 at 6:37
  • \$\begingroup\$ It's not hard to learn the x%2<1 trick... \$\endgroup\$ May 24, 2023 at 13:28
  • \$\begingroup\$ So, the output is in our choice of language, and not necessarily the language our solution is in? \$\endgroup\$
    – Shaggy
    May 31, 2023 at 11:56
  • 1
    \$\begingroup\$ @Shaggy that's correct \$\endgroup\$
    – QueueBot
    Jun 3, 2023 at 5:05
  • \$\begingroup\$ Would it be allowed to use a certain programming language as the output language, if that language's closest equivalent to an if/else statement is a ternary operator? (For example, many functional programming languages - for example in Scheme, (if (= n 0) #t (if (= n 1) #f ...)) ) \$\endgroup\$ Jun 9, 2023 at 21:59
2
\$\begingroup\$

Adjacent Items Sorting

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

Generate the SMKG aperiodic tiling

Task

Smith, Myers, Kaplan and Goodman-Strauss discovered the first "einstein" - a single connected tile that can tile the plane only aperiodically. They call their tile the "hat". Write a program to generate a finite patch of a tiling of the plane by hats. enter image description here

Details

The program must output a sequence of tiles that make up the patch. Each tile must be given in the form of its 13 (or 14 - see below) vertices, listed in order around the tile either clockwise or anticlockwise. Each vertex must be given in the form of its triangular coordinates, as explained below, and these coordinates must be integers.

Triangular coordinates are with respect to a pair of axes at 60 degrees to each other. A point with triangular coordinates (u,v) corresponds to a point with ordinary cartesian coordinates (u+v/2, v*sqrt(3)/2). An example of a single hat tile has vertices with triangular coordinates

[(4,2),(2,1),(2,2),(1,2),(2,4),(4,5),(4,6),(5,7),(6,6),(5,4),(6,4),(6,2),(5,1)]

Note that it is possible and allowed for the hat to have a different size and still have integer coordinates, although it must not be a different shape. The hat has a unique longest side (of length 2 at this scale), which may optionally be bisected by an additional vertex to give 14 vertices.

All output tiles must belong to a valid tiling of the full plane by hats (all related to each other by congruences or reflections). The output must include every tile that intersects a certain square, where this square is large enough that there are at least 1000 such tiles. (At the above scale, a square of side 120 is sufficient). The program may optionally output further tiles of the tiling that lie outside the square. The same tile should not appear more than once in the output.

The algorithm should theoretically be capable of generating arbitrarily large patches (given the ability to work with arbitrary precision integers). In particular this means that algorithms that calculate floating point coordinates and then round them to integers are typically NOT acceptable.

Examples

The beginning of the output (corresponding to the first 5 hats) might be:

[(12,0),(10,-1),(10,0),(9,0),(10,2),(12,3),(12,4),(13,5),(14,4),(13,2),(14,2),(14,0),(13,-1)]
[(10,2),(9,0),(8,0),(7,-1),(6,0),(7,2),(6,2),(6,3),(8,4),(9,3),(10,4),(12,4),(12,3)]
[(2,-2),(4,-1),(4,0),(5,1),(4,2),(2,1),(2,2),(1,2),(0,0),(1,-1),(0,-2),(0,-4),(1,-4)]
[(6,0),(7,-1),(6,-2),(6,-3),(4,-4),(3,-3),(2,-4),(1,-4),(2,-2),(4,-1),(4,0),(6,2),(7,2)]
[(4,2),(2,1),(2,2),(1,2),(2,4),(4,5),(4,6),(5,7),(6,6),(5,4),(6,4),(6,2),(5,1)]
...

The output can be in any reasonable form, such as a linefeed-delimited sequence of lists of pairs as above.

The picture below shows a possible output converted to graphical form. Note that the program itself does not need to produce any graphical output (although obviously it is useful for testing). enter image description here

This is code golf, so the shortest program in each language wins.

Related: Draw the GKMS aperiodic tile

\$\endgroup\$
3
  • \$\begingroup\$ 1. There is no input. The program should simply output the coordinates of tiles as described. 2. There are no partial tiles. The output should be exactly as described. It should include every tile that intersects the square, and is allowed to include others, but all tiles output must belong to a tiling of the plane by hats. \$\endgroup\$
    – aeh5040
    May 31, 2023 at 16:40
  • \$\begingroup\$ The specifications reads: "All output tiles must belong to a valid tiling of the full plane by hats (all related to each other by congruences or reflections). The output must include every tile that intersects a certain square, where this square is large enough that there are at least 1000 such tiles. (At the above scale, a square of side 120 is sufficient). The program may optionally output further tiles of the tiling that lie outside the square. The same tile should not appear more than once in the output." \$\endgroup\$
    – aeh5040
    May 31, 2023 at 23:31
  • \$\begingroup\$ Outputting 5 tiles would not qualify, because 5<1000. Terminating with a memory overflow would be acceptable (although somewhat perverse) provided the task is completed as described first. Not sure what the issue is here...? \$\endgroup\$
    – aeh5040
    May 31, 2023 at 23:33
2
\$\begingroup\$

Finitely generated subgroups of free groups

Suppose you are given the free group \$F_n\$ on \$n\$ generators\${}^1\$, a finite subset \$S\$ of \$F_n\$, and an element \$x \in F_n\$. Then there is an algorithm to determine whether \$x\$ is in the subgroup generated\${}^2\$ by \$S\$, as follows:

  • Start with a directed graph with a single "base" vertex, and no edges.
  • For each element of \$S\$, add a cycle to the graph according to the corresponding free group word. Start at the base vertex; for each generator \$g_n\$ in the word, add an arrow labelled by \$n\$; for each inverse of a generator \$g_n^{-1}\$ in the word, add an arrow in the opposite direction labelled by \$n\$; and end at the base vertex.
  • If there is a pair of edges with the same label and with either the same source or the same destination, merge those two edges and the two vertices at the other end. (Except that merging two vertices is not necessary if the two edges have the same source and the same destination.)
  • Iterate the previous step until there is no such pair of edges left.
  • Now follow the graph from the base vertex, according to the reduced free group word corresponding to \$x\$. For each generator \$g_n\$ in the word, look for an edge with source at the current vertex and label \$n\$, and move to the destination of that edge. For each generator \$g_n^{-1}\$ in the word, look for an edge with target at the current vertex and label \$n\$, and move to the source of that edge.
    • If at any point, you do not find such an edge, then \$x \notin \langle S \rangle\$.
    • If at the end, you end up back at the base vertex, then \$x \in \langle S \rangle\$; otherwise, \$x \notin \langle S \rangle\$.

(I plan to give an example of the operation of this algorithm; but I do not have time at the moment to generate the required graph diagrams.)

Task

Your task is: given a finite subset \$S\$ of a free group \$F_n\$ and an element \$x \in F_n\$, determine whether \$x\$ is in the subgroup generated by \$S\$. (Note: we are not asking to determine whether \$x\$ is in the normal subgroup generated by \$S\$; that problem is undecidable in general.)

You are not required to use the above algorithm. On the other hand, your program or function must always terminate in finite time; so for example, that rules out a naive algorithm just taking all possible products of elements of \$S\$ and their inverses and determining whether you eventually find \$x\$ in the output.

Input

You will be given a list of free group elements, and a second input giving another free group element. Possible input formats for free group elements include:

  • An element of a built-in free group type.
  • A string in the form abCbcA where the generators are a through z and for example C represents the inverse of the generator c. You may assume the string is in reduced form, so for example it will not contain either Cc or cC.

If you like, you could also take a single list of free group elements, and use the first element as \$x\$ and the rest of the list as \$S\$.

If it is useful, you may assume the list of subgroup generators is nonempty, and also that \$x\$ and each element of the list is not the empty word.

Output

A truthy/falsey value according to whether or not \$x \in \langle S \rangle\$, where \$S\$ is the set of elements of the list for the first input and \$x\$ is the second input.

Examples

[aa, ab], a -> False
[aa, ab], ba -> False
[aa, ab], Ba -> True
[aBc, bc], aBBCbA -> True
[aBc, bc], abc -> False
[aaaaa, aaa], a -> True

Score

This is : the shortest code in bytes for any given programming language wins.


\${}^1\$ The free group \$F_n\$ on \$n\$ generators can be described as the reduced words in the alphabet consisting of formal symbols \$g_1, g_1^{-1}, g_2, g_2^{-1}, \ldots, g_n, g_n^{-1}\$. Here, "reduced" means that \$g_i\$ and \$g_i^{-1}\$ never appear next to each other in the word. To multiply two words, concatenate them and then iteratively cancel out pairs \$g_i g_i^{-1}\$ or \$g_i^{-1} g_i\$ in the middle. This has the empty word as an identity element, and to find the inverse of a reduced word, reverse the order and transform each \$g_i\$ into \$g_i^{-1}\$ and vice versa.

\${}^2\$ The subgroup of \$F_n\$ generated by a subset \$S \subseteq F_n\$ is the smallest subset of \$F_n\$ which contains \$S\$, also contains the identity element, and is closed under multiplication and inverses. This can alternately be described as the set of elements of \$F_n\$ which can be formed as the product of some finite sequence of elements of \$S\$, and/or their inverses.

\$\endgroup\$
2
  • \$\begingroup\$ This could benefit from definitions of the relevant mathematical terms, such as "free group". \$\endgroup\$
    – Bbrk24
    Jun 9, 2023 at 19:48
  • \$\begingroup\$ @Bbrk24 OK, I added some brief definitions in footnotes. \$\endgroup\$ Jun 9, 2023 at 20:50
2
\$\begingroup\$

A Phinary Library

I've been away from SE/SO for quite some time now and have decided to revisit a SE that I used to go on way before I made this account, so I wanted to draft a challenge that I have had rolling around in my head for a bit, fitting the tags


Challenge

Knowing what base phi/'phinary' numbers are, as explained in the background to this challenge and in this one too, your task is to implement a set of arithmetic routines/functions that handle this numeric system, at least for addition and subtraction of two phinary numbers from each other.

You will need to write code that performs the following three operations:

  1. A chunk that adds two phinary numbers
  2. A chunk that subtracts two phinary numbers
  3. A chunk that outputs a phinary number in standard form

I'm refraining from calling them functions or whatnot, as you are totally free to organise your code in any way you see fit.

You may take normalised phinary input via whatever way you choose (hardcoded into ROM, through stdin, whatever) and in whatever format (for example, you can encode whether it's addition or subtraction in the input itself) and print (or output in some other way) the normalised phinary result.

Do not use built-in base conversion facilities, the arithmetic has to be done directly in phinary. The intermediate phinary can be "unstandardised": only the input and output must be in normal form.

See the following test cases for some examples:

INPUT             OUTPUT
----------------------------
10000.0001
         +
    100.01    =   10100.0101 
----------------------------
 1010.0001
         -
      10.0    =    1000.0001
----------------------------
      10.1
         +
  1000.001    =     1010.101

Your code should handle and be correct for arbitrary sized phinary input. If your language has a specific size limit (such as old Befunge, or you're writing 6502 assembly code), you should handle inputs that are at least 33% of the space constraint in size (so, 21626 digits for 6502 assembly, for example).

The shortest code in bytes wins. If your code is textual source, bytes are counted according to UTF-8 encoding sizes.


Things I'm still not sure about

What other limits should I impose?
How should I better formulate the challenge?

\$\endgroup\$
2
  • \$\begingroup\$ While the challenges you linked explain phinary quite well, I think it would be worth having at least a brief explanation in the body of your challenge as well, even if it's just copied, pasted, and cited from them. I'd also like to see some testcases where weird phinary rules apply, as right now your test cases make it look like phinary is just binary. \$\endgroup\$ Jun 20, 2023 at 20:48
  • \$\begingroup\$ "The shortest code in bytes wins. If your code is textual source, bytes are counted according to UTF-8 encoding sizes." See How to count bytes FAQ \$\endgroup\$ Jul 19, 2023 at 3:54
2
\$\begingroup\$

XOR of independent Bernoulli variables

\$\endgroup\$
1
  • 1
    \$\begingroup\$ Nice challenge, my only suggestion is to point out that the XOR is 1 when the number of 1's is odd. \$\endgroup\$
    – xnor
    Jun 21, 2023 at 18:27
2
\$\begingroup\$

Detect Maxima Using Persistent Homology

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

Translate the keitai input method

\$\endgroup\$
2
  • \$\begingroup\$ Are solutions required to cycle back to a-column, or are inputs guaranteed to never contain extraneous keypresses? \$\endgroup\$ Jun 29, 2023 at 2:09
  • 1
    \$\begingroup\$ @UnrelatedString it must cycle back; I've added a test case for this \$\endgroup\$
    – bigyihsuan
    Jun 29, 2023 at 5:04
2
\$\begingroup\$

Chamber of Reflection

Background

A ray of light is fired from the top left vertex of an MxN Chamber, where M a denotes the width and N denotes the height of the chamber. The ray of light advances one grid space per second. Given that T is the number of seconds to be simulated, calculate the number of reflections in this time frame.

For example, given 5 4 11 (ie. M = 5, N = 4, T = 11):

\/\  [
/\ \ [
\ \ \[
   \/[
-----
There would be 4 reflections, so the output should be 4.

Note that a reflection only counts if the ray of light has already bounced off it, so for example, given 5 4 10:

\/\  [
/\ \ [
  \ \[
   \/[
-----
There would only be 3 reflections, so the output should be 3.

Your Task

  • Sample Input: M, the width of the chamber, N, the height of the chamber, and T, the time frame. These are all numbers.

  • Output: Return the number of reflections.

Explained Examples

Input => Output
1 1 10 => 9 

Chamber:
\[
-

The ray will be reflected back and forth a total of 9 times. 
Input => Output
5 1 10 => 9 

Chamber:
\/\/\[

The ray will be reflected back and forth a total of 9 times. It will first go left to right, then go backwards right to left.
Input => Output
4 5 16 => 6 

Chamber:
\/\ [
/\ \[
\ \/[
 \/\[
\/\/[
----

The ray will be reflected back and forth a total of 6 times.
Input => Output
100 100 1 => 0 

Chamber:
\ ... [
...    x100
-x100


The ray never touches a wall, and is never reflected, so output 0.

Test Cases

Input => Output
5 4 11 => 4
5 4 10 => 3
1 1 10 => 9
5 1 10 => 9
4 5 16 => 6
100 100 1 => 0

3 2 9 => 5
3 2 10 => 6
6 3 18 => 5
5 3 16 => 7
1 1 100 => 99
4 4 100 => 24
2398 2308 4 => 0
10000 500 501 => 1
500 10000 502 => 1

Bonus points (not really): Listen to DeMarco's song Chamber of Reflection while solving this.

This is , so shortest answer wins.

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

Reverse Conway's Game of Life

\$\endgroup\$
3
  • \$\begingroup\$ What should the behavior be for gardens of eden? \$\endgroup\$
    – Bbrk24
    Jul 4, 2023 at 1:08
  • 1
    \$\begingroup\$ gardens of eden will not be part of the input, you can output nonsense, fail or not terminate for them, I will add it to the challenge. that's what I was trying to convey with the multiple solutions constraint \$\endgroup\$
    – c--
    Jul 4, 2023 at 15:43
  • 1
    \$\begingroup\$ determining if a configuration is a garden of eden could be an interesting challenge \$\endgroup\$
    – c--
    Jul 4, 2023 at 15:49
2
\$\begingroup\$

Sum of Two Intervals

A k-th interval plus an m-th interval is a (k+m-1)th interval. An interval with p semitones plus one with q semitones is one with (p+q) semitones. Given two intervals, get their sum. Relations between interval and semitones is listed below.

Interval Double
Diminished
Diminished Minor Perfect Major Augmented Double
Augmented
unison
(1st)
-2* -1* - 0 - 1 2
2nd -1* 0 1 - 2 3 4
3rd 1 2 3 - 4 5 6
4th 3 4 - 5 - 6 7
5th 5 6 - 7 - 8 9
6th 6 7 8 - 9 10 11
7th 8 9 10 - 11 12 13
octave
(8th)
10 11 - 12 - 13 14

* Negative distance doesn't exist but it can be added 12 until non-negative

For larger interval, k-th interval has 12 more semitones than the same type of (k-7)-th interval. Triple Augmented is 1 more semitone than Double Augmented, Triple Diminished is 1 less semitone than Double Diminished, etc.

IO format

  • The interval would likely get inputted as one argument
  • You can take Double Diminished/Diminished/Minor/Perfect/Major/Augmented/Double Augmented as -2/-1/a/b/c/1/2, where a, b, c are different, zero or non-integer
  • You can take Double Diminished/Diminished/Minor/Perfect/Major/Augmented/Double Augmented as -3/-2/-1/0/1/2/3
  • Same applies to output
  • You needn't handle invalid input like "Diminished 1st", "Major 4th" or "Perfect 2nd".

Test cases

Minor 2nd + Major 3rd = Perfect 4th
Major 2nd + Major 2nd = Major 3rd
Major 3rd + Major 3rd = Augmented 5th
Augmented 2nd + Augmented 3rd = Triple Augmented 4th
Double Diminished 6th + Double Diminished 7th = 5 Times Diminished 12th
Augmented 1st + Minor 2nd = Major 2nd

or testing friendly,

[m,2]+[M,3]=[0,4]
[M,2]+[M,2]=[M,3]
[M,3]+[M,3]=[1,5]
[1,2]+[1,3]=[3,4]
[-2,6]+[-2,7]=[-5,12]
[1,1]+[m,2]=[M,2]
\$\endgroup\$
2
\$\begingroup\$

The next popcount

Given a substring of A000120, number of 1's in binary expansion of n, find the next term.

If there's no answer, output something unambiguous to a term. If there's multiple possible answers, output any subset of the answers(Empty set allowed which may act as if no answer)

Test Cases

2, 2, 3, 2, 3, 3 -> 4  (X001, X010, X011, X100, X101, X110 where X matches /10*/)
2, 4 -> DNE
5, 1 -> 2 (11111, 100000)
\$\endgroup\$
1
  • \$\begingroup\$ This feels like a combination of determining whether a substring is valid and finding a possible next term, although maybe they're close enough to be the same challenge \$\endgroup\$ Sep 8, 2023 at 14:22
2
\$\begingroup\$

First attempt at a question. Feedback appreciated.


Calculating Complete Graphs

The above picture shows a complete graph with 7 vertices. According to Wikipedia, "a complete graph is a simple undirected graph in which every pair of distinct vertices is connected by a unique edge."

Today, we're going to be repairing incomplete graphs.

Given a 2D Array (representing an incomplete graph) where each inner array represents a vertex, determine the number of additional edges required to create a complete graph.


Here's an example:

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

And this would generate a graph that looks like this:

Incomplete

To make this graph complete, it is obvious that we only need to add two edges.

Complete

For completeness (haha), here's what the completed 2D array would look like (but this is not what your program should output):

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

Notes:

  1. There is an array for every vertex, but your code should be able to account for empty arrays (which means the vertex is originally not connected to any other vertex).

  2. I don't know if this is important, but you can assume the vertexes listed in each inner array will be listed in increasing order. Also, no vertex will be connected to itself.

  3. If vertex a is connected to vertex b, then vertex b is connected to vertex a. Symmetric.


And yeah, that's pretty much it. Here are some test cases:

Input                                                           Output

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

This question is tagged code-golf. Standard rules apply.

\$\endgroup\$
2
  • 3
    \$\begingroup\$ Hi! Welcome!!! Question looks good, sounds a bit trivial tho, can be solved using math formula (n(n-1) - x)/2 where n is the number vertices and x the number of elements in the flatten input \$\endgroup\$ Jul 25, 2023 at 20:33
  • 2
    \$\begingroup\$ @LuisfelipeDejesusMunoz I must admit the solution is easier than I originally thought. I'll attempt to remake it in a way that invites more creativity. \$\endgroup\$
    – SanguineL
    Jul 25, 2023 at 20:53
2
\$\begingroup\$

Compute this fractal matrix

\$\endgroup\$
2
  • \$\begingroup\$ once again - why so specific? why can't I just return any two distinct values, and not just a truthy and a falsy value? \$\endgroup\$
    – RubenVerg
    Jul 21, 2023 at 18:09
  • \$\begingroup\$ @RubenVerg As far as I can tell most challenges about computing matrices only allow to output the numbers that actually appear in the matrix. I removed the restrictions about the print formatting, but as the numbers in the matrix are 0 and 1, allowing any two distinct values feels overly general. Do you have any specific (type of) value pair in mind. \$\endgroup\$
    – bsoelch
    Jul 22, 2023 at 13:36
1
45 46
47
48 49
157

You must log in to answer this question.

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