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

If it floats, it boats!

code-golf

The goal of this challenge is to determine whether or not an ASCII-art shape will float. Like any other boat, ASCII boats obey the law of buoyancy: it will float if it displaces an equal mass of water.

ASCII boats are made out of O characters arranged in some contiguous shape (diagonals are connected). There may be trailing spaces, but the whole input is a rectangle (trailing newline optional). Example boat:

   O         O    
    O        O    
     OOOOOOOOO    

The material of the boat has twice the density of water. When a boat is floating, the number of displaced water characters is at least twice number of O character in the boat. Here is an artist's impression of a boat while floating.

   O         O    
~~~~O        O~~~~
~~~~~OOOOOOOOO~~~~
~~~~~~~~~~~~~~~~~~

This boat has 13 O characters, but displaces 19 water characters, so it floats.

The key to floating is the creation of an air pocket. Air pockets can be formed in two ways: either the water cannot reach the pocket (because the boat has walls keeping it out), or air is trapped in the pocket and cannot escape. Here's an example of a capsized boat which can still float (warning: do not attempt at home).

     OOOOOOOOO
~~~~O        O~~~~
~~~O         O~~~~
~~~~~~~~~~~~~~~~~~

The following shapes aren't boats because they can't float:

OOO
O  
O  
O  
OOO

   O         O    
    O        O    
     OOOOOOOOO    
             O    
         OOOOOOOOO
         OOOOOOOOO
         OOOOOOOOO

The Goal

Write a program that, when given an ASCII-art shape, outputs a truthy value if it boats, and a falsey value if it doesn't boat. This is code golf, fewest bytes wins.

Answer 2

Multiples - a wrap battle

king-of-the-hill

---

Overview

Change cells in multiples to wipe out your opponent, while avoiding being wiped out yourself.

---

This is a 2 player game, played on a linear string of cells of length L that wrap in a loop. Counting along the loop eventually brings you back to where you started (after L steps). L will be fixed across all battles, and will be a reasonably large prime.

Each cell is controlled by player 1, player 2, or is neutral. These will be indicated as 1, 2 and 0 respectively.

Starting position

Player 2 starts with a cell at position 0 (since all are equivalent).

Player 1 starts with a randomly chosen cell from 1 to floor(L/2).

Player 1 moves first, reflecting the fact that player 1 has further to go to catch player 2.

Taking a turn

Each player begins with a stockpile of 0, and at the start of each turn the player's stockpile is increased by the number of cells that they currently control. The player then takes their turn. They choose any cell they control and specify a number N, which can be any non-negative integer up to and including the size of the stockpile. The stockpile is reduced by this number, and N loop cells are affected as follows:

Starting with the chosen cell as cell 0, each of the cells N, 2N, 3N, ... N*N are changed.

• Choosing 0 means nothing happens, at zero cost.
• Choosing 1 means the cell immediately after the chosen cell is changed, at a cost of 1.
• Choosing 2 means the cell 2 cells on and the cell 4 cells on are changed, at a cost of 2.
• Choosing 3 means the cells 3, 6 and 9 cells on are changed, at a cost of 3.
• In general, choosing N changes N cells at a cost of N.

When a cell is changed it follows the following rules:

• A neutral cell becomes the player's.
• An enemy cell becomes neutral.
• A cell already owned by the player becomes the enemy's

Large N

I expect most moves will choose N considerably smaller, but saving up would allow choosing N considerably larger than L in theory.

Choosing N=L means that all of the changed cells will be the same - the chosen cell, and it will be changed L times.

Choosing N=L-1 means that the L-1 consecutive cells before the chosen cell will all be changed (that is, every cell except the chosen one will be changed).

Winning

If a move leaves no enemy cells remaining, that player wins.

After 1000 moves any player who has more cells than their enemy at the start of 2 consecutive turns in a row (one theirs, one their enemy's, in either order) wins.

After 2000 moves the game is a draw (tie).

---

Input and output

Input

At the start of a game the player's code will be called with a command line argument of 1 or 2 indicating which player they are (player 1 moves first and is represented by 1s in the loop string).

Each turn the player will be supplied with:

• A string of 0s, 1s and 2s representing the loop.
• An integer S representing the size of their stockpile.
• An integer R representing the size of their opponent's stockpile.
• An integer representing the number of turns taken so far (this will always be an even number for player 1).

Output

The player should output 2 integers:

• The cell C to play from, in the range 0 <= C < L.
• The number of cells to change N, in the range 0 <= N <= S (their current stockpile size).

---

Sandbox questions

• I like the idea of this being a 1 dimensional game, but I can also see it working on a 2d grid, where each move is applied both horizontally and vertically (either on a square L by L, or with 2 distinct large primes as side lengths). Does anyone have anything for or against either 1d or 2d?

• Any recommendations on what input to provide? I was thinking at least the values of all the cells, but would a history also be good, or better to make the players decide what history to track for themselves rather than providing it? Alternatively they could be memoryless and decide purely based on the current cell formation.

• Is the random starting position a good idea? Would it be better to fix the starting position at floor(L/2), ensuring this number is prime, and let the players taking turns to be player 1 balance out any bias?

Answer 3

Help Indiana Jones and his crew cross the bridge!

This codegolf will solve the Bridge and Torch problem. In this problem, there are multiple people (I'm thinking four) who must all cross a weak bridge to escape an evil dragon as quickly as possible. Because the bridge is weak, only two people can cross the bridge at a time. The whole crew is armed with one torch, which is necessary for 1 or 2 people to cross the bridge. Furthermore, each person takes a certain, integral amount of time to cross the bridge. When two people cross together, they must run at the rate of the slower person. The whole crew needs to quickly figure out how to get all the people across the bridge in the least amount of time to maximize their chances of survival.

Input A list of names of the crew (one word, a-zA-Z) and how long they take to cross the bridge alone.

Output An explanation of who crosses the bridge in which order so that the total time is minimized, and the total time.

Example Input: Indiana 5 Jones 10

Output:

Indiana, Jones 10

Input: A 1 B 2 C 5 D 8

Output:

A, B A C, D B A, B 15

I'm thinking of either just solving this problem with any number of people, or another version in which anyone not at the end (ie. on the first side or on the bridge) after the time limit dies, and the goal is to minimize the number of deaths.

Answer 4

Bad Lip Reading Generator

A malapropism is the substitution of one word for another that sounds similar, often as a way to make something sound unintentionally humorous. For example, "He's a wolf in cheap clothing" is a malapropism, since the expected word, "sheep's", got replaced by "cheap", which sounds similar but means something different.

A modern version of malapropism is to take scenes from movies and redub the dialog with different words that match the actors mouth movements as a parody. There is a YouTube channel called "Bad Lip Reading" that uses this technique.

I would like to apply the process to some old videos with subtitle files, then watch the videos with the sound turned down to turn it into a long series of malapropisms.

Using mouth movements gives a more flexible range of malapropism so there is some flexibility between different sounds.

Challenge

Create a malapropism generator. I want to be able to feed text from subtitles into the generator and have text which is different, but still matches the mouth movements of the actors.

Input

A string of English words, (already processed to remove punctuation and forced to uppercase).

Output

A string of English words, (same format as input).

Notes

To simplify the challenge, all input words are in upper case, separated by whitespace, with all punctuation except apostrophes removed.

Lets agree to constraint what words "sound like", to be based on the CMUDICT. You may scrub the data so you don't have to worry about comments or special punctuation entries and remove stress numbers.

Lets also agree on the mouth-movements associated with the sounds, called "visemes". Here is a mapping used by Microsoft's SAPI library, which is itself based on Disney animation rules. Microsoft uses the same set of phonemes from ARPABet as CMUDict data.

#   ARPAbet Phoneme

1   AE AH
2   AA
3   AO
4   EH EY UH
5   ER
6   IH IY Y
7   UW W
8   OW
9   AW
10  OY
11  AY
12  HH
13  R
14  L
15  S  Z
16  CH JH SH ZH
17  DH TH
18  F  V
19  D  N  T
20  G  K  NG
21  B  M  P

You should be able to take each English word, convert to a set of phonemes, then to a set of visemes, then produce a list of words with matching visemes and randomly select one of the other words from the list. If a word doesn't match, or doesn't have any alternative, the original word should be copied to output.

Examples

• "HELLO WORLD" "HALLOW WHIRLED"
• "I SEE DEAD PEOPLE" "EYE SEA TED PEOPLE"
• "I WILL BE BACK" "EYE WHEEL PEA BAG"
• "IT WAS BEAUTY KILLED THE BEAST" "INN WAS PUNY GILT THE MIST"
• "MAY THE FORCE BE WITH YOU" "MAY THE FOURS BEE WITH YEW"

Test Cases

Since the words are random, I have selected some pairs of words with unique pronunciation. Your function or program should always return one word when presented with the other:

Input            Output
"AMUSING"        "ABUSING"
"APOGEE"         "APACHE"
"BACKDATING"     "MAGNETIC"
"BALLOONING"     "POLLUTING"
"INVISIBLE"      "INFEASIBLE"
"LAMPS"          "LUMPS"
"SCORN"          "SCORED"
"WEPT"           "WEBBED"

Rules

• You can write a full program or function.
• Input should be taken from stdin or function parameters. Output should be printed through stdout or returned.

Scoring

This is [code-golf]. Submission with least number of bytes, (not including data file(s)) wins.

Answer 5

Cake

---

Concerns:

• I'm not sure how well single language questions do. It automatically limits the question to those that already know the language, and those that are willing to learn just for this question. There's no need to limit to Chef with some of the magic this community can produce!

• "selfish/demanding" sounds quite strong and could sound like a bit of a personal attack on Beta Decay. It certainly isn't intended like that, and I expect it will be accepted as intended, but is it better to err on the side of caution?

Answer 6

Source code ecological footprint

You've just been hired by a German car manufacturing company. Your first task, as an engineer, is to write a program that computes the ecological footprint of source code.

The ecological footprint of a character is computed as follows (you can assume the source code is ASCII-encoded):

Write the character's ASCII code in binary, and count the number of 1's.

For example, A has a footprint of 2, but O is dirtier with a footprint of 5.

The global footprint of a program is the sum of the footprints of its characters.

Your program must accept a string as parameter, compute its ecological footprint, and output it.

There is a subtlety though. As you wish to enter a new, more restrictive market, you need to tune your program so that it behaves differently in "test mode". Thus:

The program should output 0 when it receives the string test as parameter.

Scoring

The source code with the smaller ecological footprint wins (and yes, the answer test is forbidden!)

Answer 7

Group Students Into Pairs

code-golf graphs

Synopsis: A graph theory matching problem. Given a list of which students like and dislike each other, pair the students up to maximise the overal happiness of the classroom.

Introduction

If you've ever been a teacher before, you've likely encountered the extremely frustrating experience that is getting students to do pair work. More often than not no one is happy with their partner, and the mood of the classroom suffers.

In this challenge, we're going to solve the enduring problem of pair work in classrooms. Here's how our system will work:

1. Each student shall write down what students they are happy to work with, and which ones they are not happy to work with.
2. We will take those lists, and generate student pairs such that the total happiness of the classroom is at its maximum.
3. The students are now (mostly) happy!

So how is the happiness of the classroom calculated? For each student in each pair of students:

• If a student's partner is in their "happy to work with" list, increase the happiness of the classroom by 1.
• If a student's partner is in their "not happy to work with" list, decrease the happiness of the classroom by 1.
• If a student is neutral towards their partner (not in either list), the happiness of the classroom does not change.

Here's a useful table that summarises the possible changes in the happiness with each pair of students:

+-------------------+-------------------+--------------------+
| Student 1 Feeling | Student 2 Feeling | Happiness Modifier |
+-------------------+-------------------+--------------------+
| Happy!            | Happy!            | +2                 |
| Happy!            | Neutral           | +1                 |
| Happy!            | Not happy...      | 0                  |
| Neutral           | Happy!            | +1                 |
| Neutral           | Neutral           | 0                  |
| Neutral           | Not happy...      | -1                 |
| Not happy...      | Happy!            | 0                  |
| Not happy...      | Neutral           | -1                 |
| Not happy...      | Not happy...      | -2                 |
+-------------------+-------------------+--------------------+

Input

First line of input is a positive integer n indicating the number of students to match up. n is always even. Following that are n lines, each line which has the format:

name likes dislikes

where name is the name of the student (which will only contain characters from [A-Za-z]), likes is a comma separated list of people he or she would be happy to work with, and dislikes is a comma separated list of people he or she would not be happy to work with. For instance:

Clarence Tiger,Anna,Jamal Amelia,James

This would indicate that Clarence is happy to work with Tiger, Anna, or Jamal; he is not happy to work with Amelia or James; and towards any other student he is neutral.

Another line:

Ilya Amelia,Clarence,Anna,Tiger,Jamal _

This would indicate that Ilya is happy to work with Amelia, Clarence, Anna, Tiger, and Jamal. For dislikes, we've used the special keyword _, which indicates that Ilya doesn't have anyone he is not happy to work with. Any remaining students Ilya would be neutral towards.

Output

Output space separated comma separated pairs of names, where each name corresponds to a pair of students. The pairs should be such that the happiness of the classroom is maximised. Every student should be in exactly one pair.

Example Inputs and Outputs

Writing reference implementation. This is one of those types of questions where you can't really judge the correct output for an input "by eye".

Sandbox Questions

1. This problem is quite difficult compared to typical code-golf fare, requiring two different algorithms to solve the weighted maximum matching problem. Is it too difficult for a code-golf? And if it is, what could make a better winning criterion?

Answer 8

Approximate phi using Fibonacci numbers

code-golffibonacci

As shown by Johannes Kepler, the quotient of successive Fibonacci numbers approaches phi.

(where F(n) = the nth Fibonacci number)

The fine folks at Wikipedia also say that if you choose two different starting values for the Fibonacci sequence, this expression still holds.

Last, but not least, if you use a later number in the series in the numerator, you get some interesting properties:

The challenge

• Create a full program or function that approximates phi using Fibonacci numbers.
• The program or function will take a single integer, n (unless a bonus is applied). It will output to STDOUT as follows, stopping when it reaches n:

1/1=1 2/1=2 3/2=1.5 5/3=1.66666666 ... F(n+1)/F(n)=...

• Fibonacci numbers must be calculated using iteration or recursion.
• No built-ins / standard loopholes, and neither the square root function nor phi should appear in the source code.
• It is OK if floating point limitation/integer overflow prevent accuracy beyond 4 or 5 digits, but you should use the most precise primitive data type (yes, double is one character longer than float).

There are two bonuses that you can earn, for a total of a 25% lower score:

• Input two additional integers as starting values for the Fibonacci sequence. This will still converge on phi, though it may take a bit longer. Reward: -10%.
• Input one additional integer for a in the above formula. This will result in the sequence converging to phi^a. Reward: -15%.

Scoring

Total score is the size of the program, in bytes, minus any bonuses. Since this is code-golf, lowest score wins.

(Insert leaderboard snippet) (Insert example snippet)

Example implementation snippet:

document.getElementById("button").addEventListener("click", process, false);

function process() {
  //Store field values to vars
  var itrNum = parseInt(document.getElementById("itrNum").value);
  var prevNum = parseInt(document.getElementById("start1").value);
  var curNum = parseInt(document.getElementById("start2").value);
  var aNum = parseInt(document.getElementById("aVal").value);
  document.write("(Click \"Run\" to reset)<br><br>");

  //Iterate through each fibbonacci number
  for (var i = 0; i < itrNum; i++) {

    dispNum = getFutureItr(prevNum, curNum, aNum);
    document.write(dispNum + " / " + prevNum + " = " + dispNum / prevNum + "<br>");
    //prepare numbers for next iteration
    var tempNum = curNum + prevNum;
    prevNum = curNum;
    curNum = tempNum;
  }
}

//Helper function for F(n+a)
function getFutureItr(prevNum,
  curNum,
  aNum) {
  var tempNum = curNum;
  for (var i = 1; i < aNum; i++) {
    tempNum = curNum + prevNum;
    prevNum = curNum;
    curNum = tempNum;
  }
  return curNum;
}

<!DOCTYPE html>
<html>

<body>
  Iteration number:
  <input type="number" min=0 id="itrNum" value=20>
  <hr>Starting value 1:
  <input type="number" min=1 id="start1" value=1>
  <br>
  <br>Starting value 2:
  <input type="number" min=1 id="start2" value=1>
  <hr>Value of a:
  <input type="number" min=1 id="aVal" value=1>
  <hr>
  <button id="button">Calculate</button>
</body>

</html>

Answer 9

Counting the Pattern Unlocks

Meta

Upon thinking about this challenge harder, I've realized that it is fairly trivial. Unless I am really bad at counting (which I am liable to be), there are at least 2 ways and at most 4 ways to draw any given pattern.

I think that this makes the challenge considerably less attractive. For this reason, I am thinking of ways to spice it up. For this, I would like your feedback. Currently I am thinking of:

-->Changing the rules so that dots can be used multiple times.

Let me know what you think of this change to the challenge, or suggest other changes.

The Premise

Many modern smartphones have options that allow you to choose how you would like to unlock your phone. For example, my phone allows

1. PIN input: a 4 digit number (low security)
2. Pattern Unlock: connect the dots in a pattern (medium security)
3. Password entry: enter a password (high security)
4. Fingerprint.

When you elect this second option, you are shown a 3x3 grid of dots (9 dots total) that looks something like this

.    .    .

.    .    .

.    .    .

Instead of using dots, we will use numbers in the following fashion for ease of reference.

1    2    3

4    5    6

7    8    9

You are then prompted to connect dots to form a pattern. This process is subject to the following rules:

1. The pattern must use at least 3 dots.
2. The pattern must be one continuous connection, that is once you lift your finger, the pattern ends.
3. Each dot may be used at most once (there is a quasi exception to this in rule 4)
4. If you take three collinear dots, in connecting the outer two dots, you must connect the inner dot if it is not already used. For example, if you make the connection 1-3, if 2 is not already used, you are really making the connection 1-2-3. If 2 is already used, then you are just making the connection 1-3. This is where the quasi exception to rule 3 comes in. You are passing over 2 again, even though you have already used it.

I believe that these are all the rules. Note that some phones may use different rules, but if you think I am missing something important, please let me know.

The Task

Our goal is to count how many ways there are to draw a given pattern.

For example if you see the following pattern:

1----2----3

4    5    6

7    8    8

It could have been drawn in one of four ways:

1 --> 2 --> 3    or
3 --> 2 --> 1    or
2 --> 3 --> 1    or
2 --> 1 --> 3

Input

You will be given a series of integers between 1 and 9 to stdin. They will represent connected dots on a grid.

The above example could be input via any of the following sequences:

1 2 3    or
3 2 1    or
2 3 1    or
2 1 3    or
1 3      or
3 1

If input is invalid, your program may do whatever it wants.

Output

Your program is to output the number of ways there are to draw the pattern, as an ingeter, to stdout or equivalent. In the above example, the output would be

4

Wining Criterion

This is code golf, shortest code (bytes) wins.

Bonus

Take off 20% if your answer also outputs all ways to draw the pattern (any understandable syntax acceptable).

TEST CASES

(1) grid layout

1    2    3
        /
4    5    6
|  /
7    8    9

possible inputs:

input>> 4 7 3
     >> 4 7 5 3
     >> 3 7 4
     >> 3 5 7 4
     >> 5 3 7 4
output<< 3

the ways are (for the bonus):

4 --> 7 --> 5 --> 3    or
3 --> 5 --> 7 --> 4    or
5 --> 3 --> 7 --> 4

(2)

1----2----3
|
4    5----6
|         |
7----8----9

input>> 3 2 1 4 7 8 9 6 5    or
     >> 3 1 7 9 6 5          or
     >> 5 6 9 7 1 3          or
     a couple others
output<< 3

example directions:

 3 --> 1 --> 7 --> 9 --> 6 --> 5   or
 5 --> 6 --> 9 --> 7 --> 1 --> 3   or
 2 --> 3 --> 1 --> 7 --> 9 --> 6 --> 5
 (or could include extra collinear points)

code-golf

Answer 10

Who is the Star Abuser?

In The Nineteenth Byte some people often star chat messages without any reason. You decided to go on a quest to find out who is the star abuser.

You logged the chat actions as a string, each action represented by a character (as you are a code golfer after all).

• Every user is marked with a letter of the alphabet.
• An uppercase version marks the user entering chat and a lowercase one marks his/her leaving the chat.
• At the start there is no one at the chat room.
• A star marks a starring. We assume that each person in the chat could have starred with the same probability when a starring happened. (E.g. if there are 2 users in the chat we assume both of them had 50% chance to star.)

An example log:

MOA***a**oS**s*Cc

You should output one uppercase letter showing the letter of the user who has the highest number of expected starring. If there are multiple users, output exactly one of them.

Input:

TODO

Output:

TODO

Examples:

TODO

This is code golf so the shortest entry wins.

Answer 11

Comedy of exceptions

Your goal is to demonstrate the shortest program or function that can throw 10 different types of errors/exceptions (I use the two interchangeably here) at runtime.

This question is only open to languages which have an object-oriented type system for errors. Furthermore, in the case of each error, a message including a clear identification of the exception's type must be printed. Evidently, it must also have at least 10 error types. Other systems such as an integer error code identifying the error, or all errors represented by strings are not acceptable.

Input is an integer from 0 to 9 inclusive. The program should reliably throw a different type of error for each input.

Methods which allow exceptions of arbitrary type to be thrown may not be used. E.g, throw ... .

Determining whether two errors are of different type (TODO: fill in detail of output)

Java: x and y print different stack traces, but are the same type, so they can't be used.

Python: UnboundLocalError ..... and NameError ....... would count as two types of error, since, although UnboundLocalError is a subclass of NameError, type() would give different results for the two.

C++: stoi("aaaa") printing ......... would be valid since the message gives std::invalid_argument. Integer division by zero would not since it crashes the program without a message informing of the error type

Sandbox

Please comment if you are aware of a language that is borderline on eligibility, blurs boundaries between error types, or has other loopholes.

Answer 12

Juggling without collisions code-golf

Determine if a siteswap juggling pattern is valid, meaning that no two balls land on the same beat. Fewest bytes wins.

Input: A non-empty list of positive integers.

Output: A consistent Truthy value for valid or Falsey value for invalid.

---

Siteswap is a notation for juggling patterns. Dividing time into units called beats, a siteswap pattern says how high to throw the ball each beat, measured in beats that it's airborne until you catch it. For example, the pattern

4 2 3

says

• On the first beat t=1, throw the ball 4 beats high, so you catch it at t=5.
• On the second beat t=2, throw the ball 2 beats high, so you catch it at t=4.
• On the third beat t=3, throw the ball 3 beats high, so you catch it at t=6.

If we treat this pattern as a periodic sequence

... 4 2 3 4 2 3 4 2 3 4 2 3 4 2 3 4 2 3 ...

note that on every beat, you catch exactly one ball. But, in

 5 1 3 4 2 ...

the ball thrown for 5 beats at t=1 and the ball thrown for 3 beats at t=3 both come down at t=6, which we don't want (let's ignore that we have two hands). This happens whenever two numbers in the sequence have the same different as the number of beats between them, with the bigger on first. Note that this may happen across repetitions, like in 8 1 2, where the marked balls collide at *.

 v             v *
 8 1 2 8 1 2 8 1 2 8 1 2 ...

---

TODO: Test cases.

Sandbox: Does the explanation make sense? Is it too long for the challenge?

Answer 13

Elements with 100 ≤ Z < 1000

---

The International Union of Pure and Applied Chemistry (IUPAC) decided that it is necessary to have a systematic naming for the elements, even for those which had not been discovered. The rules for naming are:

1. The name is derived directly from the atomic number of the element using the following Latin numerical roots:

   Number     Root
   ------     ----
   0          nil
   1          un
   2          bi
   3          tri
   4          quad
   5          pent
   6          hex
   7          sept
   8          oct
   9          enn
   

2. The roots are put together in the order of the digits which make up the atomic number and terminated by 'ium' to spell out the name. The final 'n' of 'enn' is omitted when it occurs before 'nil', and the final 'i' of 'bi' and of 'tri' when it occurs before 'ium'.

3. The symbol of the element is composed of the initial letters of the numerical roots which make up the name.

For this challenge, let us consider the elements having a three digit atomic number.

Examples:

100 --> Unnilnilium
101 --> Unnilunium
111 --> Unununium
150 --> Unpentnilium
200 --> Binilnilium
500 --> Pentnilnilium
999 --> Ennennennium

Input

• Input can be taken from one of the following

  • stdin
  • Command-line arguments
  • Function arguments (One argument, as a string)

• Input will contain either a valid IUPAC name of an element, or a valid IUPAC symbol of an element.

Output

• Output the corresponding
  • IUPAC name if the input is a symbol of an element.
  • symbol if the input is an IUPAC name of an element.

Rules

• The input will contain a valid IUPAC name/symbol.
• The first character of the symbol/name in input will be in upper-case and should remain capitalized in the output.
• You are permitted to write a full program or a function.
• There should be no unnecessary characters except an optional trailing newline character.

Test Cases

Unu            --> Unnilunium
Eee            --> Ennennennium
Enn            --> Ennilnilium
Bnb            --> Binilbium
Ubt            --> Unbitrium
Qsn            --> Quadseptnilium

Septenntrium   --> Set
Hexunbium      --> Hub
Octennilium    --> Oen
Bibibium       --> Bbb
Ununennium     --> Uue
Triquadpentium --> Tqp

Scoring

This is code-golf, so the shortest submission (in bytes) wins.

---

Tags: code-golf chemistry

---

Sandbox: What do you guys think about this challenge? Anything to improve? Did I miss anything?

Answer 14

Rational Number to Repeating Numeral Conversion

code-golf math number-theory restricted-complexity

As I'm sure you know, the decimal expansion of every rational number is either terminating—consisting of a finite number of digits, or repeating—consisting of infinitely many digits, but ending with a finite pattern that repeats itself indefinitely: for example, the decimal expansion of the rational number 1/6 is 0.1666..., where the sixes repeat forever. One way to represent this decimal expansion finitely and unambiguously, is to write the repeating part, called the repetend, enclosed in parentheses: going back to the previous example, under this scheme the number 1/6 is written as 0.1(6). We call this representation a repeating decimal. Of course, none of this is specific to base 10. More generally, we call such a representation, in any base, a repeating numeral. Note that, for the sake of this challenge, we use the term "repeating numeral" (or simply, "numeral") to refer to any numeral written using this scheme, whether or not it actually has a repeating part.

Challenge

Write a program or a function taking a pair of integers, p and q, and returning a repeating numeral representing the rational number p/q. You may assume that p ≥ 0, and q > 0, so that p/q is never negative. The resulting numeral should be in base 10, unless you go for the relevant bonus below.

There is more than one possible numeral representing a given rational number. For example, the rational number 1/1 can be represented, among (infinitely many) other options, as 1, 1.0, 1.(0), 0.(9), and so on... For this challenge, however, we'd like the output to be unique. The following set of rules, which your program must follow, takes care of that:

• When the integer part of the numeral is zero, there should be a single 0 before the radix point. For example, given the input 1/2, the output should be 0.5, and not .5.

• The repetend, if exists, must begin after the radix point; that is, it shouldn't apply to the integer part. For example, given the input 10/9, the output should be 1.(1), and not (1).

• The output should be finite and minimal, under the above rules. This is the most significant rule controlling the output, so it's worth highlighting some of its consequences:

  • There should be no leading or trailing zeroes. For example, given the input 3/2, the output should be 1.5, and not 01.5 or 1.50.

  • If the fractional part is zero, it should be omitted. For example, given the input 1/1, the output should be 1, and not 1.0.

  • If the repetend is zero, it should be omitted. For example, given the input 1/2, the output should be 0.5, and not 0.5(0).

  • When the input admits a terminating numeral, there shouldn't be an unnecessary repetend. For example, given the input 1/1, the output should be 1, and not 0.(9).

  • The repetend, and the rest of the fractional part, should not be superfluous; there shouldn't be any repetition in the repetend itself, nor in the repetend and the rest of the fractional part. For example, given the input 1/99, the output should be 0.(01), and not 0.01(01), 0.(0101), or 0.0(10).

As usual, you may not use any built-in or library functions aimed specifically at this problem.

Input and Output

You may take the input through the command line, through STDIN, as function arguments, or using an equivalent method. You may use any convenient format for the input, but make sure to specify it in your post. You may assume that p and q are no greater than 10,000,000, to the extent that it helps you to avoid overflow.

You may write the output to STDOUT, return it as the function's result or through an output parameter, as a string, or use an equivalent method.

Score

This is code-golf. The shortest answer, in bytes, combined with the any of the bonuses, wins.

Bonuses

If, in addition to the requirements listed above, your program satisfies the requirements for any of the following bonuses, multiply your score by the specified amount.

×0.8 Bonus Support other bases
Your program should take a third parameter, b, which is an integer between 2 and 36, inclusive, and return the corresponding numeral in base b, instead of base 10. The letters of the alphabet, either in lowercase or uppercase, should be used as digits above 9. For example, given the input 1/2 and b=3, the output should be 0.(1). Note that base b applies only to the output—if your program takes its input in string form, it should interpret it in base 10.

×0.6 Bonus O(1) space complexity
Your program's space complexity should be O(1), where the unit of space is the amount of space required to hold the input. In other words, the amount of memory required by your program should, on a large scale, be proportional to the amount of memory required by the input. You may not use the fact that the input range is bounded when reasoning about your program's space complexity, other than to the extent of establishing the amount of space required by the input. If you go for this bonus, it is strongly advised that you include at least a brief explanation of your program, so that others can verify that it meets the criterion.

If your program does not print the output directly, but rather returns a string, you may ignore the space occupied by the string as long as your program only appends to the string, and doesn't modify or read from it otherwise. (Note that something like s=s+"0" is fine, even though it technically involves reading from the string.)

Test Cases

Each of the test cases below lists the input, p/q, on the first line, and the corresponding output on the second line. Some of the tests list a third parameter, b, which specifies a different base for the output. These tests are only applicable for the relevant bonus.

Short-Output Tests

Your program should solve each of the following tests in a matter of seconds.

0/1
0

123/123
1

12/3
4

1/2
0.5

1/3
0.(3)

7/6
1.1(6)

3/11
0.(27)

1234/9999
0.(1234)

7/12
0.58(3)

22/7
3.(142857)

123/456
0.269(736842105263157894)

7124771/4545450
1.56(745118)

1/68
0.01(4705882352941176)

678/2345
0.2(891257995735607675906183368869936034115138592750533049040511727078)

7683/238
32.2(815126050420168067226890756302521008403361344537)

123631/99999
1.(23632)

4576/2345
1.9(513859275053304904051172707889125799573560767590618336886993603411)

2239231/4950000
0.45236(98)

673/23430
0.0(2872385830132309005548442168160478019632949210413999146393512590695689)

8984/2318
3.(875754961173425366695427092320966350301984469370146678170836928386540120793787748058671268334771354616048317515099223468507333908541846419327006039689387402933563416738567730802415)

1/2 2
0.1

214/5467 13
0.(067ccb5145334200a07b6253394bc5ca12bc650017b87998acc2c516a7993810702ba1)

214 5467 11
0.0(481119a34a86245a0053a1022114643a64131367585a8095498942556925833303993816590371976aa2a6952238969a61490900a792044229187a18262724060a517a986785002750566607877532070733842a95a27a4476828a12971701a4740884573649355153)

330420/335923 36
0.(zero)

9322181/306936 28
12.ab(cd)

123/6573 29
0.(0flb8c3hblol)

123/6573 21
0.0(85669592cjj9ca173fij6g67hhg7g940b5efk6j2bb7276c1ch25ikf7dd070jf4h96hek41ji102h3ea6kb2ic5hc3089b19kjc8dfhaf9147c48kgg4k5ab463d1fd5k86eigacciai54ihj3k2e7aghdbcfeebfbi811b8ajdh521e4ed334d4bgk9f650e1i99dide8j83if205d77kdk15g3be360gj12jki3h6ae09i28f38hkcb9jb018c753a5bjgd8gc044g0fa9geh7j57f0ce624a882a2fg231h0i6da4379)

Long-Output Tests

The following tests produce significantly longer output. Instead of listing their full output, only the MD5 checksum of the output if given. The checksum is calculated without a trailing newline, and using lowercase letters for digits above 9 (in the relevant test cases). If you want to see the full output for these tests, or to calculate the checksum under different conditions, you can use the test snippet below. Your program should solve each of the following tests in no more than a few minutes.

343/677472
e1810c85500a97c36f2ba5dcc94a2aa6

234/62332
662adcee10cd77d001282f0e31a84b77

57628/7894211
81222aaa93f192c6d8334fcde6381a74

67332/1267232
3ea190c83a735a8bafc922cbb177e6f4

954/3684332
d4ef940c9986f9c2ac52ee822d94d6a7

783232/3462241
7724d3444b5540b8b4f07d13317e8da3

83/7657124
b295369267f48e642e202e0364898c82

764231/54646224
ecf7f3dd12f2d495b31a178fc03662d7

6743/1231234
9f447fd27447abb881795fc5e2f814e5

764/9343249
8381dc6f127be6d95cadc0b5bdd70104

345/2234448 22
667d437e35c3825696f64f1b27e6a827

63451/2343324 3
5d86d77856cc0a15ac8a51b46c2f22d6

93457/546464 2
1084e884aded53f0da933480c45db1b8

678541/453524 9
5bb54bddaab7bd933258d4d78a83cdba

4572/2341198 15
39af2bc67ab58438068f672ed3a8357d

1/4821466 6
57ba79a48c438b7fd21aa39ee3575c8d

145/5821417 21
009f087ae661cfd4690cc51ba71a827f

5472/2333645 33
d24583dfdad205de61763c6a87637979

Test Snippet

If you want to further test your submission, you can use the following test snippet to find the repeating numeral representation of arbitrary rational numbers, or to find the rational number corresponding to arbitrary repeating numerals. Note that the result can get very big, very fast, which can be a little much for your browser; in this case, you might want to uncheck the "Result" checkbox, and check the "MD5" checkbox, to only get the MD5 checksum of the output. Note also that you can resize the input and output boxes.

<style>* { font-family: sans-serif; }table { border-collapse: collapse; }table > tbody > tr > td { padding: 0px; }#status { display: none; }#status[loading] { display: initial; font-style: italic; }#main { display: none; width:100%; border-right:.7em solid transparent; font-size: 95%; }#main[loaded] { display: table; }#main > tbody > tr + tr > td { padding-top: .25em; }#main > tbody > tr > td + td { padding-left: .5em; }#main > tbody > tr > td:first-of-type { width: 4.25em; }.label { white-space: pre; }#flags { padding-left: 2.4em; font-size: smaller; }#flags > table > tbody > tr > td + td { padding-left: 1em; }#error { display: none; font-size: smaller; color: #880000; }#error[error] { display: initial; }#job_cancel, #job_throbber { display: none; vertical-align: bottom; }#job_cancel[working], #job_throbber[working] { display: initial; }#job_throbber > img { height: 1em; }#job_throbber[working] { padding-left: .3em; }#job_cancel[working] { padding-left: 1em; }#job_cancel > input { height: 1.8em; font-size: small; }input[type="text"], input[type="number"], textarea { padding: 0.25em; height: 1.4em; font-family: monospace; }textarea { width: 100%; }#base { width: 2.8em; text-align: right; }.output { background-color: #e4e4e4; border: none; }#length { width: 8em; text-align: right; }#md5 { width: 20em; text-align: center; }#result_container[active="false"] { display: none; }#md5_container[active="false"] { display: none; }</style></head><body><div id="status" loading>Loading...</div><table id="main" onkeydown="handle_key_down(event)"><tr><td id="input_label" class="label">Fraction:</td><td><textarea id="input" oninput="update(true)" spellcheck="false">123/456</textarea></td></tr><tr><td class="label">Base:</td><td><table><tr><td><input id="base" type="number" value="10" spellcheck="false" oninput="update(true)"></td><td id="flags"><table><tr><td><label><table><tr><td><input id="flag_result" type="checkbox" checked onchange="handle_flag('result')"></td><td>Result</td></tr></table></label></td><td><label><table><tr><td><input id="flag_md5" type="checkbox" onchange="handle_flag('md5')"></td><td>MD5</td></tr></table></label></td><td><label><table><tr><td><input id="flag_uppercase" type="checkbox" onchange="handle_flag('uppercase')"></td><td>Uppercase</td></tr></table></label></td><td><label><table><tr><td><input id="flag_trailing_newline" type="checkbox" onchange="handle_flag('trailing_newline')"></td><td>Trailing Newline</td></tr></table></label></td><td><label><table><tr><td><input id="flag_progressive_output" type="checkbox" onchange="handle_flag('progressive_output')"></td><td>Progressive Output</td></tr></table></label></td></tr></table></td></tr></table></td></tr><tr><td></td><td><span id="error"></span></td></tr><tr><td class="label">Length:</td><td><table id="length_table"><tr><td><input id="length" class="output" type="text" spellcheck="false" readonly></td><td id="job_throbber"><img src="https://i.stack.imgur.com/sHKZY.gif"></td><td id="job_cancel"><input type="button" value="Cancel" onclick="cancel_job()"><td></tr></table></td></tr><tr id="md5_container"><td class="label">MD5:</td><td><input id="md5" class="output" type="text" spellcheck="false" readonly></td></tr><tr id="result_container"><td id="result_label" class="label">Numeral:</td><td class="full_width"><textarea id="result" class="output" spellcheck="false" readonly></textarea></td></tr></table><script async type="text/javascript" src="https://gist.githack.com/anonymous/49705525fd01ba66c1ad/raw/c35226ad89444e3af07d0e505f7163df8574b860/repnum.js"></script>

Answer 15

This challenge was closed, because it was way too broad, but, in the comments, SuperJedi224 suggested a slightly different challenge that I thought was a really good idea, so I'm stealing it and posting it here.

---

Write a text editor in 2000 bytes or less

popularity-contest

Write a text editor in 2000 bytes or less. It should support loading and saving files (or something else if your language doesn't support that, maybe?), modifying text, and displaying the contents of a file that's currently open in some format.

Sandbox questions

• I'm not sure if 2000 bytes is the right number. SuperJedi224 originally suggested 10000, but that seems to me like too many.
• Should some features be required, or should it just be by votes? Will votes take care of possible submissions that aren't actually text editors?
• Should there be some kind of bonus for shorter submissions? Maybe an extra point for every 20 or so bytes you don't use? No, there probably shouldn't be.
• Should languages that don't support file operations be allowed?

Answer 16

Stitch a Picture

A few weeks ago, I asked Stitch a picture. Since then:

• The question has received several upvotes and no downvotes - hopefully an indication that the community thinks this is as interesting as I do
• No complete answers
• Several interesting comments - in particular this one from @bazzargh

In short it looks like this question is a lot harder than I though it would be. It turns out from @bazzargh's comment that I have stumbled into an area of current research, and that perfect solutions are not so easily attainable as I had assumed.

With that in mind, I think its time I took this back to the sandbox to make this into the decent question that I think the subject deserves - and I think I need some community help with that.

I am posting several possibilities I am considering as comments. Vote for these comments as you feel appropriate, and/or add your own suggestions.

---

I'm going to Yosemite this weekend (woohoo!) so will probably pick this up again next week.

Update

I have relinquished control of this question by putting it in Secret Santa's Sandbox.

Answer 17

Addition of doubles... without doubles fastest-code golf-cpu

For this challenge, you must write a GOLF assembly program that takes two IEEE 754 double-precision numbers and returns their sum.

The Format

IEEE 754 doubles use 8 bytes to store a floating-point value. The memory is laid out like this:

_(Wikipedia)

For the purposes of this challenge, all numbers will be in big-endian, and you won't have to worry about overflows or underflows. Addition works roughly like this (I won't go into all of the details):

1. Align the two numbers to a common exponent.
2. Add the fractional parts, taking into account the sign.
3. If the addition overflows, then change the exponent to match.

I/O

Your program will receive 16 bytes of input. The first 8 represent the (big-endian) first number, and the rest represent the second number. Your program will return 8 bytes representing the sum of the two.

Rules

• This is fastest-code, so the program that completes the task with the least cycles wins.
• The score of an answer is the mean number of cycles required for adding uniformly distributed numbers in [-10^64, 10^64].
• You must test with at least 2500 trials.
• Your code doesn't have to handle infinities/NaNs.
• Your GOLF binary (after assembling) must fit in 4096 bytes.

Meta Questions

• Do I have too many/too few trials?
• Is there something that I overlooked?
• Is there a more fitting title?
• How much explanation should I provide? I don't want this question to turn into a Wikipedia article, but questions requiring external resources are generally frowned upon.
• Is colf-cpu dead?

Answer 18

HTML Obfuscation

Write a program or function that takes HTML as a string as input and outputs "obfuscated" HTML. Leave the text between the <s and >s unchanged, but escape all other text.

• You can assume that the < and > characters will only be used to open/close HTML tags.
• You can safely leave any text between these characters alone. However, any text not between those characters should take on the form <ampersand><pound><ascii-encoding><semi-colon>.
• You do NOT have to support self closing tags.

Test cases:

Input:

<div>Hello World</div>

Output:

<div>&#72;&#101;&#108;&#108;&#111;&#32;&#87;&#111;&#114;&#108;&#100;</div>

Input:

ABC<input type="text">DEF<div>

Output:

&#65;&#66;&#67;<input type="text">&#68;&#69;&#70;<div>

Note: it's ok that the HTML is invalid

Input:

eee<div data-bracket=">">eee

Output:

&#101;&#101;&#101;<div data-bracket=">&#34;&#62;&#101;&#101;&#101;

Note: here your program would mess up the HTML. That's ok for the purposes of the challenge.

This is code golf, so the shortest program wins.

Answer 19

Play Flippy Bit

code-golf string pathfinding

There's a simple game called "Flippy Bit and the Attack of the Hexadecimals from Base 16", originally made as an April Fool's prank in 2014.

The premise is simple: Enemies enter the field from the top. Each one has a hexadecimal number, and are destroyed when the player's binary number matches. For example, an enemy with number 2Ah = 00101010b would be destroyed as soon as the user's number is 00101010. Of course, enemies can only be destroyed after they enter the screen.

The player manipulates their binary number by flipping individual bits with the qwertyui keys, where q is the most significant bit. Each press flips the bit at that location. Therefore, the 2A enemy above will explode if, starting from 0, the player presses etu in any order. When an enemy explodes, the player's number is reset to 0.

Challenge

Given a list of enemies, determine a sequence of keypresses that can destroy all enemies in the order given. This isn't as simple as it seems: if you're trying to destroy 3 but there's another enemy called 2 on the board, you'll need to press i before u. Your algorithm must terminate within a bounded time.

Input

A list of strings of hex digits 0123456789ABCDEF, with each string 1 or 2 digits long, and where the 2-digit strings have no leading zero. You may also take the input in a reasonable format other than a list; for example, newline-separated. The input will always represent a solvable configuration.

Output

A string representing the sequence of keypresses.

Test cases

Note that there are multiple possible outputs for most inputs.

2A 01 02 04 08 10 20 40 A0 88
quetqwertyui

[add more test cases]

Verify your solutions with the following Python:

[add verification code]

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

Answer 20

Radiation-Protected Expressions

code-challenge

Challenge

Write a program, taking an integer n as input from -999,999 to 999,999 inclusive, that returns a string representing a valid expression evaluating to that number in your language. The catch: this expression must NOT evaluate to any other number when evaluated if any single character is removed from it.

Restrictions

Your program must be <= 1024 bytes in length.

The outputted expressions must be in the same language as the generating program.

Scoring

Your score is the number of bytes in the largest string generated by your program for the entire range of valid numbers. Tiebreakers go to shortest code.

Examples of Valid Outputs (in JavaScript)

• Math.PI|0||3 for n=3, because:

  • ath.PI|0||3, Mth.PI|0||3, Mah.PI|0||3, and Mat.PI|0||3 cause ReferenceErrors,

  • MathPI|0||3 causes a ReferenceError,

  • Math.P|0||3, Math.I|0||3, and Math.PI0||3 result in 3,

  • Math.PI|||3 causes a SyntaxError,

  • Math.PI|0|3 results in 3, and

  • Math.PI|0|| causes a SyntaxError.

• 9*(8) is valid for n=72

• (n=9e5)>96?n:9e5 for n=900,000

• 1 for n=1

  ---

Examples of Invalid Outputs (in JavaScript)

• 1e2 for n=100 because 12 is a valid expression that evaluates to a number other than 100.

Answer 21

Output the points of this twisting fractal

Challenge

Output the points (in order) for the following fractal of size n:

(The above example is for n = 4)

We begin with the Binary Sierpinski Triangle, which can be generated recursively, by a number of cellular automata (including Rule 90), and by Pascal's Triangle.

As a refresher, Pascal's triangle is:

   |  0 |  1 |  2 |  3 |  4 |  5 |  6 |  7| 
---+----+----+----+----+----+----+----+---+
 0 |  1 |  0 |  0 |  0 |  0 |  0 |  0 |  0|
 1 |  1 |  1 |  0 |  0 |  0 |  0 |  0 |  0| 
 2 |  1 |  2 |  1 |  0 |  0 |  0 |  0 |  0|
 3 |  1 |  3 |  3 |  1 |  0 |  0 |  0 |  0|
 4 |  1 |  4 |  6 |  4 |  1 |  0 |  0 |  0|
 5 |  1 |  5 | 10 | 10 |  5 |  1 |  0 |  0|
 6 |  1 |  6 | 15 | 20 | 15 |  6 |  1 |  0|
 7 |  1 |  7 | 21 | 35 | 35 | 21 |  7 |  1|

Here rows are i, columns are j, and the values are i choose j.

Using Pascal's triangle, we replace each value with its remainder mod 2 to get:

   |  0 |  1 |  2 |  3 |  4 |  5 |  6 |  7| 
---+----+----+----+----+----+----+----+---+
 0 |  1 |  0 |  0 |  0 |  0 |  0 |  0 |  0|     O        
 1 |  1 |  1 |  0 |  0 |  0 |  0 |  0 |  0|     OO       
 2 |  1 |  0 |  1 |  0 |  0 |  0 |  0 |  0|     O O      
 3 |  1 |  1 |  1 |  1 |  0 |  0 |  0 |  0|     OOOO     
 4 |  1 |  0 |  0 |  0 |  1 |  0 |  0 |  0|     O   O    
 5 |  1 |  1 |  0 |  0 |  1 |  1 |  0 |  0|     OO  OO   
 6 |  1 |  0 |  1 |  0 |  1 |  0 |  1 |  0|     O O O O  
 7 |  1 |  1 |  1 |  1 |  1 |  1 |  1 |  1|     OOOOOOOO 

With the result "plotted" to the right, the n = 1 iteration of the Sierpinski Triangle.

Now, to keep the "centers" well defined, we take the center of each triangle to be its NE corner like so:

'              ^
''             |
'*'            N 
''''       <--E W-->
'  *'          S
''  ''         |
'*' '*'        v
''''''''  

Here is pseudocode to generate the fractal:

fractal(n):
    position = nth center
    while SE possible:
        go SE
        mark position
    while not all full:
        if current level not full:
            rotate counterclockwise on current level
            mark position
        else:
            go NW until reach non-full level
            rotate counterclockwise on current level
            while SE possible:
                mark position
                go SE
    return marked positions

Here's what that looks like for n = 2:

 '                              
 ' '                            
 ' 12'                          
 ' ' ' '                        
 '      9'                      
 ' '     ' '                    
 ' 10'   ' 11'                  
 ' ' ' ' ' ' ' '                
 '               '              
 ' '             ' '            
 '  4'           '  8'          
 ' ' ' '         ' ' ' '        
 '      1'       '      5'      
 ' '     ' '     ' '     ' '    
 '  2'   '  3'   '  6'   '  7'  
 ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' '

Giving the following points marked (in order):

[[3, 12], [1, 14], [5, 14], [1, 10], [11, 12], [9, 14], [13, 14], [9, 10], [3, 4], [1, 6], [5,6], [1,2]] 

Rules

• Entry may be either a function or full program.
• Input is a non-negative integer.
• Output is the (properly ordered) list of points for the fractal above.
• You may use something other than a list to output the results if it allows the easy reading of the points, in order. For example, newline separated is fine.
• Output must contain exactly (3^n - 3)/2 points.
• This is code golf so shortest wins!

Questions

• Is everything well defined?
• Should I reformat the ASCII triangles? Or even replace everything with images?

Test cases if anyone is interested or I post this.

This is a challenge that I enjoyed solving so I hope I can smooth out the corners relatively quickly.

code-golf fractal sequence

Answer 22

Replace magic numbers

Tags: code-gold string

Introduction

Magic numbers are a common problem in software development, since they tend to make software hard to maintain. Best practise is to use named constants instead of raw numbers in the source code. In this challenge you have to clean up some code that makes extensive use of magic numbers.

The Challenge

Given a piece of code, replace every number that is not 0, 1 or 2 with named constants. If you encounter a number that you already created a constant for, use the existing constant instead of adding another one. The replacement is done by replacing the number with an uppercase letter [A-Z] and prepending an assignment in the form of A=5 to the initial input.

Example

x=input()
if x == 2:
    print 42
elif x == 1337:
    print 666
print 42

becomes

C=666
B=1337
A=42
x=input()
if x == 2:
    print A
elif x == B:
    print C
print A

Notes

• The order of the assinments that get prepended to the input does not matter.
• The order of replacements does not matter as well. You don't have to replace the first magic number with an A for example.
• You may take the input as a list of strings instead of a multiline string.
• You will never have to use more than 26 constants.
• A number that has to be replaced matches the regex [0-9]{2,}|[3-9].

Rules

• Function or full program allowed.
• Default rules for input/output.
• Standard loopholes apply.
• This is code-golf, so lowest byte-count wins. Tiebreaker is earlier submission.

Happy Coding!

Answer 23

Word Squares

Create a function or program that given a list of words and size n as arguments or standard input, outputs a word square with dimensions n by n. The output can be either formatted in a similar shape to a word square, or as a list of the words used in order by rows from the top and then by columns from the right.

Explanation

Word squares are a grid of letters that form words when read horizontally and vertically. The size of the square refers to the number of letters in each word.

Example

This is a size 5 word square. The words formed by each row are heart, ember, abuse, resin, and trend. In this example, the same words are formed by each column, but this is not a necessary condition.

H E A R T
E M B E R
A B U S E
R E S I N
T R E N D

Another example is this word square with size 4. The words formed by each row in this case are different from the words formed by each column.

L A C K
I R O N
M E R E
B A K E

Rules

• This is code-golf so the shortest solution wins.
• Builtins that solve this and the standard loopholes are not allowed.
• The words must be from this dictionary. You can take the filename of the dictionary or the contents as input or as an argument. (Recommend a dictionary here that consists of only English alphabet letters, in all lowercase or all uppercase.)
• If no such word square can be found using the given dictionary, no output or a false (or falsey) value can be returned.

Test Case

n = 4, dictionary = ...
L A C K
I R O N
M E R E
B A K E
-- or --
LACK
IRON
MERE
BAKE
-- or --
["lack", "iron", "mere", "bake", "limb", "area", "cork", "knee"]
-- or --
[["lack", "iron", "mere", "bake"], ["limb", "area", "cork", "knee"]]
-- or --
Similar to the above but with swapped cases.
The case is not important as long as it remains consistent.

Answer 24

Draw the Cool S code-golf ascii-art

Given a number n≥3, print or output the Cool S made with n vertical bars. The outputs for 3,4,5,6 are:

  / \
 /   \
|  |  |
|  |  |
 \  \/
 /\  \
|  |  |
|  |  |
 \   /
  \ /

    /\
   /  \
  /    \
 /  /\  \
|  |  |  |
|  |  |  |
|  |  |  |
 \  \  \/
 /\  \  \
|  |  |  |
|  |  |  |
|  |  |  |
 \  \/  /
  \    /
   \  /
    \/

     / \
    /   \
   /     \
  /  / \  \
 /  /   \  \
|  |  |  |  |
|  |  |  |  |
|  |  |  |  |
|  |  |  |  |
 \  \  \  \/
 /\  \  \  \
|  |  |  |  |
|  |  |  |  |
|  |  |  |  |
|  |  |  |  |
 \  \   /  /
  \  \ /  /
   \     /
    \   /
     \ /

       /\
      /  \
     /    \
    /  /\  \
   /  /  \  \
  /  /    \  \
 /  /  /\  \  \
|  |  |  |  |  |
|  |  |  |  |  |
|  |  |  |  |  |
|  |  |  |  |  |
|  |  |  |  |  |
 \  \  \  \  \/
 /\  \  \  \  \
|  |  |  |  |  |
|  |  |  |  |  |
|  |  |  |  |  |
|  |  |  |  |  |
|  |  |  |  |  |
 \  \  \/  /  /
  \  \    /  /
   \  \  /  /
    \  \/  /
     \    /
      \  /
       \/

Any invisible whitespace is optional (trailing spaces and trailing/leading newlines).

How to draw the Cool S

Draw the Cool S just like you've done since childhood, except the number of vertical bars can be more than 3.

• Draw two rows of vertical bars.
• Connect them with slanted lines, tucking away the two remaining bars.
• Pair of the bars with slanted lines at the top and bottom.

Here's how we do this for ASCII art. Let's look at n=5.

A row has n vertical bars with two spaces between them

|  |  |  |  |

Draw two groups of n-1 rows, leaving two empty lines between them

|  |  |  |  |
|  |  |  |  |
|  |  |  |  |
|  |  |  |  |
 

|  |  |  |  |
|  |  |  |  |
|  |  |  |  |
|  |  |  |  |

Connect each top bar to the bottom bar one position right with a slanted line of two \, then close off the two unused bars with a /.

|  |  |  |  |
|  |  |  |  |
|  |  |  |  |
|  |  |  |  |
 \  \  \  \/
 /\  \  \  \
|  |  |  |  |
|  |  |  |  |
|  |  |  |  |
|  |  |  |  |

Complete the S on the top and bottom by drawing lines sloping inwards that meet at the center. When n is odd, a gap of one space is left and the center bar isn't used.

     / \
    /   \
   /     \
  /  / \  \
 /  /   \  \
|  |  |  |  |
|  |  |  |  |
|  |  |  |  |
|  |  |  |  |
 \  \  \  \/
 /\  \  \  \
|  |  |  |  |
|  |  |  |  |
|  |  |  |  |
|  |  |  |  |
 \  \   /  /
  \  \ /  /
   \     /
    \   /
     \ /

---

Spun off from this Sandboxed challenge by Beta Decay.

Answer 25

Strip Iterated Prisoner's Dilemma

koth

Inspired by https://xkcd.com/696/, of course.

The Prisoner's Dilemma is a classic game (more in the game theory sense than the family fun sense) where two agents - two accomplices to a crime, in the original formulation - must choose whether to sell out the other.

If each player chooses not to betray the other, both win. If one player chooses treachery and the other does not, it wins, but if both betray each other, neither wins. The "iterated" variation is where the game is played multiple times with the same players, and both players know all the decisions each player has made in the past.

Of course, that's all a bit dull, and has been done before besides. We're going to tart it up a bit.

(Unfortunately due to the nature of the test all solutions must be in the same language, and one that supports executing strings. I've chosen Python 3, since it's my favorite and I have to write the runner.)

The Game:

Submit a program - specifically a Python 3 function - that plays Iterated Prisoner's Dilemma against another such program. If both functions betray each other, each one gets one character deleted from the end of its source code. If one function betrays the other, the betrayed function gets two characters deleted from the end of it, and the traitor gets a # appended to it, immunizing it against one future loss. If neither turns traitor, both go unharmed. Functions will be restored to their original text between each contest with a new opponent.

Submissions are scored based on failure rate and length; specifically, score = round( (number_of_trials_failed / total_number_of_trials) * ( length / 2 ) ). The submission with the lowest score wins.

The length of a submission is the number of non-whitespace characters in the submission. Comments are not counted, but are also removed before the contest begins, so a commented out "guard" at the end will not protect your code from deletions. Length also does not count the function specifier (the def submission(y, o, t): which should not be included in your submission text anyway.)

Your function will be called with three parameters, y (your history), o(opponent's history), and t (text of the opponent itself). t is the very same text that the game runner will execute as your function's opponent, which you may analyze or otherwise use to run simulations. It will then return True if it wishes to betray its opponent or False if it does not.

Every possible 2-combination of submissions will be contested against each other - including each submission against itself. Each contest consists of 2,500 trials.

Other Rules:

• All submissions must be in Python 3. (Specifically, they should run under Python 3.4.4)

• The submission text must be the only code that is run to produce the result; you may not import any libraries, ask for user input, read from /dev/urandom/or equivalent, and of course you can't pull results from some webserver (which is already a violation of the standard loophole rules.) You MAY execute the given opponent text, and of course you're allowed to call all the builtins.

• The submission must terminate and return an answer within 1 second (this will be run on a 12GB i7 gaming computer, so this should be plenty of time).

• A submission that emits an uncaught exception or returns an invalid value loses that round.

• Submissions that do not return in one second or less are immediately disqualified.

• Submissions will be closed on [date posted + 8 days] and programmatically judged, results will be appended to the challenge. There will be a "trial run" in the evening of [date posted + 4 days].

API:

The "submission text" is valid, 4-space-indented Python 3 source code that will have the function specifier line def submission(y, o, t):\n appended to the beginning and a single 4-space-indent added to the beginning of each line. So:

if len(y) == 0: return False
else: return (not y[-1])

...is run as...

def submission(y, o, t):
   if len(y) == 0: return False
   else: return (not y[-1])

The function should return True to betray its opponent or False to trust its opponent. Returning any other value (such as if your return statement has been deleted and you return None`) is an error and will result in an automatic loss of that round.

o is a list of True-es or False-es, representing the opponent's previous moves when playing against you; o[n] equals the decision your opponent made in round n, and of course this list will be empty in the first trial. y is similar except it's your previous moves. t is the text of the opponent submission, formatted as specified above.

This is the program that will perform the contest:

[said code here]

Example Submissions: These will also be included in the actual contest.

Chronic Villain Syndrome:

#always choose 'betray'
return True
11111111 #padding

The Patsy:

#always choose 'trust'
return False
11111111 #padding

Do Onto Others...:

#always choose what opponent chose last round
if o:
   return o[-1]
return True

Professor X:

me="""
#Read opponent's mind and choose optimally.
exec("def e(y, o, t):\n"+t)
return False e(o, y, me)
#Opponent's choice this turn if we betray...
tb = e(o,y+[True], me)
#if we trust...
tt = e(o,y+[False], me)

#Opponents choice NEXT turn if we betray then betray...
tbb = e(o+[tb], y+[True], me)
#... betray then trust...
tbt = e(o+[tb], y+[False], me)
#... trust then betray...
ttb = e(o+[tt], y+[True], me)
#... trust then trust...
ttt = e(o+[tt], y+[False], me)

#Maps (your_choice,opponent_choice) to desirability
#Betrayed = -2, mutual betrayal = -1,
#mutual cooperation = 1, betray opp. = 2
v = {(False, True): -2, (True, True): -1,
     (False, False): 1, (True, False): 2}
#Best outcome next turn of trusting now
ftv = max(v[ttt], v[ttb])
#... of betraying now
fbv = max(v[tbt], v[tbb])
#value of betraying now
bv = v[tb] + fbv
#... of trusting now
tb = b[tt] + ftv

#Tuple comparison is done l to r, so
#this returns True if tv >= bv,
#False if bv > tv.
return max( (bv, True), (tv, False) )
"""
exec(me)

(p.s. this one gets disqualified every time - why is left as an exercise to the reader)

Answer 26

Simultaneous variable updates

Suppose we have the following code snippet:

a = 2*b + c
b = a - b + c
c = a + 3*c

In most programming languages, the above three lines would execute one after the other. This means that the a on the second and third lines would refer to the updated value of a, rather than the value of a before this code block ran.

If we wanted to see how a, b, c actually changes as the result of running the above three lines, we'd have to substitute earlier variable updates into later expressions, like so:

a = 2*b + c
b = a - b + c = (2*b + c) - b + c = b + 2*c
c = a + 3*c   = (2*b + c) + 3*c   = 2*b + 4*c

Hence, the first code block is equivalent to the following in languages like Python, which support simultaneous variable updates:

a, b, c = 2*b + c, b + 2*c, 2*b + 4*c

We can rewrite the original code block and the updated code block in matrix form, like so:

[ 0  2  1 ]        [ 0  2  1 ]
[ 1 -1  1 ]   ->   [ 0  1  2 ]
[ 1  0  3 ]        [ 0  2  4 ]

For example, the second rows of the input/output matrices above refer to b = a - b + c and b = b + 2*c respectively. Expressing the update step in the latter, simultaneous form is useful since we can perform multiple updates very easily, using matrix exponentiation (which we will not do in this challenge).

Here's one more example, for clarity:

                                              Input matrix:
a = a - b + d                                 [  1 -1  0  1 ]
b = 2*b + c                                   [  0  2  1  0 ]
c = -2a - b + d                               [ -2 -1  0  1 ]
d = b + c                                     [  0  1  1  0 ]

                                              Output matrix:
a = a - b + d                                 [  1 -1  0  1 ]
b = 2*b + c                                   [  0  2  1  0 ]
c = -2*(a-b+d)-(2*b+c)+d = -2*a - c - d       [ -2  0 -1 -1 ]
d = (2*b+c)+(-2*a-c-d) = -2*a + 2*b - d       [ -2  2  0 -1 ]

The task

Given a square input matrix representing a sequence of variable updates one after the other, output the corresponding matrix which represents the variable updates being applied simultaneously.

You may write either a function or a full program. The exact input/output format is flexible, as long as rows are separated from other rows and individual matrix entries are distinguishable. You may assume that entries in the input/output are integers in the range [-127, 127], and that the matrix will be at least 2x2.

This is code-golf, so the goal is to reduce the number of bytes in your program as much as possible.

Test cases

TODO. Will contain:

• Several simple 2x2 examples
• The above examples, plus a few more 3x3 or 4x4s
• An example with input rows all zero
• An example with input columns all zero
• Large examples: dense 10x10, sparse 10x10

---

Questions for the sandbox

• Any potential of being a dupe?
• Any interesting test cases?

Answer 27

Capture the Flag

^{Do you ever wonder why we're here?}

Objective

Capture the enemy team's flag and return it to your base. The first team to 3 captures wins the round. The player with the most wins across all (number TBD) rounds wins the game.

Teams

There will be two teams each round. Teams will be randomly, evenly assigned to all submissions at the start of each round.

Playing

The game will be turn-based. At the start of each turn, each player will be given the current map. All players will move simultaneously. Players shall submit their move as a one or two character ASCII string, composed from the following options:

• First character: wait, move, stab (if not holding flag), drop (if holding flag), or pick-up (if standing on a flag)
• Second character: north, east, south, or west, or nothing if waiting, dropping, or picking-up

Moving a direction will result in the player moving one square in that direction if possible, otherwise standing still (for example, if the player is attempting to move into a wall, or into an occupied square). Stabbing in a direction will result in killing the player standing in the adjacent square in that direction, unless the player is a teammate (no teamkilling). Stabs are processed before moves each turn. Dropping the flag results in it being placed on the ground beneath the player. Drop, pick-up, and wait commands ignore the second character. Invalid commands are interpreted as waiting. Case is ignored, so W and w are the same command. Either team may pick up either flag.

If two or more players attempt to move onto the same square, one of the players will be randomly selected to successfully move, and the rest will not move.

If a player is killed, they will drop the flag they are holding (if they are holding one), and will respawn in 3 turns in an unoccupied square in their home base. If there is no unoccupied square in their home base, they will respawn in the nearest square to the base. Respawns happen after stabs, but before moves.

Inside each base, there will be a 5x5 square room, with doorways in the middle of each wall, and the team's flag in the center of the room. Players who spend 5 consecutive turns inside their team's flag room (this includes the 4 doorways), while no enemies are present in the flag room and they are not holding a flag, will be killed at the conclusion of the 5th turn, to discourage camping. Successfully placing the enemy's flag on top of your flag's stand (in the center of the room), either by dropping it or being killed on top of the flag stand, will result in a point being scored for your team and the enemy's flag immediately returning to their flag stand.

The Map

(work in progress)

The world map will be a single level (no upstairs or downstairs), represented as such:

# : wall, cannot be moved into
. : an empty space
F : the enemy team's flag
f : your flag
! : a flag stand (with no flag on it)
@ : you
$ : you, carrying the enemy flag
% : you, carrying your flag
p : one of your teammates
P : an enemy player
c : a teammate, carrying or standing on top of the enemy flag
C : an enemy player, carrying or standing on top of your flag
s : a teammate, carrying or standing on top of your flag
S : an enemy player, carrying or standing on top of the enemy flag

Here is an example map (the actual maps used in the tournament will be posted later):

####################################################
#..................................................#
#..###.###########.######........###......##########
#..#....................#..........................#
#..#.....###.###...................#######.........#
#..#.....#.....#........#..........................#
#..#.....#.....#........#...................#...#..#
#..#........f...........#..........................#
#........#.....#........#....#########.............#
#..#.....#.....#........#..........................#
#..#.....###.###........#......##################..#
#..#...............................................#
#..#.#################.............................#
#.........................###########.........###..#
#..................................................#
####################################...............#
####################################...............#
#..................................................#
#..................................................#
#...............####################################
#...............####################################
#..................................................#
#..###.........###########.........................#
#.............................#################.#..#
#...............................................#..#
#..##################......#........###.###.....#..#
#..........................#........#.....#.....#..#
#.............#########....#........#.....#........#
#..........................#...........F........#..#
#..#...#...................#........#.....#.....#..#
#..........................#........#.....#.....#..#
#.........#######...................###.###.....#..#
#..........................#....................#..#
##########......###........######.###########.###..#
#..................................................#
####################################################

Controller

The controller and an example map and player are located on the challenge's GitHub project. Once I finish the controller, I'll copy the program here.

Restrictions

• Bots must be fully deterministic. RNGs may not be used.
• Bots may be written in any language, so long as they support reading ASCII input from STDIN and writing ASCII output to STDOUT. Anything that is written to STDERR will be ignored.
• Bots' processes will be started at the beginning of each turn, and must output their command and terminate within the given 5 seconds.
• Each bot will be able to store up to 1 MiB (1024*1024 bytes) of data on disk per game, for saving any stateful data they desire. The name of the bot's data file will be passed as the first command line argument to the bot process. Should a bot write more than 1 MiB of data during a single game, data from the beginning of the file will be removed to append additional data to the end of the file. At the end of each game, the data files will be wiped.
• Any attempt to tinker with the controller, runtime or other submissions will be disqualified. All submissions should only work with the inputs and storage they are given.
• Bots should not be written to beat or support specific other bots.

king-of-the-hill game

Sandbox notes

Anything missing or unclear (other than the parts specifically marked as TBD)?

Answer 28

Primitive Pythagorean triples

Introduction

A Pythagorean triple is a tuple of three positive integers a, b and c so that a² + b² = c². One example of that is (3, 4, 5).
One subset of those are primitive Pythagorean triples which require a, b and c to also be coprimes, so their only common divisior is 1. One example is (5, 12, 13)

The Challenge

Given three numbers representing a triple, output a truthy value if there is a triple representation of them that form a primitive Pythagorean triple and a falsy value if not.

Test cases

Truthy

Coming Soon

Falsy

Coming soon

---

tags: code-golf primes number-theory

TODO

• What about zero as input?
• Test cases
• Example for the different triple configurations?
• What about builtins?
• More descriptive title

Answer 29

Join the dots without crossing the line

code-golf geometry

---

Given a collection of distinct points in the unit square, output the points in order. This can be any order such that a closed polygon formed by straight line segments joining each point to the next (and the last back to the first) has no two lines crossing.

Input

1. There will be between 4 and 255 points.

2. Each one is represented by an ordered pair (x, y)

3. The coordinates will have entries in the range [0, 1), that is 0 <= x < 1

4. Each entry may have up to 8 decimal places, so the range is 0 to 0.99999999.

5. You may choose to accept integers instead, in which case the range will be 0 to 99999999.

6. You may take input in any reasonable format. For example:

   • (0.1, 0.2), (0.3, 0.4), (0.5, 0.7)
   • 10000000 20000000 30000000 40000000 50000000 70000000

Output

The output format need not match the input format as long as both are unambiguous.

Impossible cases

The code does not need to work for impossible cases, such as all points being colinear. Neither does it need to report such cases - it can simply not work. Behaviour is undefined.

Random algorithms

Your code must be deterministic. That is, it must always give the same output for the same input. For this purpose, the same points in a different order will be counted as distinct inputs and need not have the same output.

You may use pseudo random number generators provided the output is still consistent. If this requires setting a seed, that seed must be zero.

Time limit

Your code does not have to be particularly efficient, but it must finish for the 255 point test case in under 5 minutes.

The requirement for the code to be deterministic is so that this time limit can be checked with a single run. If your random number generator of choice cannot give consistent behaviour by default, then you will need to seed it with zero. If a random number generator does not allow for seeding and does not give consistent behaviour then you may not use that generator.

Test cases

[ TO BE ADDED ]

Output verification snippet

[ TO BE ADDED ]

Scoring

This is code golf. Shortest code in bytes wins.

---

Note that this is not a Traveling Salesman Problem. There is no requirement for the tour to be short, only for it to be non-intersecting.

Answer 30

The Fast and The Fourier

code-golfrestricted-complexity

Implement the Discrete Fourier Transform (DFT) for a sequence of any length using a Fast Fourier Transform algorithm (FFT). This may implemented as either a function or a program and the sequence can be given as either an argument or using standard input. A DFT has time complexity of O(n²) whereas a FFT has time complexity of O(n log n).

The algorithm will compute a result based on standard DFT in the forward direction. The input sequence has length n and consists of the complex values {x₀, x₁, ..., x_n-1}. The output sequence will have the same length and consists of {y₀, y₁, ..., y_n-1} is defined by the relation below.

Bluestein's algorithm

One algorithm that meets these requirements Bluestein's algorithm. It is a special case of the Chirp-Z transform and is able to compute the FFT for a sequence of any length n by transforming it in order to solve it as a cyclic convolution which can be solved with a time complexity of O(n log n).

Keep in mind that it is not required that you only use this algorithm in your implementation. If you know a better way, feel free to use it.

First, an identity is used to rewrite the initial DFT in a form where a convolution can easily be recognized.

You can obtain two sequences from this new form

which allow you to write the DFT as a convolution of two sequences.

Sample

Get the input
    x = [1, 2, 3, 4, 5]

Get the length of the input
    n = 5

Compute the 'a' sequence
    a = [1, 1.618 - 1.176j, -2.427 - 1.763j, 3.236 + 2.351j, -4.045 + 2.939j]

Compute the 'b' sequence
    b = [1, 0.809 + 0.588j, -0.809 + 0.588j, 0.809 - 0.588j, -0.809 - 0.588j]

Compute the convolution of 'a' and 'b' (using summation)
    y[0] = (a[0]*b[0] + a[1]*b[1] + a[2]*b[2] + a[3]*b[3] + a[4]*b[4]) / b[0]
         = 15 / 1 = 15

    y[1] = (a[1]*b[0] + a[0]*b[1] + a[2]*b[1] + a[3]*b[2] + a[4]*b[3]) / b[1]
         = (-4.045 + 1.314j) / (0.809 + 0.588j) = -2.5 + 3.441j

    y[2] = (a[2]*b[0] + a[1]*b[1] + a[3]*b[1] + a[0]*b[2] + a[4]*b[2]) / b[2]
         = (1.545 - 2.127j) / (-0.809 + 0.588j) = -2.5 + 0.813j

    y[3] = (a[3]*b[0] + a[2]*b[1] + a[4]*b[1] + a[1]*b[2] + a[0]*b[3]) / b[3]
         = (-2.5 + 0.813j) / (0.809 - 0.588j) = -2.5 - 0.813j

    y[4] = (a[4]*b[1] + a[3]*b[1] + a[2]*b[2] + a[1]*b[3] + a[0]*b[4]) / b[4]
         = 4.253j / (-0.809 - 0.588j) = -2.5 - 3.441j

The Fourier tranform of x
    y = [15, -2.5 + 3.441j, -2.5 + 0.813j, -2.5 - 0.813j, -2.5 - 3.441j]

Rules

• This is code-golf so the shortest solution wins.
• Builtins that compute FFT in forward or backward (also known as inverse) directions are not allowed.
• Builtins that compute the convolution are not allowed. (Most will have not been allowed by the previous rule as they use FFT internally.)
• Your solution must have time complexity of O(n log n) where n is the length of the input sequence.
• Floating-point inaccuracies will not be counted against you.

Test Cases

FFT([1, 1, 1, 1]) = [4, 0, 0, 0]
FFT([1, 0, 2, 0, 3, 0, 4, 0]) = [10, -2+2j, -2, -2-2j, 10, -2+2j, -2, -2-2j]
FFT([1, 2, 3, 4, 5]) = [15, -2.5+3.44j, -2.5+0.81j, -2.5-0.81j, -2.5-3.44j]
FFT([5-3.28571j, -0.816474-0.837162j, 0.523306-0.303902j, 0.806172-3.69346j, -4.41953+2.59494j, -0.360252+2.59411j, 1.26678+2.93119j] = [2, -3j, 5, -7j, 11, -13j, 17]

Related

• Compute the Discrete Fourier Transform - This contains some implementations for the standard DFT algorithm which has time complexity O(n²). You'll want to understand how to implement this before trying FFT.
• Too Fast, Too Fourier: FFT Code Golf - This previous challenge is the precursor to the current challenge here. Before, you only had to consider sequences where the length n was a power of 2 which allowed for simpler recursive implementations. The difference here is that you now have to implement an FFT algorithm that will work for sequences with any length.