Sandbox for Proposed Challenges

Question

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".

Answer 1

When's my weekend finally here?

Answer 2

Reverse RegEx

Take a regex a as input, output a regex b such that, for each string x, x matches a iff x.reverse matches b.

Here, regex need to support such symbols:

• .(any character expect \n)
• [abc](any character in abc)
• [^abc](any character not in abc)
• x?(appears 0-1 times), x*(appears any amount of times), x+(appears any positive amount of times)
• x{n,m}(appears n to m times, m can be omitted to mean infinite)
• (abc) (?:abc)(group block, () can be referred while (?:) can't)
• \n(refer to the latest match of n-th group)
• ^(begin of string), $(end of string) (or begin/end of line, see flags/m)
• |(or, choose one in some choices)
• Letters, \n(this n is char rather than variable, line-feed)

You need to handle flags i(ignore upper/lower case) and m(multiline, ^ and $ match begin/end of lines rather than string). You can also just pipe the flags and make the containment of regex work for all possible flags, aka. you can treat pipe free. (They refuse to allow or disallow)

Sample Input    Sample Output
/abcd/          /dcba/
/[abc]/         /a|c|b/
/[^abc]/        /[^abc]/
/(.)abc\1$/     /^(.)cba\1/
/$1/            /10% of $10/

Shortest code win

Answer 3

The Great Betting Game

Answer 4

Play Thud

Thud is a game described by Terry Pratchett in his novel, Thud!.

The game simulates a battle between the Dwarfs (in blue) and the Trolls (in green) on an octagonal board with the Thudstone (an impassable space) in the centre of the board.

I have created an environment to play the game and develop game playing code at: https://ajfaraday.github.io/Thud/dist/index.html

The challenge is to write the most successful dwarf or troll player of this game (these will be two separate challenges).

Rules

Starting with the Dwarfs, players take it in turns to move.

Dwarf Movement

On the Dwarf player's turn, they can move one dwarf piece either as a walk or a hurl.

Walk: Dwarfs can move as far as they like in any direction until they hit an obstacle (another dwarf, the edge of the board, or a troll). They can only kill a troll by walking if they are only one space away.

Hurl: If two or more dwarfs are in a line (horizontal, vertical or diagonal), they can hurl the dwarf on the end of the line, by the length of the line (e.g. in a line of 3, the dwarf on the end can be hurled 3 spaces). If a dwarf is hurled into a troll, the troll is killed, reducing the trolls score by 4 points.

Troll Movement

On the Troll player's turn they can move one troll piece, either as a walk or a shove.

Walk: Trolls can move one space in any direction, unless a troll, dwarf or the edge of the board is in the way. Whenever a troll moves, it kills all dwarfs adjacent to it's destination space.

Shove: If two or more trolls are in a line (horizontal, vertical or diagonal) they can shove the troll at the end of the line that number of spaces away, but only if any of the target space's immediate
neighbours contain a dwarf. When a troll is shoved, it kills all dwarfs on or adjacent to it's destination space.

It is not permitted for a troll to land directly on a dwarf by either walk or shove moves.

Each dwarf killed reduces the dwarfs score by 1 point.

Scores

The score is calculated thus:

• The dwarf player has one point for every dwarf remaining on the board.
• The troll player has four points for every troll remaining on the board.
• The key figure is the difference between these two. This will be used to calculate players' scores in the tournament.

Ending the game

The game ends when any of these conditions is met:

• There are no dwarfs on the board.
• There are no trolls on the board.
• Both players have declared the game over.
• The game has reached it's cut-off length of 500 moves.

How to manually play a game

• Go to https://ajfaraday.github.io/Thud/dist/index.html
• Hover the mouse over a piece to see it's available moves.
• • Safe moves are outlined in green.
• • Dangerous moves (which can be killed the next turn) are outlined in orange.
• • Killing moves are highlighted in red when the mouse hovers over them.
• Click a piece to select it for the current move.
• Click one of the available moves to move the piece.
• (You can click the relevant 'Make Peace' button to declare the game over according to that player, during their turn)

How to set up a local instance of the game

You don't have to clone the repository and use it locally to to create an entry, but it helps.

• git clone [email protected]:AJFaraday/Thud.git
• cd Thud
• npm install
• You can then run ./get_answers.sh to get the latest entries from Stack Exchange

If you prefer, you can use the github pages instance at https://ajfaraday.github.io/Thud/dist/index.html

How to customize a game

• Open /dist/index.html in your browser
• Click 'Customize'
• Select troll and dwarf clients (manual allows direct control)
• Select a turn time in milliseconds (only relevant to non-manual players)
• Click 'Run Game' to see or play the game.
• (Clicking 'Close' will not enact any changes)

Clients

The game is played by clients, which represent either a troll or a dwarf player. Each is a JavaScript class which must have these three functions:

• constructor(controller) - controller is an object which acts as your interface with the game (see below).
• turn() - This is called whenever it is your players turn to move.
• end_turn() - This is called after your player's turn is over. It can not move pieces, but can make decisions on whether or not to declare the game over.

Controller

The controller object is your client's interface with the game itself. You can find full documentation for the controller class here: https://github.com/AJFaraday/Thud/blob/main/docs/controller_interface.md

It provides these methods to interrogate the state of the game:

• turn() - Current turn of the game

• scores() - The current score

• spaces() - Every space, and what's in it

• space_info(x, y) - Detailed information on any space on the board.

• dwarves() - The location of every dwarf

• trolls() - The location of every troll

• pieces() - All pieces belonging to the current player (equivalent of dwarves() or trolls())

• indexed_dwarves() - The location of every dwarf with a fixed index

• indexed_trolls() - The location of every troll with a fixed index

• previous_move() - What got moved to where last turn

• killing_moves() - All moves which can kill one or more opponent

• current_space - Currently selected space (not a function)

• clear_space() - Empties currently selected space These methods are used to actually make your move:

• check_space(x, y)- Find out what moves are available from a given space

• select_space(x, y) - The player decides to move a piece at space.

• check_move(x, y) - Find out what will happen if you move to a place

• move(x, y) - The player moves the current piece to the selected space.

These are concerned with ending the game:

• declare(game_over) - Say whether or not your player thinks the game is over.
• opponent_declared() - Has the opponent declared the game over?

How to write a client

Warning: There is an issue with the project on Firefox (https://github.com/AJFaraday/Thud/issues/3) which prevents editing the code in the browser. This has been confirmed to work in Chrome.

• Open 'dist/index.html' in your browser.
• Click 'Customize'.
• Select 'dwarf/template' as the Dwarf player (or use another client as a starting point).
• Click 'Edit' beside the Dwarf player select.
• Write your client code in the text box provided.
• The Validate button will change colour based on whether or not the client is passes validations (see below).
• When you're happy with it, click 'Apply' (This can be done before it passes validation, but it may not actually work).
• Select a worthy opponent and click 'Run Game' to see the game.

Validations

In order for a client to work, and therefore be enterable in the challenge, it has to pass these validations:

• It must evaluate as Javascript code.
• The code must return a class, with a constructor which accepts one argument.
• Instances of this class should have functions named turn() and end_turn()
• The client must play a game until it is over (i.e. it must call a valid move during every turn call). The validator will run games against default opponents to determine if this happens.
• Does not have any forbidden terms ** game. - Only interact with the game via controller ** Math.random - Please keep it deterministic ** setTimeout or setInterval - Keep it sequential
  ** eval, require or import - Just don't

You can open the developer console (F12) to see more detailed information on your client's validation process.

How to save a client

If you have cloned the git repository, you can save your entry for future tinkering. This step is not required for entry in the challenge, but it may be helpful.

• Edit a client, as above.
• When you're happy with it (preferably if it's passing validation, too), click 'Copy' from the edit interface.
• Create a .js file in /src/clients/dwarf/entry with the name of your entry e.g. /src/clients/dwarf/entrygreat_dwarf_player.js. (This folder will not be wiped by get_clients.js)
• Run node script/get_clients.js from the Thud directory to make your entry available from the Dwarf player select. You only need to do this once to make it avilable.
• npm run build - this will keep watching for changes in your entry and updating the package.

How to enter your client in the competition

• Decide on the name of your client, your client_name must only have alpha characters and underscores.
• Answer this question with your entry
  • The first line of your answer should be your client's name as a title (with = characters under it on the second line)
  • There should be a code block containing the class for your entry (with or without the preceeding module.exports =)
  • After that please include a brief explanation of your client's behaviour, and any other information you'd like to include.

Once this is in place, anyone running ./get_answers.sh will see your client available under your username.

The GitHub Pages instance will also be updated periodically. So by making an entry, your code will be added to the repo.

Tournament rules

The tournament will pit every available dwarf client (in /src/clients/dwarf/) against every available troll client (in /src/clients/troll/), and each pairing will play exactly one game.

The difference between the two players' scores will then update a running total for each client. The winner will gain the difference, and the loser will lose the difference.

There are two winners in the tournament, the most successful troll player and the most successful dwarf player.

According to the rules, after playing a game, the players swap sides, so please also write an entry on the Troll challenge.

asymmetrical king-of-the-hill game board-game javasctript

---

This is now nearly complete (apart from some UI improvments and presenting the tournament results a bit more nicely). There's a working example of the code importer working against these two meta questions:

• Dwarf: Stack Exchange API Sandbox (dwarf edition)
• Troll: Stack Exchange API Sandbox

I could really use someone to attempt an end-to-end run at creating a client and adding it to one of these to check that my instructions are clear and everything works.

Answer 5

Print this sequence I just made up

Answer 6

Generate off-by-one regex for a string

Given an alphanumeric string as input, generate JS-flavored regex in order to match any off-by-one errors for that string. In stricter terms, your resulting regex must match any single deletions, single replacements, or single additions like in the below examples.

Examples:

"hi" -> "(h|i|.i|h.|.hi|h.i|hi.)"
"golf" -> "(olf|glf|gof|gol|.olf|g.lf|go.f|gol.|.golf|g.olf|go.lf|gol.f|golf.)"

Here is a program for generating the results.

Note: The order of the regex does not need to matter (ie, "hi" could be "(h|h.|hi.| . . .")) so long as all patterns are in the regex.

This is code-golf, so shortest program in bytes wins.

code-golf code-generation regular-expression

Answer 7

Are you a probabilist or a physicist?

Answer 8

Calculate the integer square root of a matrix

Answer 9

Pinpoint the typo!

Task

Write a program that finds the location of an error in its own code!

The program itself must output either nothing or an empty string (or an appropriate equivalent in your language).

Let n be the length of the program in bytes, which must be at least 2. For an integer k with 1<=k<=n, if the kth byte of the source code is deleted, then the resulting program should output the integer k (and nothing else), in as many cases as possible.

Outputs may be 0-indexed if preferred, so that omitting the kth byte outputs k-1, but the choice of indexing must be consistent across all k.

Error messages do not count as valid output unless they are of exactly the required form.

Your score is the number of integers k for which the above condition is satisfied, divided by n. Highest score wins, with ties broken by smallest n.

Example

Consider the program blob() in a fictitious language. Suppose that:

blob() outputs nothing (this is a requirement)

lob() outputs 1 (right)

bob() outputs 2 (right)

blb() outputs 3 (right)

blo() outputs 4 (right)

blob) outputs nothing (wrong)

blob( outputs 6: Syntax error (wrong)

Then the score would be 4/6 = 0.66666667

Answer 10

IATA Airport Codes code-golfdecision-problemstringkolmogorov-complexitycompression

Out of 17576 alphabetical triplets, to this day, 9144 are used as IATA airport codes.

Given a 3-letter string, tell whether it appears in the list.

• The input string is mixed-case by default, but you can restrict it to non-mixed-case or lower-case or upper-case

• To output the affirmative/negative outcome you should use:

  • truthy/falsy according to your language's convention (swapping is allowed), or
  • one consistent value as either affirmative or negative, and any other value as the other

• This is code-golf

_{The list was scraped from iata.org on 2021-08-07}

Meta

• Is there something that needs to be specified/clarified?

Answer 11

Sum of 3 Vectors

code-golfnumber-theory

Question

Given 3 vectors a, b, c

Find integer (n, m, r) where a*n+b*m+c*r = 0 and n,m,r are all not equal to 0.

your answer group (n, m, r) must be the closest valid group to 0, calculate by adding abs value together: |n|+|m|+|r|

You can assume that 3 vectors do not parallel

Test case

work in progress

Rules

• no Standard loopholes
• any I/O case allowed, as long as it's clear and mostly understandable.

Score

• Lowest byte count per language wins!

Meta

any extra tag?

suggestions?

Rename question?

Answer 12

Distances between keys on a QWERTY keyboard

Answer 13

Answer 14

Unfudge my terminal!

Intro

Today I fiddled around with termios for a program. The only thing I managed to do so far is fundging my terminal... can you help me out?

Challenge

Given a terminal input that contains fudged special chars, output the string that should be displayed if the terminal worked correctly. Here's a list of the broken special chars:

^B -> Backspace
^J -> (Fwd-) Delete
^W -> Discard
^D -> Cursor left
^C -> Cursor right
^F -> End
^H -> Start

How the special characters work

• Backspace deletes the character behind the cursor and moves it one step back. Has no effect on the start of the string.
• Delete deletes the character in front of the cursor. Has no effect on the end of the string.
• Discard deletes the string typed up to this point.
• Cursor left/right moves the cursor to the left/right by one. Has no effect on the end/start of the string.
• End/Start move the cursor to the end/start of the string.

Undefined special characters are to be removed.

Input

• Any represetation of a string/list of characters
• Single lines only
• The special characters may be either all capitalized or all not capitalized
• The input will not contain a sequence that will result in a ^ in the output, nor will it contain a single ^ at the end.

Output

• The unfudged input.
• No leading/trailing whitespace that isn't part of the string.

Examples

abcd^B^B^B --> a

abcd^We^Af^Lgh --> efgh

 gof^D^D^D^Dcode^C^C^Cl --> code golf

ocde gol^H^J^Jco^Ff --> code golf

edgecase^H^D^B^J^F^C^J^B --> dgecas

Rules

• This is code-golf, shortest answer wins
• Standard loopholes are not allowed
• A submissiom may be a program/function/link/lambda/chain/etc.

Tags: code-golfstring

Sandbox things

• Is anything unclear?
• Should any special char be added or removed?
• Is there an edge case not covered by the examples?
• Are the rules and I/O restrictions fine or should I change anything?

Answer 15

Snap (card game)

Answer 16

Display a number in Toki Pona

Answer 17

Khinchin's constant bad estimate

Answer 18

Unicode Calendar Generator

Rules

Your program will receive a valid date in the format relevant to your language (date object or three int for year, month, day or whatever) and should returns a fancy unicode calendar as such (note that the title is right/left aligned):

Given Y-M-D as 2021-10-13
Then

╔════════════════════╗
║ October ░░░░░ 2021 ║
╟──┬──┬──┬──┬──┬──┬──╢
║░░│░░│░░│░░│░░│01│02║
╟──┼──┼──┼──┼──┼──┼──╢
║03│04│05│06│07│08│09║
╟──┼──┼──╔══╗──┼──┼──╢
║10│11│12║13║14│15│16║
╟──┼──┼──╚══╝──┼──┼──╢
║17│18│19│20│21│22│23║
╟──┼──┼──┼──┼──┼──┼──╢
║24│25│26│27│28│29│30║
╟──┼──┼──┼──┼──┼──┼──╢
║31│░░│░░│░░│░░│░░│░░║
╚══╧══╧══╧══╧══╧══╧══╝

Given Y-M-D as 2021-11-13
Then

╔════════════════════╗
║ November ░░░░ 2021 ║
╟──┬──┬──┬──┬──┬──┬──╢
║░░│01│02│03│04│05│06║
╟──┼──┼──┼──┼──┼──╔══╗
║07│08│09│10│11│12║13║
╟──┼──┼──┼──┼──┼──╚══╝
║14│15│16│17│18│19│20║
╟──┼──┼──┼──┼──┼──┼──╢
║21│22│23│24│25│26│27║
╟──┼──┼──┼──┼──┼──┼──╢
║28│29│30│░░│░░│░░│░░║
╚══╧══╧══╧══╧══╧══╧══╝

Given Y-M-D as 2021-06-15
Then

╔════════════════════╗
║ June ░░░░░░░░ 2021 ║
╟──┬──┬──┬──┬──┬──┬──╢
║░░│░░│01│02│03│04│05║
╟──┼──┼──┼──┼──┼──┼──╢
║06│07│08│09│10│11│12║
╟──┼──╔══╗──┼──┼──┼──╢
║13│14║15║16│17│18│19║
╟──┼──╚══╝──┼──┼──┼──╢
║20│21│22│23│24│25│26║
╟──┼──┼──┼──┼──┼──┼──╢
║27│28│29│30│░░│░░│░░║
╚══╧══╧══╧══╧══╧══╧══╝

This is code-golf, so you the shortest bytes of each language will be the winner.

Inspired by qwerty.dev

Answer 19

Answer 20

Pretty print a grid of polyominoes

Answer 21

Fast Matrix Multiplicator Evaluator

Answer 22

Find the k-th order summary of a number

Posted

Answer 23

Consider all arrays of \$\ell\$ non-negative integers in the range \$0,\dots,m\$. Consider all such arrays whose sum is exactly \$s\$. We can list those in lexicographic order and assign an integer to each one which is simply its rank in the list.

For example, take \$\ell=7, s=5, m=4\$, the list could look like:

(0, 0, 0, 0, 0, 1, 4)  rank 1
(0, 0, 0, 0, 0, 2, 3)  rank 2
(0, 0, 0, 0, 0, 3, 2)  rank 3
(0, 0, 0, 0, 0, 4, 1)  rank 4
(0, 0, 0, 0, 1, 0, 4)  rank 5
(0, 0, 0, 0, 1, 1, 3)  rank 6
(0, 0, 0, 0, 1, 2, 2)  rank 7
(0, 0, 0, 0, 1, 3, 1)  rank 8
(0, 0, 0, 0, 1, 4, 0)  rank 9
[...]
(3, 2, 0, 0, 0, 0, 0) rank 449
(4, 0, 0, 0, 0, 0, 1) rank 450
(4, 0, 0, 0, 0, 1, 0) rank 451
(4, 0, 0, 0, 1, 0, 0) rank 452
(4, 0, 0, 1, 0, 0, 0) rank 453
(4, 0, 1, 0, 0, 0, 0) rank 454
(4, 1, 0, 0, 0, 0, 0) rank 455

This challenge requires you to produce two pieces of code/functions.

• Given a rank, compute the corresponding array directly. Call this function unrank()
• Given an array, compute its rank. Call this function rank()

Your code should run in polynomial time. That is it shouldn't be brute force and more specifically it should take \$O(\ell^a s^b m^c)\$ time for fixed non-negative integers \$a, b, c\$. Any non-brute force method is likely to satisfy this requirement.

Examples

unrank((7, 5, 4), 9) = (0, 0, 0, 0, 1, 4, 0)
rank((7, 5, 4), (4, 0, 0, 0, 0, 1, 0)) = 451
unrank((14,10, 8), 100000)  = (0, 0, 0, 1, 0, 0, 1, 3, 1, 2, 0, 0, 2, 0)
rank((14, 10, 8), (2, 0, 1, 1, 2, 0, 0, 0, 2, 1, 1, 0, 0, 0)) = 1000000

Your score will be the total size for your code

Answer 24

Convert codepoint to UTF-9

Answer 25

Lexigolf: Is this number a prime?

Write a program that, given a strictly positive integer n as input, determines whether n is prime and prints a truthy or falsy value accordingly.

For the purpose of this challenge, an integer is prime if it has exactly two strictly positive divisors. Note that this excludes 1, who is its only strictly positive divisor.

Goal

Competing programs are compared lexicographically. The program that is lexicographically less than all other programs is the winner.

If a program begins with a prefix that may be removed without altering the program's behavior, it is disqualified. This is to discourage adding meaningless whitespace or comments to change the first character (consider int main(){} or /**/int main(){}).

For example,

abc < def
aa < ba
aaaaaaa < aba
aa < aaaa
Zzz < aaa
012 < AAA

Meta

This is essentially an earlier classic code-golf challenge, Is this number a prime?, except with a different goal, which I propose is called lexigolf.

I'm not sure whether lexicographic order should entirely be based on UTF-8 (for languages that can be expressed in bytes). It seems to massively favor weird esolangs that rely on characters with small ASCII codes. There is also a loophole in prefixing the program with noop characters, e.g. placing a arbitrary amount of whitespace before a C program: int main() {} > int main(int, char**) {} > int main(int argc, char **argv) {} (fixed? probably still a loophole somewhere)

Answer 26

Will one-cell brainfuck halt?

Answer 27

Construct a Heptagon avoiding compass use

A while back I asked you to construct a pentagon avoiding compass use. Now flawr suggested:

Next time you should ask people to draw a heptagon, which would be slightly more challenging:)

This is of course a joke, because if you didn't already know it is not possible to construct a Heptagon using a ruler and compass ...

... in finite steps.

In this challenge answers will construct equilateral polygon of 7 sides, using a ruler and a compass.

We will begin with some standard ruler and compass operations:

• Draw a line that passes through two non-identical points. (Ruler)

• Draw a circle centered at one point such that another point lies on the circle. (Compass)

• Place a point at an intersection of two non-identical objects (a circle and a line, a line and a line or a circle and a circle)

Normally a construction must be finished after some finite number of operations. However we will allow you to take any ordinal number of steps. Meaning you can perform an infinite number of steps and then perform more.

To go with this you are given one more operation:

• Choose converging sequence of already drawn points and place a point at their limit. (limiting)

This operation is only meaningfully useful if you have already performed an infinite number of steps, but is crucial to constructing a heptagon.

Summary

In this challenge you will start with two arbitrarily placed (but non-equal) points on an infinite plane. You must then describe some sequence of steps to arrive at a regular Heptagon. Here a regular heptagon simply being 7 points which form the vertices of a heptagon, they do not need to be in any particular position relative to the starting points.

Your score will be the number of compass operations used in the entire proof with lower being better. Since many answers may end up using an infinite number of compass steps we will break ties by the strict supremum of ordinals representing steps you have used a compass.

For example if two answers both use an infinite number of compass operations, their primary score is \$\infty\$. If one of them uses all of their compasses at finite numbered their secondary score is \$\omega\$, which would beat the other answer if it uses the compass at any time \$\omega\$ and after.

Answer 28

How long will my microwave run for?

Answer 29

Operator precedence is dead

Calculate the result of some math expressions using the following constraints:

• Numbers will be between 0 and 9
• Operators are + - / *
• Expressions will always have the format Number operator number operator number...
• Parenthesis have the highest precedence
• The order of reading goes Left Left Right Right Left Left Right Right etc.
• Division by 0 never happen

For example:

1+3-4*9
1       = 1   ; Start calculating using the left most number
 +    9 = 10  ; Add 9
  3  *  = 30  ; Multiply by 3
   -4   = 26  ; subtract 4

Using this method 1+3-4*9 = 26

Input / Output

Input:

• string OR list of characters OR list of numbers and characters
• Can be reversed if specified in the answer

Output: a number

Precision

Floating point errors are OK.

More examples and test cases:

2*9 = 18

1+3-4*9
1       = 1
 +    9 = 10
  3  *  = 30
   -4   = 26

8-5*0/9+8/2+3*4
8               = 8
 -            4 = 4
  5          *  = 20
   *        3   = 60
    0      +    = 60
     /    2     = 30
      9  /      = 3.33333...
       +8       = 11.33333...

Knowing that 1+3-4*9 is 26

8-5*0/9+8/2+(1+3-4*9)*4
8                       = 8
 -                    4 = 4
  5                  *  = 20
   *        (1+3-4*9)   = 520
    0      +            = 520
     /    2             = 260
      9  /              = 28.8888...
       +8               = 36.8888...

8-2+4*6/2
8         = 8
 -      2 = 6
  2    /  = 3
   +  6   = 9
    4*    = 36

(1+2*7)*6+3+(2*2+3)

First group:
1+2*7
1
 +  7 = 8
  2*  = 16

Second group:
2*2+3
2
 *  3 = 6
  2+  = 8

(1+2*7)*6+3+(2*2+3)
(1+2*7)             = 16
       *    (2*2+3) = 128
        6  +        = 134
         +3         = 137

1+(6+(6+1*2)/2)/4
Nested group:
6+1*2
6     = 6
 +  2 = 8
  1*  = 8

Group:
6+(6+1*2)/2
6           = 6
 +        2 = 8
  (6+1*2)/  = 1

Full expression:
1+(6+(6+1*2)/2)/4
1                 = 1
 +              4 = 5
  (6+(6+1*2)/2)/  = 5

Scoring

This is code-golf, so the answer with the least amount of bytes wins.

Answer 30

Subdivide the Bezier Curve

Background

A Bezier curve is a type of curve that has a lot of applications in all sorts of places, but most commonly, in computer graphics. It has a very simple algorithm and yet can represent a wide variety of shapes with just one common formula. If you've ever used pen tools in drawing software, you're probably already familiar with the general idea behind Bezier curves.

Given an ordered list of control points, we set some parameter \$t\$ in the range \$[0, 1]\$. Then, for each \$t\$, we draw a line between each consecutive pair of control points and select a point that is \$t\$ from the starting point. For example, if we have three control points and \$t\$ is \$\frac13\$:

The purple point is \$\frac13\$ of the way from the red point to the blue point, and the black point is \$\frac13\$ of the way from the blue point to the green point. You can change the ratio and move the points around here to try it out.

Now, we have one fewer point than we initially had control points. Let these be the new control points, and do this again with the same \$t\$:

(Desmos link). Now, we finally have a single point, so that is the point we obtain for this value of our parameter \$t\$. The Bezier curve is obtained from all final points for each \$0\leq t\leq 1\$. For more points, we just repeat this for more steps. Here's what a Bezier curve with four control points looks like:

(Desmos link)

Challenge

Given a list of control points for a Bezier curve and a positive integer \$n\$, subdivide the Bezier curve into \$n\$ segments and return the points. More precisely, return the output points for \$t=0,\frac1n,\frac2n,\cdots,\frac{n-1}n,1\$.

You may do I/O in any reasonable format; for example, a list of pairs or a pair of x and y coordinates for input, and a pair of numbers for output. Floating point errors are acceptable but your outputs should have an accuracy of at least \$10^{-3}\$ relative or absolute, whichever is larger.

There will be at least one point and \$n\$ will be a positive integer.

Example

Given input \$\{(0,0),(1,3),(4,2),(5,1)\}\$ and \$3\$ subdivisions:

For \$t=0\$, we just have \$(0,0)\$, and for \$t=1\$ we just have \$(5,1)\$.

For \$t=\frac13\$, we first go \$\frac13\$ of the way from each control point to the next to get \$\{(\frac13,1),(2,\frac83),(\frac{13}3,\frac53)\}\$. Repeating that once more gives us \$\{(\frac89,\frac{14}9),(\frac{25}9,\frac73)\}\$. Finally, if we do it once more, we get the single point \$(\frac{41}{27},\frac{49}{27})\$.

For \$t=\frac23\$, we first get \$\{(\frac23,2),(3,\frac73),(\frac{14}3,\frac43)\}\$, then \$\{(\frac{20}9,\frac{20}9),(\frac{37}9,\frac53)\}\$, and finally, \$(\frac{94}{27},\frac{50}{27})\$. And just for a sanity check, the points are indeed on the curve:

Note that these points do not evenly subdivide the Bezier curve by arclength. The arclength of a Bezier curve actually cannot be calculated exactly and subdividing like that would have to be done via approximations.

Test case generator

_{Credit to Wezl for the original idea.}