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

Von Neumann Probe Battle (king-of-the-hill)

---

This is just an idea for now, placing it here as a draft and to collect feedback.

Basically, your goal would be to design a set of machines, including factories and spacecraft, which start on earth and spread outward into the universe. You'd be able to design these machines. Not just their code, but the parts that make them up.

For example, you could start on earth with a single factory, which would make a swarm of mining bots. These would bring ore to the surface, and the factory would switch to making spacecraft. Once the spacecraft are built, the factory could assemble all of the parts needed to make an identical factory, load them onto the spacecraft, and send them to the moon. Then, both factories would start the process over.

The ultimate goal would be to build "stamps", which cost a small amount of iron, and then vanish from existence. These are used for scoring.

This challenge might not be very practical, due to the issues involved in simulating a detailed and exponentially increasing swarm of robots in a vast universe.

Answer 2

Pretty print my arrays

I like to pretty print multidimensional arrays, like this:

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

But it's a pain to do by hand and it'd be nice to have a program that does this for me. Your challenge is to create a program that does this for me, taking a multidimensional array containing only numbers and prettyprinting it.

Specifically, an array of depth 1 is printed joined by , with [ prepended and ] appended:

[1, 2, 3]

An array of depth \$n+1\$, which contains at least one array of depth \$n\$, has its subarrays prettyprinted, joined by newlines and indented by two spaces. All but the last subarray have a comma appended, the last has ] appended, and the first has its first line indented with [ instead of two spaces:

Here's a reference implementation:

function recursivePrettyPrint(array){
  if(array.every(x => typeof x == "number")){
    return `[${array.join(', ')}]`;
  } else {
    return array.map((item, index) => {
      let result = recursivePrettyPrint(item) + ',';
      result = result.split`\n`;
      if(index == 0){
        result[0] = '[ ' + result[0];
      } else {
        result[0] = '  ' + result[0];
      }
      for(let i = 1; i < result.length; i++){
        result[i] = '  ' + result[i]
      }
      return result.join('\n');
    }).join('\n').slice(0,-1) + ' ]';
  }
}

function change(){
  let array = JSON.parse(document.getElementById('input').value);
  let output = document.getElementById('output');
  output.innerText = recursivePrettyPrint(array);
}

<textarea id=input></textarea>

<button id=run onclick=change()>Pretty Print</button>

<pre id=output></pre>

Numbers may be multiple digits. The input will always be orthogonal/rectangular, and you may take its dimensions as well.

Testcases

[[892, 759], [962, 251]] ->
[ [892, 759],
  [962, 251] ]

[118, 922, 619] ->
[118, 922, 619]

[[966, 639, 616, 255], [622, 483, 87, 241], [453, 870, 728, 725], [163, 936, 48, 967], [261, 833, 87, 200]] -> 
[ [966, 639, 616, 255],
  [622, 483, 87, 241],
  [453, 870, 728, 725],
  [163, 936, 48, 967],
  [261, 833, 87, 200] ]

[[[[[912, 547], [366, 754]], [[723, 536], [779, 238]]], [[[559, 392], [602, 709]], [[692, 915], [412, 302]]]], [[[[3, 504], [936, 83]], [[352, 442], [425, 375]]], [[[380, 440], [793, 762]], [[850, 321], [780, 457]]]]] ->
[ [ [ [ [912, 547],
        [366, 754] ],
      [ [723, 536],
        [779, 238] ] ],
    [ [ [559, 392],
        [602, 709] ],
      [ [692, 915],
        [412, 302] ] ] ],
  [ [ [ [3, 504],
        [936, 83] ],
      [ [352, 442],
        [425, 375] ] ],
    [ [ [380, 440],
        [793, 762] ],
      [ [850, 321],
        [780, 457] ] ] ] ]

[[[128, 910, 664, 658], [172, 238, 564, 492], [325, 384, 566, 90]], [[876, 819, 764, 105], [583, 528, 731, 839], [480, 126, 692, 875]], [[215, 84, 268, 504], [400, 674, 997, 526], [799, 692, 193, 296]], [[943, 185, 567, 188], [118, 200, 879, 409], [116, 493, 62, 343]]] -> 
[ [ [128, 910, 664, 658],
    [172, 238, 564, 492],
    [325, 384, 566, 90] ],
  [ [876, 819, 764, 105],
    [583, 528, 731, 839],
    [480, 126, 692, 875] ],
  [ [215, 84, 268, 504],
    [400, 674, 997, 526],
    [799, 692, 193, 296] ],
  [ [943, 185, 567, 188],
    [118, 200, 879, 409],
    [116, 493, 62, 343] ] ]
```

Answer 3

Trap the hero in a maze

Answer 4

Ragged list addition

Let's define the operator \$+\$ as follows, using wrapping list indexing:

\$ a+b=\begin{cases} a+b,\space\text{if }a\text{ and }b\text{ are integers (regular integer addition)}\\ [a+b[0], a+b[1], ...,a+b[len(b)-1]],\text{if }a\text{ is an integer and }b\text{ is a list}\\ [a[0]+b,a[1]+b,...,a[len(a)-1]+b],\text{if }b\text{ is a list and }\text{ is an integer}\\ [a[0]+b[0], a[1]+b[1], a[2]+b[2],...,\\a[\max(len(a),len(b))-1]+b[\max(len(a),len(b))-1]],\text{if }a\text{ and }b\text{ are lists} \end{cases} \$

That is huge wall of text, so let's look at an example: We want to add the arrays \$[1,2,[5,6,7]]\$ and \$[[1],2,3,10,0,[3,0],1]\$ together

Let's start

\$[1,2,[5,6,7]]+[[1],2,3,10,0,[3,0],1]\$

We are adding two arrays, so we add element by element, looping if neccesary:

\$[1+[1],2+2,[5,6,7]+3,1+10,2+0,[5,6,7]+[3,0],1+1]\$

Now, let's get all the additions that don't involve lists out of the way

\$[1+[1],4,[5,6,7]+3,11,2,[5,6,7]+[3,0],2]\$

Next, lets look at \$1+[1]\$ and \$[5,6,7]+3\$. Here we add an integer to an array, so we just distribute the addition like so:

\$[[1+1],4,[5+3,6+3,7+3],11,2,[5,6,7]+[3,0],2]\$

\$[[2],4,[8,9,10],11,2,[5,6,7]+[3,0],2]\$

Now we have \$[5,6,7]+[3,0]\$ left. Again, we interleave the arrays, looping if necessary:

\$[[2],4,[8,9,10],11,2,[5+3,6+0,7+3],2]\$

\$[[2],4,[8,9,10],11,2,[8,6,10],2]\$

Now there are no \$+\$ signs left. Thus \$[1,2,[5,6,7]]+[[1],2,3,10,0,[3,0],1]=[[2],4,[8,9,10],11,2,[8,6,10],2]\$

Note that ragged list addition is not commutative. So \$a+b\$ is not necessarily the same as \$b+a\$.

Your code takes two ragged lists and returns their sum. Shortest code wins.

Answer 5

Animate finding the middle (hypercube edition)

Answer 6

Play a chess-like game

king-of-the-hill

Your task is to build a program that plays chess. However, it doesn't know how the pieces move before the game begins. In fact, each time it sits down at the board the pieces are different!

The game

This game is played on a 6x6 board, looking roughly like:

123451
pppppp
......
......
pppppp
123451

Each game has a time control of 1+1 (1 minute, plus 1 second per move). One piece (of 2345) is selected to be the king, and the game ends when any of the following occur:

• A king is captured (a win for the capturing player)
• 50 moves pass without a piece being captured or a pawn moving (a draw)
• One player runs out of time or attempts an invalid move. (a loss for that player)

The pieces

Pawns

Each player has 6 pawns. Pawns have at least one possible capturing move and at least one non-capturing move that moves it forward. If a pawn moves into a space on the last rank, it may promote into any non-king piece. I've listed white's moves; blacks are mirrored. Pawns may have any or all of the following:

Capturing or non-capturing

.x.
... x.x .x. ...
.p. .p. .p. xpx

Capturing only

.p. .p.
x.x .x.

Example:
In a game, pawns may be able to move to

...
.x.
xpx

And capture pieces in

x.x
.p.
xxx

Major Pieces

The major pieces are more varied, but all of their moves are symmetric. If a major piece can move to a space, it can also capture on that space. Possible moves include (not necessarily exhaustive):

.x. x.x
xPx .P.
.x. x.x

These moves may or may not include the ability to jump over pieces in between:

.x.x. x.x.x
x...x .....
..P.. x.P.x
x...x .....
.x.x. x.x.x

These moves extend across the whole board:

.x... x.x.. P....
xPxxx .P... ..x..
.x... x.x.. .x..x
.x... ...x. .....
.x... ....x ..x..

Each piece will have at least one of these (or others - no guarantees will be made that other movesets will not be included). A piece can have any number of these sets of moves. The two "1"s will have the same moves.

The controller

I haven't built this; I want to gauge interest first.

A potential spec for the controller (have to work out how it communicates):

// Return a list of possible moves in that game state
// If piece is passed (a 2-element array - [x,y]) then only moves which that piece can make are returned
getMoves(board, player, piece = null) => board[]

// Returns the number of milliseconds that player has remaining on their clock.
getTime(player) => float

// Move the piece at origin to destination
makeMove(origin, destination, promotion = null) => void

The tournament

There will be a round-robin tournament played, with as many rounds as possible. Each game will have its pieces randomized at the start, then the bots will play a game as white and a game as black (using the same pieces).

Sandbox

• Does this sound like an interesting challenge (would it be more than just "fork stockfish")?
• Would it be alright to restrict this to javascript?

Answer 7

Retaining Water

Answer 8

Can I wall glitch to there?

Posted

Answer 9

Slice the source code - Cops and Robbers

Answer 10

All sequences as substrings

Answer 11

posted

Answer 12

Make me a k-NN classifier

code-golf machine-learning The "machine-learning" tag will be created

---

The k Nearest Neighbors (k-NN) classifier is a simple machine learning classifier. Although k-NN also works for regression tasks, we will be focusing on classification tasks for this challenge.

The classifier can be customized in a number of different ways. For this challenge, the following can be customized:

• k itself;
• the distance metric; and
• the aggregation function.

Main idea

As you can probably tell by its name, k-NN works using the concept of neighbors. First, we "train" classifiers by giving it (preferably a lot of) training data.

A training data point consists of two parts: its "features" and its target value. For instance, if predicting car brand, features might be maximum speed, size etc, and the target variable would be brand. We can also specify k, a distance metric, and/or an aggregation function, or let the classifier fine-tune these hyperparameters itself. For this challenge, the above hyperparameters will be given directly to the classifier.

When we give the classifier a list of features to be assigned a predicted target value, it takes the k train points closest to the test point, measured by distance metric via features, and runs their target values through its aggregation function to obtain its prediction.

The hyperparameters are explained below:

k

k is the neighbor count. If k is 5, for instance, the classifier will consider 5 neighbors when predicting.

Distance metric

The distance metric measures how far two data points are from each other, measured by their features. A standard distance metric is Euclidean distance, but many others can be used, such as the Manhattan distance.

Aggregation function

Once the classifier has found the k nearest neighbors, it calls its aggregation function using the target values of these neighbors. A standard aggregation function for classification is majority vote, but many others can be used.

Challenge

The following are to be taken as input:

• a list of train data points where each data point consists of:
  • a list of numbers, where the lengths of these lists are the same for all training data points; and
  • a target value;
• k;
• a distance metric which takes two data points' features and outputs a positive number; and
• an aggregation function which takes k data points' target values and outputs a value that is one of the target values contained within the training data (this means that you can't just output some arbitrary number; it must be a target value for at least one of the train data points);

You may also take in the following:

• a list of features of the same length as every list of features within the training data.

Output:

• if an additional list of features was given, the prediction, found using the procedure described above, for that list of features;
• if no such list was given, a function that takes in a list of features as described above and outputs the prediction for that list of features.

Input is flexible so long as it is within reason.

The distance metric and aggregation function are black-box functions.

This challenge is code-golf, so the shortest code, measured in bytes, wins.

Test case

Given in python.

k = 5
distance = lambda a, b: sum((b[i] - a[i]) ** 2 for i in range(5)) # Euclidean distance
aggregation = lambda a, b, c, d, e: max([a, b, c, d, e], key=lambda i: [a, b, c, d, e].count(i)) # output the one with the most occurrences
train = [
 [[1, 2, 3, 4, 5], 0],
 [[2, 3, 4, 5, 6], 1],
 [[3, 4, 5, 6, 7], 1],
 [[1, 4, 5, 6, 7], 0],
 [[1, 8, 9, 9, 9], 0],
 [[9, 0, 0, 0, 0], 1],
 [[2, 3, 4, 1, 1], 1]
]

classifier_func = knn_classifier(train, k, distance, aggregation) # function output

print(classifier_func([1, 0, 0, 0, 0])) # outputs 1

---

Do we have any feedback? Duplicate? Clarification needed? Wrong terminology? Wrong test case?

Answer 13

Simulating Bombs

Answer 14

Golf the prime numbers in Shue

Answer 15

Golf the colors of a rug

code-golf kolmogorov-complexity

Background

The challenge is based on this rug:

Its colors seem very regular, but the pattern isn't obvious. However, it becomes visible when we move vertical stripes of the rug up and down:

All stripes are colored in the same way, but each stripe is offset by some height, except for a few irregularities. Also, the stripes have different widths.

First, we need to list all colors:

0: blue-ish white
1: lighter blue
2: darker blue
3: darkest blue
4: green-ish white (the color between the middle orange rows)
5: middle green
6: dark green
7: orange
8: light red
9: dark red

Now, we can lay a grid of cells of equal color over this image. I found that using a cell size of 73.5x129 pixels seems to be a good compromise between precision and compactness. This results in a 42x32 grid, which looks like this when overlayed over the rug:

Correcting for some perspective errors, we now can approximate the colors of this rug like this:

The color scheme shared by all stripes consists, from top to bottom, of these 42 colors: [3, 3, 2, 3, 3, 2, 2, 0, 2, 2, 1, 1, 3, 1, 1, 5, 5, 6, 5, 5, 6, 6, 7, 6, 6, 7, 7, 4, 7, 7, 8, 8, 7, 8, 8, 9, 9, 8, 9, 9, 9, 9]. (This already contains the information that some rows have different heights, by having multiple entries of the same color in a row.)

There are 18 stripes with widthes [2, 3, 3, 3, 1, 1, 4, 2, 1, 6, 1, 1, 2, 2, 2, 3, 2, 3]. Their vertical offsets are [3, 4, 3, 4, 2, 0, 2, 4, 7, 9, 10, 9, 5, 3, 5, 3, 4, 5], which means the first stripe starts at the color at index 3 in the common scheme, the second stripe at index 4 and so on. Starting from the respective start index, the next 32 colors are used; remaining colors (if any) are unused.

There are some irregularities in the rug. I didn't find a better way of expressing them except for listing their X and Y coordinates in the grid together with their colors:

X     [8,  9, 10, 19, 19, 12,  0,  1,  2,  3,  4,  2,  3,  4,  2,  3,  4,  5, 13, 14, 15, 16, 17, 18, 34]
Y     [18, 18, 18, 23, 24, 27, 31, 31, 29, 29, 29, 30, 30, 30, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31]
Color [5,  5,  5,  0,  0,  8,  9,  9,  9,  9,  9,  9,  9,  9,  8,  8,  8,  9,  9,  9,  9,  9,  8,  8,  9]

They are included in this challenge to better reflect the rug and to increase difficulty a bit.

Challenge

Output this 42x32 grid of numbers from 0-9, each corresponding to the color of one cell of the rug:

333333333332322223302222221222332233333222
332223332223333332221111111122332233322222
222222222223233332221111113100220022222000
220002220002322220013333331322222222200222
002220002222322222211111111122002200022222
222222222220200002231111115111221122222111
221112221112222221115555555511221122211111
111111111112022221115555556533113311111333
113331113331211113356666665611111111133111
331113331111211111155555555511331133311111
111111111113133331165555556555115511111555
115551115551111115556666666655115511155555
555555555551311115556666667666556655555666
556665556665155556667777776755555555566555
665556665555155555566666666655665566655555
555555555556566665576666667666556655555666
556665556665555556667777777766556655566666
666666666665655556667777774777667766666777
667776665556566667774444447466666666677666
776667776666566666677777777766776677766666
666666666667677776647777778777667766666777
667776667776666667778888888877667766677777
777777777776766667778888887844774477777444
774447774447677774407777778777777777744777
447774447777677777708888888877447744477777
777777777774744447778888889888778877777888
778887778887777778889999999988778877788888
888888888887877778889999998977887788888777
887778887778788887798888889888888888877888
779997778888788888899999999988778877788888
889998888887877778889999999999889988888999
998889889998899998899999999999889998899999

Rules

• The program should not take input.
• Formatting doesn't matter.
• This is code-golf, so shortest answer (in bytes) wins.

Sandbox Questions

• Why doesn't the box with irregularities align?
• Would the challenge be more fun with or without having to include irregularities? I guess allowing both variants is not a good idea because solutions aren't comparable anymore.

Answer 16

Smallest maximal rectangle in a skyline

Answer 17

Chess Board Analyzer

Answer 18

Wiggle the tower

Answer 19

Disassemble tables

Posted here.

Answer 20

Lexicographical sum

Answer 21

Random Point from a 2D Donut Distribution

Posted here.

Answer 22

Social distance the graph

Given a connected, undirected graph like so, where various nodes are connected to each other:

Select as many nodes as possible such that no two selected nodes are adjacent.

^ made by clumsy by-hand greedy algorithm, tell me if I stuffed this up. The red ones are the selected ones.

You should output the maximal number of points for which this is possible.

You can take the graph in any reasonable form - as an adjacency matrix, a list of edges, a list of nodes, etc.

The graph will have at least one edge, and no more than one edge connecting two points.

Testcases

-> 2
-> 3
-> 5
-> 5

Answer 23

String table

Posted here

Answer 24

Implement a very simple ALU using only NAND gates

Answer 25

Is it a base-\$\infty\$ prime?

To explain how base-\$\infty\$ numbers work, let's look at how base 10 arithmetic works. We can view a base 10 number as a list of digits (numbers). So 123 is [1,2,3] and so on. When we add numbers, we use the standard long addition, meaning we add digit by digit, carrying if necessary. For example, 123+798:

  ₁₁ 
  123
+ 798
-----
  921

Similarly, multiplication can be done using long multiplication. For example, 123*798:

    123
*   798
-------
    984
  1107
+ 861
-------
  98154

Now, like the name suggest, base-\$\infty\$ numbers have infinitely many possible digits. Therefore we can represent a base-\$\infty\$ number as a list of integers. For lists consisting of only non-negative numbers, addition and multiplication are straightforward. For example, [19,53,1]+[8,4]=[19,53,1]+[0,8,4]=[19,61,5] and [1,2]*[3,4]=[1,2]*[3,0]+[1,2]*[4]=[3,6,0]+[4,8]=[3,10,8]. When restricted to non-negative numbers, carrying doesn't occur.

Negative numbers however spice things up. Let's look first how [-1] works. Let's see what happens when we add [1] to it:

[-1]+[1]=[1,0]

We get [1,0]. Before explaining how this works, it may be helpful to look at a related example in base-10:

9 + 1 = 10

Do you see the similarities? Nine is just ten minus one. Anyways, what is happening is that when you cross the boundary from the negatives to the positives, you carry one, so you end up with [1,0] where the one is carried.

Let's see what happens when we add [-1] to [-1]. We can reason in this way:

[-1]+[-1]=[-1]+[1]+[-2]=[1,0]+[-2]=[1,-2]

Here is the related base-10 example:

9 + 9 = 18

Ok, here is a more complicated example

[1,3,-2,-3,6]+[1,5,-1]=[1,4,0,3,5]

And the base-10 equivalent

13876+159=14035

For singular non-negative integers, multiplication works as you'd expect:

[3]*[1,-2,3]=[1,-2,3]+[1,-2,3]+[1,-2,3]=[5,-6,9]

For singular negative integers, we can use the following trick:

[-3]*[1,-2,3]=([1,0] - [3])*[1,-2,3]=[1,0]*[1,-2,3]-[3]*[1,-2,3]=[1,-2,3,0]-[5,-6,9]=[1,-8,9,-9]

where a-b=c iff b+c=a (subtraction is well defined as long as a>=b).

Here is a base-10 example:

[-1]*[-1]=[-2,1] 9*9=81

For multiplying with longer numbers, we just distribute the addition:

[a,b,c]*[d,e,f]=[a,0,0]*[d,e,f]+[b,0]*[d,e,f]+[c]*[d,e,f]=[a]*[d,e,f,0,0]+[b]*[d,e,f,0]+[c]*[d,e,f]

Basically just doing long multiplication.

Primes

A prime number is a number which cannot be expressed as a non-trivial product. A non-trivial product is a product which doesn't contain the multiplicative identity ([1]). By convention, the multiplicative identity is not a prime.

Your task is to take a base-\$\infty\$ number as input and decide if it's a prime.

Rules

Standard decision-problem rules apply. You may assume that the input doesn't contain leading zeros. You may choose whether the additive identity (zero) is represented as [] or [0].

Mathematical definition of addition and multiplication

Addition:

[] + b = b
a + [] = a
[...ia,la] + [...ib,lb] = [...(ia + ib + carry(la, lb)), la+lb]

where

carry(a,b) = [(a < 0 and b < 0) or (a + b >= 0 and min(a,b) != 0]

Multiplication:

[] * b = []
[..ia, 0] * b = [...(ia*b),0]
[..ia,-a] * b = [...(ia + [1]), 0]*b - [a]*b
[..ia, a + 1] * b = [..ia, a]*b + b

Where a-b is the unique solution to b+x=a (guaranteed to be well defined when using the above definitions)

Test cases:

[0] -> False
[1] -> False
[2] -> True
[3] -> True
[4] -> False
[5] -> True
[6] -> False
[7] -> True
[8] -> False
[9] -> False
[10] -> False
[11] -> True
[12] -> False
[-12] -> True
[-11] -> True
[-10] -> True
[-9] -> True
[-8] -> True
[-7] -> True
[-6] -> True
[-5] -> True
[-4] -> True
[-3] -> True
[-2] -> True
[-1] -> True
[1,0] -> True
[1,1] -> True
[1,2] -> True
[1,3] -> True
[1,4] -> True
[1,-4] -> False
[1,-3] -> True
[1,-2] -> False
[1,-1] -> True
todo add more test cases

Answer 26

Spaceship shooter

Answer 27

Flipping Burnt Pancakes, but Optimally!

This is based on the Burnt Pancake problem.

In the burnt pancake problem, each “pancake” has a burnt side. You must sort these pancakes in order with the burnt side down. You may only use one tool, your spatula, which can flip the pancakes from the top of the pancake stack to where you inserted the spatula.

Flipping pancakes that have the burnt side down results in those pancakes being in reverse order and having the burnt side up, and vice versa.

For a given pancake stack, return the minimal number of flips needed to be made burnt pancake sorting.

The output must show every step of the optimal flipping process, with the position of the spatula being represented by a pipe character, and u or b after every number representing whether or not a pancake is burnt or unburnt.

Note that this is an NP-HARD problem. You may not make an approximation algorithm.

Testcases

1b2b3b4u returns the following:
 1b|2b3b4u
 1u2b|3b4u
 2u|1b3b4u
 2b1b|3b4u
 1u2u3b|4u
 3u|2b1b4u
 3b2b1b|4u
 1u2u3u4u
4b3b2b1b returns the following:
 4b3b2b1b|
 1u2u3u4u

This is fastest-algorithm, so the minimal time complexity wins.

Answer 28

Convert from Two's Complement to Decimal

Answer 29

Draw an ASCII envelope

Answer 30

Order of an algebraic number