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\$
2
  • \$\begingroup\$ What if I posted on the sandbox a long time ago and get no response? \$\endgroup\$
    – None1
    Commented May 15 at 14:05
  • \$\begingroup\$ @None1 If you don't get feedback for a while you can ask in the nineteenth byte \$\endgroup\$
    – mousetail
    Commented May 29 at 13:27

4705 Answers 4705

1
42 43
44
45 46
157
2
\$\begingroup\$

Draw an ASCII envelope

\$\endgroup\$
3
  • \$\begingroup\$ Wow your're a good challenge poster. nice challenge! \$\endgroup\$
    – DialFrost
    Commented Mar 22, 2022 at 23:31
  • \$\begingroup\$ But i think you can remove the last 2 points under rules as they are sort of standard code golf rules and ascii art rules, and u might wanna include "trailing spaces are allowed" \$\endgroup\$
    – DialFrost
    Commented Mar 22, 2022 at 23:32
  • \$\begingroup\$ @DialFrost Thanks for the feedback! I'll edit it according to your suggestions! \$\endgroup\$ Commented Mar 22, 2022 at 23:46
2
\$\begingroup\$

Order of an algebraic number

\$\endgroup\$
11
  • \$\begingroup\$ i find it fascinating although its a bit beyond my knowledge of how to solve it \$\endgroup\$
    – don bright
    Commented Dec 21, 2021 at 7:41
  • \$\begingroup\$ Of course this is your challenge, and you can configure it as you wish. But I'd like to note that, by separating out any answers that employ Built-Ins into a Community Answer, you're effectively reducing this to a "Do X without Y" challenge, where "Y", in this case, is Built-Ins. That takes away the fun of being able to find just the right Built-In (or combination of two or three Built-Ins) to do the job... \$\endgroup\$
    – theorist
    Commented Dec 24, 2021 at 4:11
  • \$\begingroup\$ ...fun that you were happy to avail yourself of when you answered each of these two questions with a pair of Built-Ins: codegolf.stackexchange.com/questions/224125/… and codegolf.stackexchange.com/questions/229414/… \$\endgroup\$
    – theorist
    Commented Dec 24, 2021 at 4:12
  • \$\begingroup\$ Sorry I did not spot this problem when the challenge was still in sandbox: Surd in Mathematica only gives real roots. \$\endgroup\$
    – alephalpha
    Commented Dec 24, 2021 at 4:44
  • \$\begingroup\$ Deleted main post \$\endgroup\$ Commented Dec 24, 2021 at 16:25
  • 1
    \$\begingroup\$ @alephalpha I've edited the challenge to include the test cases suggested by you and tsh on the main post. I've also specified that the input will always be real \$\endgroup\$ Commented Dec 24, 2021 at 16:26
  • \$\begingroup\$ @theorist I already know that Mathematica essentially has a builtin for this - it wouldn't surprise me if other math-oriented langs (e.g. Pari/GP) also did. I'm not interested in solutions that off-hand all the work onto a builtin, but banning them isn't something I like doing. Therefore, I go by this suggestion to combine trivial builtin answers into a single CW answer. I'm well aware that I've posted builtin-only answers before, but only if the challenge doesn't combine trivial answers into a single CW answer (like I prefer to do) \$\endgroup\$ Commented Dec 24, 2021 at 16:31
  • \$\begingroup\$ There's three problems: (1) For all intents and purposes, the suggestion you are folowing does effectively ban builtins. By requiring any who answer to put builtin solutions into an anonymous community wiki, you are banning them from including builtins in their answers. The practice you've adoped just seems like a way to ban builtins in practice, while saying they're not "technically" banned. It's a "distinction without a difference." Thus I think those who adopt this practice shouldn't say "I'm not banning builtins".... \$\endgroup\$
    – theorist
    Commented Dec 24, 2021 at 22:08
  • \$\begingroup\$ Instead, I think it's more accurate to say: "I am banning builtins. But for those who want to post builtins anyways, you can put them into the Community Wiki." (2) Calling builtin answers "trivial", IMO, unfairly, well, trivializes the knowledge and understanding of a program needed to identify the right builtin for the job. Sure some can be trivial, but I don't think think they should be blanket-labeled as suchl. E.g., while you may have a different view, I don't think this was trivial: codegolf.stackexchange.com/questions/230836/leave-the-times-out/… ... \$\endgroup\$
    – theorist
    Commented Dec 24, 2021 at 22:10
  • \$\begingroup\$ The point of the linked example is that Defer wasn't designed to accomplish the goal set by the OP, but it nevertheless had that effect anyways. And you needed some understanding of how the language worked to realize it would do that. But it's still a simple one-word builtin. (3) Unless you're programming in machine code, all answers consist of a sequence of builtins. So it really comes down to an arbitrary cutoff of what's the minimum amount of builtins an answer needs to contain. \$\endgroup\$
    – theorist
    Commented Dec 25, 2021 at 0:03
  • \$\begingroup\$ To my understanding, the most complex thing here is not find out a minimal polynomial, but instead of how to simplify the input. Especially for testcases like \$\sqrt{\sqrt{5}+1}\cdot \sqrt{\sqrt{5}-1}\$, or \$\frac{5\sqrt{5}-1}{\sqrt{5}-1}\$. \$\endgroup\$
    – tsh
    Commented Dec 27, 2021 at 6:23
2
\$\begingroup\$

Batt to the Basics

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

What's the Missing Code?

Cops' thread Robbers' thread

\$\endgroup\$
5
  • 1
    \$\begingroup\$ Now this sounds like fun! Just one question: wouldn't it add more to the challenge if you didn't tell the robbers where each letter was removed? I feel like knowing where the missing characters are would make it too easy, especially since the cops are trying to create as short code as possible (so that they win). Do you think it would make it too easy? \$\endgroup\$ Commented Mar 27, 2022 at 18:13
  • \$\begingroup\$ I thought about this, but I came to the conclusion that it would make it easier for the robbers to simply go to the start of the program, and write print(...); end program. However, on thinking about it again, this would make it easier for the cops to reduce the characters removed while keeping the answer non-obvious, which would prevent the robbers from doing this. I will consider this and perhaps change the question. \$\endgroup\$
    – Lecdi
    Commented Mar 27, 2022 at 18:19
  • \$\begingroup\$ Ohh.... I see what you mean. But that could be part of the cops' challenge: making the code complicated enough, with few enough characters removed, so that the robbers couldn't do that. But yes, your reasoning makes sense now. In that case, either way would be fine. I'm looking forward to when this is posted on the main site! \$\endgroup\$ Commented Mar 27, 2022 at 18:28
  • 1
    \$\begingroup\$ I think it is too easy for the robbers in its current state, so I will edit it to include your suggestion: I think that as long as the cops remove few enough characters, it will be impossible for the robbers to do this. \$\endgroup\$
    – Lecdi
    Commented Mar 27, 2022 at 19:17
  • 1
    \$\begingroup\$ If your int("5") example is run in the Python shell (as opposed to in a program), the output is 5. Just FYI. \$\endgroup\$ Commented Mar 27, 2022 at 19:46
2
\$\begingroup\$

Wash clothes as quickly as possible

\$\endgroup\$
1
  • \$\begingroup\$ Can you add test cases? \$\endgroup\$
    – Seggan
    Commented Mar 29, 2022 at 15:50
2
\$\begingroup\$

Translate Text into Matoran

The Matoran Alphabet is the alphabet used by many of the characters in the Bionicle universe.

Matoran Alphabet

Your challenge is to create a program or function that takes a string as input and creates an image of the input written in the Matoran alphabet.

The input will only consist of uppercase letters (A-Z), numbers (0-9), and spaces. You may instead take input in lowercase.

Glyphs

As you can probably notice, the alphabet comprises glyphs made up of circles and straight lines.

For the sake of this challenge, let's define each glyph as a circle of radius 4 units (8 x 8), with some internal designs. The internal designs of letters can be any of:

  • Vertical Line at position 2, 4, or 6 (either full length or half)
  • Horizontal Line equivalent to above
  • Circle of radius 1, centered at [2, 2], [2, 6], [6, 2], or [6, 6]
  • Any of the above rotated by 45 degrees about the centre

Number glyphs work slightly differently; they always have a circle of radius 1 in the centre. For numbers 0 - 5, the glyph has evenly spaced spokes between the circles, starting from the top. For numbers greater than 5, the glyph has an additional circle of radius 2 in the centre, and the number of spokes is 6 less than the number.

Here is a diagram of the glyphs in spec, any glyphs with 45 degree rotations have an orange grid.

Matoran Alphabet

For drawing the glyphs, any line stroke in the range (0, 1) can be used. Glyphs can be kerned (space between adjacent glyphs) any amount from 0 - 4 units. Spaces should be 8 units wide (in addition to kerning).

This is a code-golf challenge, so the shortest code in bytes in each language wins.

\$\endgroup\$
4
  • \$\begingroup\$ This does seem like pretty interesting challenge, although I would recommend a clearer image of the characters of the Matoran alphabet, and probably a more rigorous definition of the shapes of each of the characters (eg. defining the positions/lengths/radii/etc of the inner circles/lines in terms of the radius of the exterior circle) \$\endgroup\$
    – des54321
    Commented Apr 11, 2022 at 4:14
  • \$\begingroup\$ @des54321 Thank you! I added some specification around the characters. Do you think this is sufficient, or should I include a written definition of each glyph? \$\endgroup\$ Commented Apr 11, 2022 at 22:31
  • \$\begingroup\$ That looks pretty good! I'd suggest leaving this challenge up on the sandbox for a bit longer to see if anyone else has suggestions, but as things stand now this seems a very well specified and fairly interesting challenge \$\endgroup\$
    – des54321
    Commented Apr 11, 2022 at 23:06
  • 1
    \$\begingroup\$ Thanks for your help, I'll leave it a couple of days then post it. \$\endgroup\$ Commented Apr 11, 2022 at 23:13
2
\$\begingroup\$

Get the trends of an array

\$\endgroup\$
2
  • 1
    \$\begingroup\$ Is there any specifications prevent the program from outputting [[1,1], [1,2], [2,3]] for [1,1,2,3]? Maybe you should add some texts about "you should generate fewest possible trends" or something like it. \$\endgroup\$
    – tsh
    Commented Apr 18, 2022 at 8:43
  • \$\begingroup\$ @tsh Good idea. Added. \$\endgroup\$
    – chunes
    Commented Apr 18, 2022 at 9:17
2
\$\begingroup\$

Will this makina program halt?

makina is a cell-based esolang composed of automata which move around a grid. These automata follow paths of instructions that direct their movement. Your task is to, given a makina program using only the below instructions (so a subset of normal makina) as input, output two distinct values depending on whether or not it is a loop. (If program flow comes to an arrow character that it has already visited then the program is a loop.)

Instructions

  • ^>v< These instructions (arrows) set the direction of the automaton to the direction they point in.
  • I This instruction halts automata going up or down, but does nothing to ones going left or right.
  • H This instruction halts automata going left or right, but does nothing to ones going up or down.
  • O This instruction does nothing to the automaton, acting like a sort of 4-way intersection.

All other characters halt the automaton, as does exiting the bounds of the program. The automaton starts in the top-left corner going right.

Testcases

Truthy

>>>v
v<<<
OOOv
H<<<
v

Falsey

>>>v
^<<<
>v
^O<
>^
>>>v
v<I<
H>^
>^
>>>>v
v <<<
OOOv
H<<<
v
\$\endgroup\$
2
  • \$\begingroup\$ "All other characters halt the automaton" So arbitrary characters different from >v<^HIO can be part of the input? If so, this should be reflected in the test cases. (Personally, I'd only allow valid characters in the input.) \$\endgroup\$
    – Laikoni
    Commented Apr 24, 2022 at 19:39
  • \$\begingroup\$ Also the current last two Falsy test cases actually halt and are probably a cop-paste error from the Truthy cases. \$\endgroup\$
    – Laikoni
    Commented Apr 24, 2022 at 19:43
2
\$\begingroup\$

Sequence of integers not the sum of powers of earlier terms

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

Convert to Shorthand (Part 1, Part 2)

\$\endgroup\$
5
  • \$\begingroup\$ Conjunction points of O P X Y may be ambiguous. \$\endgroup\$
    – tsh
    Commented Apr 26, 2022 at 12:08
  • \$\begingroup\$ @tsh I am thinking of allowing multiple correct answers for the same input. To make it slightly more precise I have added more rules and improved the examples. \$\endgroup\$
    – Saphereye
    Commented Apr 26, 2022 at 12:14
  • 3
    \$\begingroup\$ I feel like this are actually two challenges in one: 1. transcribe to the weird alphabet 2. make this "interconnected". I suggest splitting to two challenges. \$\endgroup\$
    – pajonk
    Commented Apr 26, 2022 at 17:57
  • \$\begingroup\$ I see you posted the first part, please edit this post or post a new one so that we can discuss the details of the second part (if you like). \$\endgroup\$
    – pajonk
    Commented Apr 27, 2022 at 5:12
  • \$\begingroup\$ @pajonk Thank you for the interest. I am thinking of putting all details in the same question to avoid clashing of data. This question is still the umbrella goal I am trying to achieve with it. I will be editing details once I get more suggestion from the posted questions \$\endgroup\$
    – Saphereye
    Commented Apr 27, 2022 at 8:00
2
\$\begingroup\$

Modular tetration

Tetration is the operation of repeated exponentiation. That is \$ ^{n}a = a ^ {. ^ {. ^ {.^a}}} \$, with \$ a \$ appearing \$ n \$ times.

Tetration grows extremely fast - \$ ^6 2 \$ would take significantly more digits to write then there are atoms in the known universe.

However, to work with big numbers, we can operate on them modulo some number \$ m \$.

Your task is to calculate \$ ^n a \mod m \$, with integer \$ 1 < a,n < m \$.

Rules

  • You may use any consistent reasonable I/O method.
  • The complexity of your answer must be \$ O(m) \$, where \$ m \$ is the modulus. In particular, you can't calculate \$ ^{n}a \$ with arbitrary precision and then modulo by \$ m \$.
  • Standard loopholes are disallowed.
  • Your algorithm must work for all values, but it's allowed for your program to fail due to integer overflow.

Test cases

The format for the test cases is a n m -> answer (however, you can take your input in any order) [Sandbox note: TODO - there's an error in my program]

This is , so the shortest answer in bytes wins.

\$\endgroup\$
2
  • \$\begingroup\$ I don't really know how to compute \$O\$ here, but would this algorithm satisfy the requirement on \$O(m)\$? \$\endgroup\$
    – pajonk
    Commented May 13, 2022 at 11:03
  • \$\begingroup\$ @pajonk it depends on the implementation. If you calculate euler's totient by going over all numbers from 1 to m and calculating the gcd it wouldn't, since calculating the gcd is logarithmic time, so it'll be \$ \Theta(m \log m) \$. If you calculate it by factoring \$ m \$ in \$ o(m) \$ time then it's fine. \$\endgroup\$ Commented May 13, 2022 at 11:49
2
\$\begingroup\$

Write a (simplified) BitCycle Interpreter

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

Convert Alpha-2 to Alpha-3

\$\endgroup\$
1
  • \$\begingroup\$ I liked the back story, personally. \$\endgroup\$
    – Qaziquza
    Commented May 13, 2022 at 16:49
2
\$\begingroup\$

There's more than one way to skin a set

\$\endgroup\$
5
  • \$\begingroup\$ You may want to clarify that when summing the subset, one may take a number only once and that the order doesn't matter. Also subjective suggestion: allow only inputs of length >1 (or even >2). \$\endgroup\$
    – pajonk
    Commented Apr 9, 2022 at 19:35
  • \$\begingroup\$ Description could be clearer, possibly something like "given a set S of integers, output all the integers that are the sum of multiple subsets of S" would be less wordy and clearer, also outputting a "set" is probably not necessary, as I feel that whitespace delimited strings or simple lists would work, especially since not all langs have a specific concept of a set \$\endgroup\$
    – des54321
    Commented Apr 11, 2022 at 16:48
  • \$\begingroup\$ also possibly add a few comments onto the test cases to explain them a bit more, eg. on test case 3 adding a comment like "21 can be 10+11 or 9+12" \$\endgroup\$
    – des54321
    Commented Apr 11, 2022 at 16:51
  • \$\begingroup\$ @des54321 It's pretty standard that "outputting a set" doesn't literally mean a builtin set type, it just means some kind of list-y thing \$\endgroup\$
    – pxeger
    Commented Apr 11, 2022 at 16:55
  • \$\begingroup\$ @pxeger, fair enough, although you may want to explicitly specify strings with just whitespace separators if you want to allow that as output, as especially with the current format of your testcases that does feel slightly like its not allowed \$\endgroup\$
    – des54321
    Commented Apr 11, 2022 at 16:57
2
\$\begingroup\$

I want 8 bits for every character!

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

Convert Klingon romanization to pIqaD


Context

Klingon is a constructed language from Star Trek. It has two writing systems: a not-very-good Latin alphabet (with case distinctions, I being different from l, ...) and its own script, called pIqaD.

Task

Convert the bad[disputed - discuss] Klingon romanization into pIqaD. Here's a CSV (the pIqaD [or, if you don't have a font for it, boxes or nothing] is in the second column and the Unicode hexadecimal codes are in the third):

a,,f8d0
b,,f8d1
ch,,f8d2
D,,f8d3
e,,f8d4
gh,,f8d5
H,,f8d6
I,,f8d7
j,,f8d8
l,,f8d9
m,,f8da
n,,f8db
ng,,f8dc
o,,f8dd
p,,f8de
q,,f8df
Q,,f8e0
r,,f8e1
S,,f8e2
t,,f8e3
tlh,,f8e4
u,,f8e5
v,,f8e6
w,,f8e7
y,,f8e8
',,f8e9

Be careful not to mix up q and Q, they are different letters in Klingon!

Input and output

Strings! or your language's equivalent. You can assume that the input contains no characters not in Klingon (incl. miscapitalized dhis) or numbers or punctuation.

Scoring

Lowest byte count wins, as always.


suggestions? :)

\$\endgroup\$
3
  • \$\begingroup\$ I like it! It seems ready for publication. \$\endgroup\$
    – Qaziquza
    Commented May 25, 2022 at 21:34
  • 1
    \$\begingroup\$ My browser shows only in the second column of the csv. Maybe add a link to TIO or other external page, which will render it correctly. If possible, you may also add UTF codes for those characters. \$\endgroup\$
    – pajonk
    Commented May 26, 2022 at 10:02
  • \$\begingroup\$ @pajonk i added the unicode codes :) \$\endgroup\$
    – matt
    Commented May 29, 2022 at 14:28
2
\$\begingroup\$

Generate Fibonacci Primes Quickly

Unsurprisingly, fibonacci primes are primes that are also Fibonacci numbers. There are currently 34 known Fibonacci primes and an additional 15 probable Fibonacci primes. For the purpose of this challenge, the Fibonacci numbers are the sequence \$F_n\$ defined as \$F_1 = 1\$, \$F_2 = 1\$, and \$F_n = F_{n-1} + F_{n-2}\$, and a number is considered prime if it passes a probabilistic prime test with a probability of being incorrect of less than \$2^{-32}\$. For example, since a \$k\$ round Miller-Rabin test has an error probability of \$4^{-k}\$, a 16 round Miller-Rabin test is sufficient to prove primality for the purpose of this challenge.

Submissions:

The goal of this challenge is to write a full program that calculates every Fibonacci prime and its index in the Fibonacci series as fast as possible.

Submissions shall be a full program, complete with instructions for building and running it. Submissions must be in a language freely available for noncommercial use and capable of running on Windows 10, and users must be prepared to provide installation instructions for that language. External libraries are permitted, with the same caveats that apply to languages.

Primes will be output by writing to stdout with a simple binary format, that has a little-endian byte order:

[8 bytes- index into the Fibonacci series]
[8 bytes- length of the Fibonacci prime, in bytes]
[? bytes- the Fibonacci prime, as a byte array]

Scoring

The programs will be run on an Intel(R) Core(TM) i5-8365U CPU with 8 threads, avx-2 support, and 24 Gigabytes of ram. The largest prime that can be correctly reached in one minute wins. Tiebreaker is the time taken to reach the largest value. Programs that tamper with my computer or the testing program will be disqualified. Programs that error or otherwise fail to produce the correct output will be judged based on the furthest Fibonacci prime reached before they failed.

see also: A005478, A001605

The test program can be found here. Additionally, there is an example program here.

Meta

The test program is now completed and posted, but I still have a little documentation to write. I chose the output format to be simple, and so that answers wouldn't have to worry about formatting integers quickly. Is there anything I need to improve clarity-wise?

tags:

\$\endgroup\$
4
  • \$\begingroup\$ Since there are only 34 (?+15) of them, how will you stop a program from hard-coding these, and then starting looking for larger ones from the last of them onwards? \$\endgroup\$ Commented May 22, 2022 at 10:02
  • \$\begingroup\$ @DominicvanEssen tweaked the question to use "calculate" instead of "list", which has worked for other challenges in the past. I also posted the controller. \$\endgroup\$
    – Aiden4
    Commented May 30, 2022 at 5:30
  • \$\begingroup\$ How is the "error bound" of a "probable prime" defined? \$\endgroup\$
    – pxeger
    Commented May 30, 2022 at 15:07
  • \$\begingroup\$ @pxeger I hopefully clarified what I meant, by error bound I meant error probability. \$\endgroup\$
    – Aiden4
    Commented May 30, 2022 at 17:01
2
\$\begingroup\$

Fill the rectangle

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

`lol` is an ambigram, `dad` isn't

\$\endgroup\$
3
  • 1
    \$\begingroup\$ I think you mean "rotated", not "reversed". Related, Related, but not a dupe of either. \$\endgroup\$ Commented May 30, 2022 at 5:20
  • 2
    \$\begingroup\$ I think using the word "palindrome" is misleading here. Palindrome is specifically for reversing right-to-left, not rotating. Also, please specify what kind of rotation is required (180 deg around the center of the word, isn't it?) and add some longer test-cases with various length. Please also specify what to do with empty string. Suggestion: make this decision-problem, not a "filter a list", because now it requires some needless boring boilerplate code. \$\endgroup\$
    – pajonk
    Commented May 30, 2022 at 10:08
  • \$\begingroup\$ I've edited this down to a stub now that it's been posted to save space \$\endgroup\$ Commented Jun 4, 2022 at 2:50
2
\$\begingroup\$

How much more to a repdigit?

\$\endgroup\$
1
2
\$\begingroup\$
\$\endgroup\$
0
2
\$\begingroup\$

Enumerate all pure sets

\$\endgroup\$
2
  • 1
    \$\begingroup\$ sequence IO? \$\endgroup\$
    – pxeger
    Commented Jun 12, 2022 at 9:05
  • \$\begingroup\$ @pxeger Good idea :P \$\endgroup\$
    – emanresu A
    Commented Jun 12, 2022 at 9:13
2
\$\begingroup\$

Is it a heapable sequence?

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

Find the walls!

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

Interpret BigTalk

Talk is a language which takes a single bit of input and has four commands:

  • 00 If the accumulator is 0, set the accumulator to 0.
  • 01 If the accumulator is 0, set the accumulator to 1.
  • 10 If the accumulator is 1, set the accumulator to 0.
  • 11 If the accumulator is 1, set the accumulator to 1.

These can be interpreted as replacement commands. We're going to extend that concept to positive integers, and make the language more complicated.

The language we're going to be defining is called BigTalk. It has an accumulator, which is a list of positive integers, initially set to only the input.

Programs are a series of commands. Each command is a pair of lists of integers, like ([24, 2], [32, 1]), and means to replace the first as a sequence with the second, as many times as it occurs.

The program runs repeatedly until the accumulator does not change. Finally, the accumulator is output.

For example, with the input [5, 5, 5, 5] and the program ([5, 5], [3, 2, 1]), ([3], [5]), ([2, 1, 5], [5, 1, 2]), the list goes:

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

Your challenge is to interpret this language. You may take input and program in any reasonable format.

This is , shortest wins!

Testcases

In the format of input, commands.

[5, 5, 5, 5], ([5, 5], [3, 2, 1]), ([3], [5]), ([2, 1, 5], [5, 1, 2]) -> [5, 2, 1, 1, 2, 2, 1]
[4], ([4], [4, 4]) -> Infinite loop
[2, 19, 13], ([13, 19], [2]) -> [2, 19, 13]
[39, 1, 23], ([1], [39, 23]), ([39, 39], [1, 1]), ([23, 23], [1]) -> [39, 23, 39, 23, 39, 23]

This language may be Turing-complete, and I have a +50 bounty for someone who proves it either way.

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

How far from binary?

\$\endgroup\$
3
  • \$\begingroup\$ Your description doesn't quite match your test cases. It should probably say that the absolute value of n-m is composed only of 1s and 0s. Since negative numbers have -. \$\endgroup\$
    – Wheat Wizard Mod
    Commented Jun 15, 2022 at 8:40
  • \$\begingroup\$ @WheatWizard Why is it necessary? -101 is a signed binary. \$\endgroup\$
    – Fatalize
    Commented Jun 15, 2022 at 8:46
  • 1
    \$\begingroup\$ -101 is not a binary string. It might be reasonable to interpret the intended way, but I certainly think it's more reasonable to interpret it another way. I don't see any harm in being explicit. \$\endgroup\$
    – Wheat Wizard Mod
    Commented Jun 15, 2022 at 8:48
2
\$\begingroup\$

Parse this handy graph format

There's a great number of ways to represent directed graphs like the following: Three examples of directed graphs

Most representations are tailored towards being easy to work with, either for humans (like the picture above) or for computers (like an adjacency matrix representation). A middle ground I found useful in the past is this format:

        A -> B <-> C                A -> B -> C -> A           A -> C -> D; B <-> C <-> E

It is basically a condensed edge list, which is still relatively close to a graphical representation (good for humans) but not too hard to parse for a computer.

The goal in this challenge is to take a string representing a graph in this format as input and output a list of the graph's nodes and a list of the graph's edges.

This is , so try to use as few bytes as possible in the language of your choice.

Input specification

  • Each node has a unique name consisting of alphabetical letters, for example A, b, or Node. It is also fine if you only support upper or lower case names.
  • Three types of arrows can appear: ->, <-, and <->.
  • A chain is formed by a sequence starting with node and then alternating between arrows and nodes, for example A -> B <- C or also just A.
  • A chain may be followed by another chain with ; as a separator in between.
  • Between node names and the arrows and the semicolon can be any number of spaces (including zero).
  • Self-loops are possible, i.e., A -> A describes an arrow from node A to itself.
  • You may assume the input string is a valid encoding of a graph.

Output specification

  • The list of nodes can be returned or printed in any reasonable format and order, e.g., A, B, C, ["A", "B", "C"], A\nB\nC, ...
  • Edges are represented as ordered tuples in any reasonable format, e.g., ("A", "B") or A B for the edge A -> B and ("D", "C") or D C for the edge C <- D.
  • The list of directed edges can again be output in any reasonable format.

Test cases

"A -> B <-> C"               : ["A", "B", "C"], [("A", "B"), ("B", "C"), ("C", "B")]
"A -> B -> C -> A"           : ["A", "B", "C"], [("A", "B"), ("B", "C"), ("C", "A")]
"A -> C -> D; B <-> C <-> E" : ["A", "B", "C", "D", "E"], [("A", "C"), ("C", "D"), ("B", "C"), ("C", "B"), ("C", "E"), ("E", "C")]
"AA<->BB"                    : ["AA", "BB"], [("AA", "BB"), ("BB", "AA")]
"A;B"                        : ["A", "B"], []
" "                          : [], []
"   A   <- B  ;  C  "        : ["A", "B", "C"], [("B", "A")]
"A -> A; B <- B"             : ["A", "B"], [("A", "A"), ("B", "B")]

Sandbox question:

Given that this is foremost a question, I'm tempted to drop the validity assumption and require answers to raise an error if the input does not follow the spec. What do you think, would that still be fun?

\$\endgroup\$
2
  • \$\begingroup\$ Definitely don't require validity. That makes the challenge two quite different challenges, and is in no way necessary. \$\endgroup\$
    – emanresu A
    Commented Jun 27, 2022 at 1:00
  • 1
    \$\begingroup\$ ^ probably a typo, but 100% you should allow users to assume validity. Don't require validity checking. \$\endgroup\$ Commented Jun 30, 2022 at 2:06
2
\$\begingroup\$

Flood fill by distance

\$\endgroup\$
2
  • 1
    \$\begingroup\$ I suggest using a different character than O for obstacles, because it looks too much like 0. Maybe #? \$\endgroup\$
    – pxeger
    Commented Jun 20, 2022 at 12:52
  • 1
    \$\begingroup\$ In your third code block, the last two grids still use O intead of X in two places each. \$\endgroup\$
    – naffetS
    Commented Jun 25, 2022 at 21:24
2
\$\begingroup\$

Nest some addition

  • There's a natural follow-up with the other possible addition operator, where the order of application is reversed, i.e. \$\operatorname{add2}\overparen{\underparen a}\overparen{\underparen b} f=\left(\overparen{\underparen b} f\right)\circ\left(\overparen{\underparen a} f\right)\$.
\$\endgroup\$
10
  • \$\begingroup\$ Even though I've dabbled in similar contexts before, I would have been helped by a reminder to think of everything in terms of functions which act on functions. \$\endgroup\$
    – aschepler
    Commented Jun 20, 2022 at 21:05
  • \$\begingroup\$ It looks like the multiplication and exponentiation rules are part of the "Task", but if I understand right they're really an additional comment on add or a hint which could be useful for understanding / implementing / verifying behavior. \$\endgroup\$
    – aschepler
    Commented Jun 20, 2022 at 21:14
  • 1
    \$\begingroup\$ @thejonymyster add is binary, since it expects two curried arguments. \$\endgroup\$
    – att
    Commented Jun 20, 2022 at 22:14
  • 1
    \$\begingroup\$ May I take input as \$x_0,\dots,x_a\$ without taking the integer \$a\$? \$\endgroup\$
    – alephalpha
    Commented Jun 23, 2022 at 11:45
  • \$\begingroup\$ @alephalpha that should be allowed by default \$\endgroup\$
    – att
    Commented Jun 23, 2022 at 18:21
  • \$\begingroup\$ I think the \$ \mathsf {formatting} \$ might be clearer if you denoted "Church numeral of \$ n \$" as something like \$ [n] \$. Because at the moment, it's not entirely clear that \$ \mathsf {a^b} \$ means \$ [a^b] \$ and not \$ [a]^{[b]} \$ (which doesn't make any sense) \$\endgroup\$
    – pxeger
    Commented Jun 27, 2022 at 7:21
  • \$\begingroup\$ @pxeger What do you think about \$\overparen{\underparen n}\$ / \$\overparen{\underparen{a^b}}\$ (or maybe only over)? I feel like braces add a bit too much clutter. \$\endgroup\$
    – att
    Commented Jun 27, 2022 at 19:36
  • \$\begingroup\$ @att Sure, both work fine \$\endgroup\$
    – pxeger
    Commented Jun 27, 2022 at 19:38
  • \$\begingroup\$ @thejonymyster I think "where ∘ denotes function composition" should be sufficient (it's also defined as the multiplication rule) \$\endgroup\$
    – att
    Commented Jun 27, 2022 at 22:22
  • \$\begingroup\$ Oh, i skimmed right over that. I guess my friend just can't read :P \$\endgroup\$ Commented Jun 27, 2022 at 22:35
2
\$\begingroup\$

Is this a squashed series?

Given a string of digits, determine whether it is the concatenation of at least two ascending consecutive integers. (in decimal, with no leading zeroes)

For example, the string 7891011 is valid, because it's the concatenation of the sequence [7, 8, 9, 10, 11].

However, the string 54 could only be formed by concatenating [5, 4] (which is not ascending), or [54] (which does not have at least two numbers in it), so it is not valid.

(This challenge is essentially asking "Is it a valid input to Decipher a squashed series")

You should output using two distinct values of your choice to represent "valid" and "not valid".

Take care with leading zeroes: for example, 809 is not valid, even though it could be decomposed into [8, 09], because 09 is not a valid decimal integer.

You may assume the input does not start with a 0, and has a length of at least 2. The input will also only contain digits (and not -, so you don't need to handle negative numbers).

This is , so the shortest code in bytes wins.

Test cases

Valid

1234
7891011
293031323334
9991000

Invalid

54
66
28
3131
809

Valid numbers are given by A035333 in the OEIS.

Meta

  • Is this interesting enough? (It was just a byproduct of Decipher a squashed series)
  • Is my handling of the 809 case good? Or should I allow either output for inputs like that?
\$\endgroup\$
2
  • 2
    \$\begingroup\$ In Brachylog, this would be the exact same answer as your previous challenge, but I guess it’s mostly because of the declarative nature of the language. I don’t know if that’s interesting enough compared to the othe challenge with other language paradigms. \$\endgroup\$
    – Fatalize
    Commented Jun 28, 2022 at 13:58
  • \$\begingroup\$ Fwiw, in 05AB1E it isn't the exact same answer, but it's a pretty trivial change. My initial answer was .œ.Δ¥P; and it would be .œʒ¥P}g without the 809 test case or .œʒ¥P}ïJQO with the 809 test case (both outputting 2/1 for truthy/falsey respectively). So the 8,09 test case definitely adds something interesting, although 05AB1E's "09"==9 being truthy makes it a bit more tricky than in most other languages I'd imagine. \$\endgroup\$ Commented Jul 8, 2022 at 14:21
1
42 43
44
45 46
157

You must log in to answer this question.

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