# What is the Sandbox?

This "Sandbox" is a place where Code Golf users can get feedback on prospective challenges they wish to post to the main page. This is useful because writing a clear and fully specified challenge on the first try can be difficult. There is a much better chance of your challenge being well received if you post it in the Sandbox first.

See the Sandbox FAQ for more information on how to use the Sandbox.

## Get the Sandbox Viewer to view the sandbox more easily

To add an inline tag to a proposal use shortcut link syntax with a prefix: [tag:king-of-the-hill]

# Tell me my vocabulary words! Donated.

When taking textbook notes, I need to write down the vocabulary words and their definition. So your task is to write some code that will give me the vocabulary words and their definitions!

Vocabulary words are detonated with a * on both sides of them, like this: Sentences are .-delimited, meaning that after every . a new sentence starts. An example of a valid sentence would be: This sentence has a *vocab word* in it. The vocab word in the sentence is 'vocab word'.

Input: A string of text with some words marked with asterisks. Only valid inputs will be provided, meaning that only sentences with exactly two asterisks inside of them, and there is something between the asterisks.

Output: A list or delimited string where each item is in the following format: Vocabulary word: sentence. The Vocabulary word is the vocab word found in the sentence. The sentence must be the one with the emboldened vocabulary word in it. If there is any whitespace other than the  s separating the words, it needs to be stripped.

Test cases:

Input: *Alan Turing* invented the Turing machine. A *Turing machine* is a machine that follows simple rules, but is capable of any computation.

Output: *Alan Turing*: *Alan Turing* invented the Turing machine.
*Turing machine": A *Turing machine* is a machine that follows simple rules, but is capable of any computation.

Input: What is code-golf? *Code-golf* is the best site on the SE network. But what is SE, you ask? *SE* is a group of Q&A sites, with a system to prevent bad posts.

Output: *Code-golf*: *Code-golf* is the best site on the SE network.
*SE*: *SE* is a group of Q&A sites, with a system to prevent bad posts.

• So split on '.' and then filter to strings containing a *? Or can there be asterisks which don't mark vocabulary words? Should we trim whitespace at the start and end of the sentences? – Peter Taylor Apr 6 '17 at 9:54
• @PeterTaylor A string surrounded by * is a vocab word, like this: *vocab word*. You need to format the outputted sentence correctly, and trim whitespace. I will edit when I have more time. – Comrade SparklePony Apr 6 '17 at 13:52
• Are the following valid inputs or not? a) Unbalanced* asterisk; b) Empty ** vocabulary word; c) Vocabulary* word *has bad spacing. – Peter Taylor Apr 7 '17 at 10:05
• Only the last one is valid. – Comrade SparklePony Apr 7 '17 at 13:25
• The latest wording "only sentences with exactly two asterisks in them" suggests that there's no need to filter: just split on ., trim, and prepend Vocabulary word:  to each sentence. – Peter Taylor Apr 7 '17 at 21:03

# Base 32 RFC 4648 Compliant Alphabet!

When writing my handy-dandy totp/hotp token implementation in Python and Swift (ad: here), I encountered for the first time RFC 4648. There is a nice and long memo about RFC 4648, but I only had to focus on a very specific part of it: Page 8. If you are bored and want some enthralling reading, you can find this memo here, and a useful table here.

Basically, I was looking for the alphabet that could be used when base 32 decoding a String. Well, this is it: ABCDEFGHIJKLMNOPQRSTUVWXYZ234567, and padding, =. However, simply printing that is not the challenge –– that would be too simple1. Instead, we are going to print this (the comments are for your reference and do not need to be printed):

__,__,__,__, __,__,__,__, __,__,__,__, __,__,__,__,  // 0x00 - 0x0F or   0 -  15
__,__,__,__, __,__,__,__, __,__,__,__, __,__,__,__,  // 0x10 - 0x1F or  16 -  31
__,__,__,__, __,__,__,__, __,__,__,__, __,__,__,__,  // 0x20 - 0x2F or  32 -  47
__,__,26,27, 28,29,30,31, __,__,__,__, __, 0,__,__,  // 0x30 - 0x3F or  48 -  63
__, 0, 1, 2,  3, 4, 5, 6,  7, 8, 9,10, 11,12,13,14,  // 0x40 - 0x4F or  64 -  79
15,16,17,18, 19,20,21,22, 23,24,25,__, __,__,__,__,  // 0x50 - 0x5F or  80 -  95
__, 0, 1, 2,  3, 4, 5, 6,  7, 8, 9,10, 11,12,13,14,  // 0x60 - 0x6F or  96 - 111
15,16,17,18, 19,20,21,22, 23,24,25,__, __,__,__,__,  // 0x70 - 0x7F or 112 - 127
__,__,__,__, __,__,__,__, __,__,__,__, __,__,__,__,  // 0x80 - 0x8F or 128 - 143
__,__,__,__, __,__,__,__, __,__,__,__, __,__,__,__,  // 0x90 - 0x9F or 144 - 159
__,__,__,__, __,__,__,__, __,__,__,__, __,__,__,__,  // 0xA0 - 0xAF or 160 - 175
__,__,__,__, __,__,__,__, __,__,__,__, __,__,__,__,  // 0xB0 - 0xBF or 176 - 191
__,__,__,__, __,__,__,__, __,__,__,__, __,__,__,__,  // 0xC0 - 0xCF or 192 - 207
__,__,__,__, __,__,__,__, __,__,__,__, __,__,__,__,  // 0xD0 - 0xDF or 208 - 223
__,__,__,__, __,__,__,__, __,__,__,__, __,__,__,__,  // 0xE0 - 0xEF or 224 - 239
__,__,__,__, __,__,__,__, __,__,__,__, __,__,__,__,  // 0xF0 - 0xFF or 240 - 255


There may be trailing spaces after every line, and trailing newlines after the last one.

Also, the single digit numbers can be written as 0[digit] instead of [space][digit]. However, be sure to include the spaces between the four groups.

By the way, the __ actually represent 255, but the former do not make me drown in a sea of digits.

1 Should the challenge be to just print that string?

Any other suggestions to make this challenge more interesting?

• Perhaps get a list of characters (of any length) and print such a table? – ugoren Jul 29 '17 at 19:14

# Is this 2048 board valid?

Some 2048 boards are impossible to get into. For example,

2 _ _ 2
_ _ _ _
_ _ _ _
2 _ _ 2


will never occur in a 2048 game. Additionally, these are all impossible:

8 _ _ 8    8 _ _ _    2 2 2 2
_ _ _ _    _ 8 _ _    2 2 _ _
_ _ _ _    _ _ _ _    _ _ _ _
8 _ _ _    _ _ _ _    _ _ _ _


Your program needs to accept a 2048 board, and return a truthy value if the board is reachable, else falsy.

//Explanation of 2048 goes here.

I've listed 4 different boards that cover major test cases. Are there any others I'm missing?

• hehe, don't forget [tag:sliding-puzzle] – Stephen Aug 1 '17 at 19:56
• As you've stated yourself the main thing missing here is the bulk of the challenge. – TheLethalCoder Aug 2 '17 at 9:14
• I wonder if it suffices to look one step back, or if you need to check if the previous position can itself be produced. – xnor Aug 4 '17 at 7:35

# Smooth Usage [On hold while alternative scoring is considered]

We've all seen CPU usage graphs like this one:

Doesn't that look ugly? It would look much nicer as a lovely smooth sine wave...

## Challenge

Write a program in the language of your choice that will infinitely produce a regular sine wave in Task Manager's (or Activity Monitor's if that's your thing) CPU usage graph.

You may assume:

• Background CPU usage is constant
• Only a single core must display the pattern
• The system has sufficient cooling to prevent thermal throttling
• Features such as Intel TurboBoost are disabled

This is tagged as to encourage short answers, but ultimately will be a as I suspect perfect solutions will be hard to come by.

• – MTCoster Aug 11 '17 at 15:14
• code-golf and popularity-contest don't mix together. You have to choose one or the other, but making it strictly code-golf would be difficult because you'd have to define what is a good enough sine wave, but on the other hand popularity contests are very risky to do. – dzaima Aug 11 '17 at 15:16
• @dzaima That was exactly my dilemma - which would you suggest fits the challenge best? – MTCoster Aug 11 '17 at 15:17
• I'd say a scoring algorithm of some sort would be best for this, no idea how you'd do it. Like the related one was objective. If you could read the word, it was valid. With this, is a bumpy sin-wave a sin-wave? – Magic Octopus Urn Aug 11 '17 at 20:39
• @MTCoster If you're not sure whether popularity-contest fits, then you can be sure that it does not. It is quite difficult to make an well received one. Go with code-golf or make a code-challenge if you can come up with a good own winning criterion. – flawr Aug 11 '17 at 20:53

# Time bomb ping pong

## Challenge - Both teams

All users are divided into two teams based on their PPCG ID. For example, my ID can be found here, from which you can see that my ID is 34388. To check on which team you are, run the following snippet:

## Challenge

This is a challenge, all submissions should be written in

Your function should accept four variables as follows, obviously within your function you can name these whatever you like
- 1st variable represents the current value of 1 bar of Megatanium
- 2nd variable represents your current bank balance
- 3rd variable represents your current stock holding
- 4th variable represents the iteration number

The return value should be negative if you wish to sell stock, positive if you wish to buy stock, 0 if you wish to neither buy or sell

For example;
If you wish to buy 10 bars of Megatanium at the current price you would return 10
If you wish to sell 5 bars of Megatanium at the current price you would return -5

I will call your function 1000 times. Stock price will always be an integer, chosen at random, with a minimum of 0 and a maximum of 256. Method of selecting the stock price is described in more detail below, it will NOT be an even distribution!

Your bot will be disqualified if it does any of the following at any point

• Try to buy more stock than it can afford
• Try to sell more stock than it holds
• Try to write any value to any of the global variables
• Fail to return a value
• Return a value that is not an integer

Here is the code I will be running, the score output at the end will be your bot's score. It is calculated from your bank balance plus the value of your held stock at the latest value.

function go(bot) {
bank = 1000;
stock = 0;
disqualified = 0;
for (i=1; i<=1000; i++) {
price = prices[i];
trade = window[bot](price, bank, stock, i);
bank = bank - (price * trade);
if (bank < 0) disqualified = "RUN OUT OF MONEY";
if (stock < 0) disqualified = "TRIED TO SELL STOCK YOU DIDN'T OWN";
if (disqualified) break;
}
if (disqualified) {
console.log("Disqualified on iteration " + i + " REASON: " + disqualified);
}
else {
score = bank + (stock * price);
console.log(bot + " scores " + score);
}
}


The function for generating a suitable distribution of random values is a slightly modified version of the function described here
Every bot will be given the same set of prices, but the set will not be generated until immediately before the bots are run.

function randn_bm() {
var u = 0, v = 0;
while(u === 0) u = Math.random();
while(v === 0) v = Math.random();
w = Math.floor(Math.sqrt( -2.0 * Math.log( u ) ) * Math.cos( 2.0 * Math.PI * v ) * 32) + 128;
while (w < 0 || w > 256) w = randm_bm();
return w;
}
prices = [];
for (i=1; i<=101; i++) {
prices.push(randn_bm());
}


## Completion

You may submit as many bots as you like, try to be inventive with your algorithms! You may use a global variable called data, this will be initially set to null and will always be available to your function.

## Example bots

function buyBot(p,b,s,i) {
/* Bot always buys as much as it can */
return Math.floor(b / p);
}

function randomBot(p,b,s,i) {
/* Bot buys and sells randomly */
if (Math.random() > 0.5) {
return Math.floor(Math.random() * (b / p));
}
else {
return -Math.ceil(Math.random() * s);
}
}

function smartBot(p,b,s,i) {
/* Bot always buys at under 100 and sells at over 150 */
if (p < 100) {
return Math.floor(b / p);
}
else if (p > 150) {
return -s;
}
else {
return 0;
}
}

function bankruptBot(p,b,s,i) {
/* Bot always sells at under 100 and buys at over 150 */
if (p > 150) {
return Math.floor(b / p);
}
else if (p < 100) {
return -s;
}
else {
return 0;
}
}

function alternateBot(p,b,s,i) {
/* Bot buys and sells alternately */
if (data == 1) {
data = 0;
return Math.floor(Math.random() * (b / p));
}
else {
data = 1;
return -Math.ceil(Math.random() * s);
}
}


## Winning conditions

All bots will be run on locally by me approximately 1 week after the question is posted (date will be decided when question is posted, no point setting a date in sandbox)
Winner will quite simply be the bot that has the highest final score after the last iteration, as calculated by the function provided above. The array of prices used will be published after a winner has been crowned.
There are no set conditions on the speed of your function, but please be fair and try to avoid anything that will take more than a couple of minutes to execute

Note: Please leave an upvote if you think the challenge idea is good and is clear, a downvote if you think the challenge idea is bad, and comment if you can't understand the challenge. Last time I asked on TNB 2 users told me that they can't understand anything.

# Golf a return-oriented code generator!

## Background

Return-oriented programming (ROP) is a computer security exploit technique that allows an attacker to execute code in the presence of security defenses such as non-executable memory (W xor X technique) and code signing. (from Wikipedia)

## Challenge

In this challenge, you should write a program, that takes the code of the existing program and the required code, and output the stack necessary to execute that program.

## Rules

• Standard loopholes apply, as usual.
• How the machine works
• At first, IP is equal to the top of the stack, and the top of the stack is popped.
• For each clock cycle (whatever it means), the command at the position of IP is executed, and the IP is advanced if the command does not modify IP.
• The behavior if the IP is at the last instruction and that instruction does not modify IP is undefined.
• Assembly instructions
• All commands are case insensitive.
• Note: There is nothing that guarantees commands must be 3 characters long, or limited to some sets. After all, this is not real assembly. However:
• You can assume that all the characters are in the English alphabet, uppercase or lowercase.
• There may be some other commands "similar but not the same" with ret, so checking for the first character or the SHA256 hash won't work.
• The special command ret will pop the value on the top of the stack, and set the instruction pointer IP to that value.
• You may assume that all the other commands won't modify the stack, or the IP.
• The "existing program" and "required code" will be represented as a string, separated by newline characters (you may optionally take a list of strings as input).
• The required code will never contains ret.
• The output should be a stack of line-numbers in appropriate format (list of numbers - may be reversed, array of numbers, etc.)
• The command executed right after the last command in the "required code" must be a ret.
• Because the memory of the machine is limited, you should output the shortest possible stack. If there are multiple shortest stack, output any.
• You may assume that there exists an output.

## Example test cases:

• Existing program:
1:  add eax, ebx
2:  lea eax, [2*eax+4*ecx]
3:  ret
4:  mov eax, ebx
5:  xch ecx, eax
6:  ret

(the line numbers are just for demonstration purposes. They are not included in the input, you can use 0-indexing or 1-indexing)

(disclaimer: this is not real assembly, just for demonstration purposes)

• Required code:
lea eax, [2*eax+4*ecx]
xch ecx, eax
mov eax, ebx
xch ecx, eax

In that case, you should output [2, 5, 4] (2 is at the top of the stack), because if the stack have that value, then:

• First, IP = 2.
• The commands
2:  lea eax, [2*eax+4*ecx]
3:  ret

are executed.

• On executing ret, the IP get the value 5. Then, the commands
5:  xch ecx, eax
6:  ret

are executed.

• Then, similarly, when the next ret is executed, the value 4 is popped from the stack, and commands
4:  mov eax, ebx
5:  xch ecx, eax
6:  ret

are executed.

Therefore, the commands executed (apart from ret) are:

2:  lea eax, [2*eax+4*ecx]
5:  xch ecx, eax
4:  mov eax, ebx
5:  xch ecx, eax


which is equal to the "required code".

## Winning criteria

This is , shortest code in bytes win!

• You should probably include a list of all valid identifiers or if all of them are always 3 characters mention that and whether there are instructions that begin with r other than ret. – ბიმო Jan 28 '18 at 18:57
• @BMO Better now? – user202729 Jan 29 '18 at 12:00
• No idea what the alphabet ØA;Øa¤ is but apart from that I think you made it pretty clear now. Other things that came to mind: What if there are multiple possibilities for a shortest stack (eg. like this)? Will the input always have a solution (eg. unlike this)? And are the line numbers part of the input? If so is it safe to assume that they always start with 1 and have an offset of 1? Maybe you could add some testcases. – ბიმო Jan 29 '18 at 12:52

# Faux Compress a String

Given a string s, perform a faux compression on it. Below is an example with f('hello world').

To faux compress a string, start by taking a frequency count of all letters.

hello world -> [h:1, e:1, l:3, o:2, :1, w:1, r:1, d:1]

Next, sort smallest to largest in count with a tie-breaker of ASCII-code.

[ :1, d:1, e:1, h:1, r:1, w:1, o:2, l:3]

Next, in the original string, replace each letter with it's index in the frequency list.

[3,2,7,7,6,0,5,6,4,7,1]

Next, convert each integer to binary, and join them all with the digit 2, then convert this to base-3.

1121021112111211020210121102100211121 -> 240591504997661290

Lastly, print or return both this number and the sorted keyset of the frequency map.

[240591504997661290, ' dehrwol']

Is the final result.

You now have a "faux compressed" string.

To get a real compressed string you'd figure out the shortest sequence of bits to replace 2 with which would be a unique delimiter and treat the binary digits as they are, bits, instead of bytes.

# More Examples

000000000001 -> [58839486765, '10']
eeEeeeeeeeeeeEEEEEeeeeee -> [16508589985213004629636, 'Ee']


# Rules

• Your code's function may be undefined if the following is not met:
• The string will contain more than one unique character.
• Lowest byte count wins because this is .

# PSA: I have many PENDING PROPOSALS, tell me which to delete.

If you post a comment on any of these challenges with the words "This isn't good in my opinion."

It will be removed.

• The posted one by MDXF. – user202729 Feb 3 '18 at 5:28

# Casinos and Gamblers king-of-the-hillcops-and-robbers

You either play as a casino, or as a gambler. Casinos offer bets, and gamblers choose bets to take. Casinos want to make money, gamblers want to have more money than others. Read that sentence again, it is the core concept here.

1. All casinos simultaneously comes up with a Bet. A Bet consists of three parts:
1. Entry Fee (Positive integer amount a gambler must pay to take)
2. Odds (The chance that a gambler will win between 0 and 1)
3. Reward (Positive integer amount a gambler is given if he wins). This can be any amount, even if it would make the casino go negative.
2. Each gambler optionally chooses a bet to take. They must have enough money to pay for the Entry Fee.
3. We calculate who wins and who doesn't (using a PRNG), and pay out.

At the end of a game, we give points as follows:

1. Casinos receive 1 point for each dollar they have (can be negative)
2. Gamblers receive N^2 points for having more money than N other gamblers.

A tournament consists of many games, and a player's score is their average score across all of the games.

Gamblers and Casinos all have complete information throughout the game.

• Might want to specify that entry fee and reward must be positive (negative/negative games map to positive/positive games but complicate the "can this gambler afford this game" calculation.) – histocrat Jan 31 '18 at 19:34
• I have a hunch that 100 dollars won't give quite enough granularity for casinos to work with. Maybe bump it up to 10,000? – Beefster Feb 2 '18 at 23:09
• Also, how are odds represented? Fraction? Floating point number? Precision? – Beefster Feb 2 '18 at 23:10
• @Beefster Floating point, of course. I think you may be right, but 10,000 seems too high. I think I'll do 1,000 – Nathan Merrill Feb 3 '18 at 0:06

# Busier Beaver cops-and-robbersbusy-beaver

## Cops

You will write two programs in a language of your choice

• A public program: This program must execute in a finite amount of time. So it can not go on indefinitely (although there is no time limit). It also wise if you program it to output a large number of bytes to standard output. This is the what you post in your answer. You must also post the programming language.
• A secret program: This program must output more bytes than the public answer, i.e. it is a busier beaver. It also must not go on indefinitely. It also can not be longer than the public program. You do not post it the answer immediately. After one week, if no robber has cracked the answer, you edit it in.

For these programs, you may assume that numerics types are actually unbounded, i.e. that overflow never occurs. This means that you can store, for example, Graham's number in a variable. It also means that finding the maximum value of storage capacity of a numeric type results in an error.

If no robber has cracked your answer, your score is equal to (length of public program)/(length of secret program), which you are trying to maximize. In case of ties, the longer public program wins.

## Robbers

The cops will post a public program. Your job is to find a busier beaver. That is, you need to find a program that outputs more bytes to standard output than the cops program. It can not go on indefinitely, and can not be longer than the public program (although it can be the same length).

You get points equal to (length of cops public program)/(length of your program) for each post you crack.

• Need to specify that it's the number of bytes output when given no input. – Peter Taylor Feb 16 '18 at 11:38

# Indices of inner join (code-golf)

Given two lists of integers x and y of possibly unequal lengths, return the list of pairs (i, j) such that the ith element of x is equal to the jth element of y.

The output consists of a vector of pairs or a pair of vectors (the zip of the other option, may be useful for languages without pair data structure). The pairs may be given in any order, and using 0-based or 1-based indexing.

In pseudo-code: (this returns two lists of indices, assumes 1-based indexing, and gives lexicographically sorted output)

input vector<int> x, vector<int> y
vector<int> xout, yout;
for (i in 1 to length(x))
for (j in 1 to length(y))
if (x[i] == y[j]) {
add i to end of xout;
add j to end of yout;
}
return xout, yout;


This is code-golf so answers will be scored in bytes with fewer bytes being better.

### Test case 1

x = [5, 1, 1, 2], y = [5, 1]

-> xout = [1, 2, 3]


(5, 1, 1 each appears once in y)

-> yout = [1, 2, 2]


(the first position appears once in x, the second twice)

Reshuffling the pairs is okay:

-> xout = [2, 1, 3]
-> yout = [2, 1, 2]


## Test case 2

x = [2, 2, 2, 3, 3], y = [4, 2, 2, 2]

-> xout = [1, 1, 1, 2, 2, 2, 3, 3, 3]


(each of the three first positions finds three matches in y)

-> yout = [2, 2, 2, 3, 3, 3, 4, 4, 4]


Improvements and clarifications are very welcome!

• It should be ready to post now. The sandbox is not very active (not many people know about it), so even sandboxed posts may not have sufficient feedback. – user202729 Feb 20 '18 at 2:29
• "The output consists of a vector of pairs or a pair of vectors" seems unnecessarily restrictive. The semantically correct return type in languages which support it would be a set of pairs, and while that may not be the golfiest I don't see a reason to prohibit it. – Peter Taylor Feb 20 '18 at 12:15

# Number of Adjacently Divisible Partitions of n

Output the following sequence (OEIS A167865):

1, 0, 1, 1, 1, 1, 2, 1, 2, 2, 2, 1, 4, 1, 3, 3, 3, 1, 5, 1, 5, 4, 3, 1, 6, 2, 5, 4, 5, 1, 9, 1, 6, 4, 4, 4, 8, 1, 6, 6, 7, 1, 11, 1, 8, 8, 4, 1, 10, 3, 10, 5, 8, 1, 11, 4, 10, 7, 6, 1, 13, 1, 10, 11, 7, 6, 15, 1, 9, 5, 11, 1, 14, 1, 9, 12, 8, 5, 15, 1, 16, 9, 8, 1, 18, 5, 12, 7, 10, 1, 21, 7, 13, 11, 5, 7, 12, 1, 14, 12, 15, 1, 20, 1, 14, 17, 9, 1, 18, 1, 21, 10, 17, 1, 19, 5, 14, 14, 7, 6, 22, 3, 14, 9, 12, 8, 25, 1, 18, 13, 17, 1, 24, 8, 16, 21, 11, 1, 23, 1, 22, 6, 12, 7, 19, 7, 15, 19, 11, 1, 28, 1, 21, 17, 18, 11, 27, 1, 16, 10, 18, 6, 28, 1, 18, 25, 9, 1, 25, 5, 29, 19, 18, 1, 27, 14, 20, 8, 11, 1, 30, 1, 31, 15, 21...


Number of partitions of n into distinct parts greater than 1, with each part divisible by the next.

### Definition:

Choose one of the three options:

• Output the sequence indefinitely.

• Take n as input and output the n first elements of the sequence.

• Take n as input and output the nth element of the sequence. Both 0- and 1-based indices are allowed, but please specify which one your answer uses.

Hint: There is a simpler formula than the one used on OEIS and in this post. It may save you some bytes (it saved six bytes on a simple reference implementation I made in Python). I'll add it here later.

This is , so the shortest answer in bytes wins.

• I'm not sure about having three different output methods, when one even changes the input required. Almost looks like 3 different challenges. Maybe you could make it so that if no input is given output sequence indefinetely, and if input is given output option 2 or 3. – Brian H. Jan 25 '18 at 10:03
• @BrianH. I saw a few sequence challenges allow to choose from these three output methods, and it seemed to work. Here's one such challenge: codegolf.stackexchange.com/q/152402/61405 – Steadybox Jan 25 '18 at 10:32
• True, i wonder if there's a Meta question about this, can't seem to find one – Brian H. Jan 25 '18 at 10:54
• @BrianH. I don't think there's a meta question for this particular issue, but I think it at least partly falls under allowing flexible input. – Steadybox Jan 25 '18 at 11:19

# Background Information: What is a Fenwick Tree?

A Fenwick tree is a way of representing the prefix sums of an array of numbers (basically, it makes it easy to get the sum of a contiguous run of numbers). While a normal array has O(1) access time, O(1) modification time, and O(n) summation time, a Fenwick tree has O(log n) access time, O(log n) modification time, and O(log n) summation time.

Note that a Fenwick tree actually works with any commutative binary operation in terms of getting the running values up to that value.

I won't go into details about exactly how Fenwick trees work, but basically you have the following pseudocode implementations for the two operations modify and sum (accessing the nth element is the same as doing sum(1 .. n) - sum(1 .. n-1)).

func modify(index, change) # index points to the value in the represented array that you are modifying (1-indexed); change is the amount by which you are increasing that value
while index <= len(fenwick_tree)
fenwick_tree[index] += change
index += least_significant_bit(index)

func sum(count) # sum(n) sums the first n elements of the represented array
total = 0
while index > 0
total += fenwick_tree[index]
index -= least_significant_bit(index)

least_significant_bit(x) := x & -x


# Challenge

Given the Fenwick tree for an array a and an integer n, return the sum of the first n values of a; that is, implement the sum function given as an example.

# Reference Implementation

A reference implementation in Python for both the make_tree and sum functions is provided here.

# Test Cases

[6, 6, 3, 20, 8, 12, 9, 24, 8, 12], 6 -> 32
[6, 4, 3, 36, 1, 8, 3, 16, 5, 4], 3 -> 7
[2, 10, 1, 4, 4, 2, 0, 32, 1, 14], 4 -> 4
[7, 8, 4, 36, 9, 0, 0, 8, 1, 4], 5 -> 45
[3, 0, 7, 12, 4, 18, 6, 64, 6, 14], 6 -> 30
[3, 4, 3, 28, 5, 6, 8, 40, 1, 8], 9 -> 41
[4, 8, 8, 4, 0, 18, 7, 64, 0, 12], 7 -> 29
[9, 0, 6, 16, 8, 14, 5, 64, 3, 18], 0 -> 0
[3, 14, 7, 12, 2, 6, 5, 0, 7, 18], 2 -> 14


# Rules

• Standard Loopholes Apply
• This is , so the shortest answer in bytes in each language will be considered the winner of its language. No answer will be marked as accepted.
• You may take the two inputs in any order and the list in any reasonable format.
• You may assume that the integers in the tree are all non-negative.
• No input validation - the index will be non-negative and at most the length of the Fenwick tree
• You may assume that all values (in the list, as the index, and the output) will be at most 232-1

Happy Golfing!

# Sandbox

• Is my explanation of a Fenwick tree sufficient enough that most people can understand it?
• Are my test cases sufficient?
• Any more tag suggestions?
• your tests cases appear correct – ngn Mar 2 '18 at 2:31
• @ngn Yay, thanks. I'll remove that from the footer then; I was asking because earlier in a CMC my values were apparently really wrong because I was doing something dumb :P – HyperNeutrino Mar 2 '18 at 2:40

Consider a typical dot-matrix LED module. The LEDs are addressed in rows and columns. A LED will light up iff the voltage on the row R it's on is high (1), and the column C it's on is set to low (0). For example,

1  | 0 1 1 0
0  | 0 0 0 0
0  | 0 0 0 0
1  | 0 1 1 0
^  +---------
R C> 1 0 0 1


In other words, state of the LED at the rth row and cth column will be r AND NOT(c).

To make arbitrary images, different parts of the matrix are lighted up sequentially. In other words, the sequential frames form the final image through element-wise OR. For example (adressing row-by-row)

| 1 0 0 1    Frame 1: R=[1 0 0 0]', C=[0 1 1 0]
| 0 1 0 0    Frame 2: R=[0 1 0 0]', C=[1 0 1 1]
| 0 0 1 0    Frame 3: R=[0 0 1 0]', C=[1 1 0 1]
| 0 0 1 0    Frame 4: R=[0 0 0 1]', C=[1 1 0 1]
+--------


However, a more efficient way would be to address the third and fourth row together in a single frame, Frame 3: R=[0 0 1 1]', C=[1 1 0 1]. This way, we can address the entire display in only three frames.

Your task is to make a program or function that outputs the required frames to display an arbitrary dot-matrix, using as few frames as possible.

## Input

A binary square matrix taken in any of the default input methods in any convenient format. To allow for submissions taking the input as bytes, the size of the matrix will always be a multiple of 8.

## Output

A minimal set of frames that addresses only the required LEDs, using any of the default output methods in any convenient format. This includes outputting bytes or hex representations rather than vectors of 1s and 0s.

# Testcases

Note: the output given is just one way of addressing the matrix. There may be many different options; however, your solution must not use more frames than these examples.

Testcase 1

Binary:                            Hex:
0 0 0 0 0 0 0 0                    00
0 1 1 1 1 0 0 0                    1E
0 1 1 1 1 0 0 0                    1E
0 1 1 1 1 0 0 0                    1E
0 1 1 1 1 1 0 0                    3E
0 0 0 0 1 1 0 0                    30
0 0 0 0 0 0 0 0                    00
0 0 0 0 0 0 0 0                    00

Frame 1: R=[0 1 1 1 1 0 0 0]', C=[1 0 0 0 0 1 1 1]; (hex: R=1E, C=E1)
Frame 2: R=[0 0 0 0 1 1 0 0]', C=[1 1 1 1 0 0 1 1]; (hex: R=30, C=CF)

Testcase 2

Binary:                            Hex:
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0    0001
0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0    0000
0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0    0000
0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0    0000
0 0 0 1 1 1 1 1 1 1 1 1 0 0 0 0    0FF8
0 0 0 1 1 1 1 1 1 1 1 1 0 0 0 0    0FF8
0 0 0 1 1 1 0 1 1 1 1 1 0 0 0 0    0FB8
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1    FFFF
0 0 0 1 1 1 1 1 1 1 1 1 0 0 0 0    0FF8
0 0 0 1 1 1 1 1 1 1 1 1 0 0 0 0    0FF8
0 0 0 1 1 1 1 1 1 1 1 1 0 0 0 0    0FF8
0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0    0000
0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0    0000
0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0    0000
0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0    0000
0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1    8000

Doable in 6 frames.


Make sure your submission also handles a matrix of all ones and all zeros (both of course can be handled in a single frame).

• So if I understand correctly, the sequence of frames are composed elementwise by an OR? – Giuseppe Mar 8 '18 at 17:26
• @Guiseppe Yes. I'll edit that in! – Sanchises Mar 8 '18 at 19:04

# Minimal viable file corruptor

Your totally legal ROM collection, as vast as it may be, has started feeling a bit mundane recently. Why not spice it up a notch? Write a program that takes in the following arguments:

• The first (inclusive) and last (exclusive) bytes between which the corruption will occur (indexing can start from either 0 or 1, as long as it's consistent)
• n, the distance between bytes to be corrupted (1 = all bytes, 2 = every second byte, etc.)
• i, the increment value
• Path or contents of the file to be corrupted

and saves or outputs a modified version of the file where every nth byte in the specified range has been incremented by i. In case of an overflow, take the modulo 256 of the number. If saved as a file, the path can be anything but the input one (unless you've appended something to it or whatever). You wouldn't want to lose your legally-acquired ROMs, would you?

Examples:

File:   00 01 02 03 04
Start:  0
End:    5
n:      1
i:      7
Output: 07 08 09 0a 0b

File:   ff ff ff ff ff ff ff ff
Start:  2
End:    5
n:      1
i:      1
Output: ff ff 00 00 00 ff ff ff

File:   00 00 00 00 00 00 00 00 00 00
Start:  3
End:    8
n:      2
i:      16
Output: 00 00 00 10 00 10 00 10 00 00


You want as much space as possible for your most definitely not pirated files, so shortest bytecount wins.

TODO: clarify the rules a bit? also another example or two

• Operating on files seems to be quite more complex than choosing not to do so, especially since there is the added restriction to save the new file with a different name. I suspect noone would choose to work with files. My suggestion is to either make it mandatory as part of the challenge (it's fine if your challenge is not solvable with some languages) or remove that option entirely. – Leo Mar 25 '18 at 10:36

# That's MY Program Now

Given the previous answer in the chain, write a program that outputs that program.

The start of this challenge will be the following Brain-flak program:

# Brain-Flak, 148 bytes

(((((((((((()()()()){}){}){}()))){}{}())[][][][])[][])[[]]())[[][][][][]]())([([]([])[][]{})]()()()([[]](([()()()]([([][][])](((({}()){}))){}{})))))


Try it online!

# Scoring

Your answer will be scored based on the size of the previous answer in comparison to your answer. You are aiming to maximize your score (the max being 1, the minimum allowed is -10).

1-[Your Answer's Bytecount]/[Previous Answer's Bytecount]


The highest possible score will be 1, which means an empty program outputs the previous program (if this ever happens, the challenge is over). Your score can be negative, and you shouldn't see this as being a bad thing, it is what it is. The minimum allowable score, however, is -10. No Lenguage answers or answers that would destroy the challenge.

# 1. 05AB1E, 149 bytes (Score -0.0067)

"(((((((((((()()()()){}){}){}()))){}{}())[][][][])[][])[[]]())[[][][][][]]())([([]([])[][]{})]()()()([[]](([()()()]([([][][])](((({}()){}))){}{})))))


Try it online!

But, the score of this program would be awful (negative even -0.0067). However, don't let a bad score dissuade you from competing if your goal is to make it a bit more difficult for the next person to attempt the challenge. Conversely, if your goal is to post a trivial answer, try not to gunk up the challenge too much.

#<Answer #>. <Language Name>, <N Bytes> (<Score>)

<Code>



# Rules

• No language may be reused until there have been 20 answers.
• This is arbitrary to version number, E.G. you cannot use Python 2 if 3 has been used.
• You may not post a second answer until 2 other people have answered after you.
• If you and another person submit the same answer #, use timestamps to decide who deletes.
• (or marks "non-competing").
• Your post may have a negative score (E.G. Java will probably be negative).
• Your score may not exceed -10.
• PRNG, Encryption and any form of hashing is explicitly banned (E.G. gzdeflate).
• This is , but the best score will be considered the winner.
• The scores can be used as a decider for best answer though (if I choose to).

Sandbox question: Could this be a cops and robbers answer chaining question where the cops are trying to reduce the size while the robbers are trying to increase it? If cops get to 1 or less bytes before robbers can fill a TB HDD, one wins.

• I'm not sure it's a good idea to make people delete their post just because somebody posted right before them. Maybe they should instead indicate that their post is no longer part of the chain? Maximizing the score will take a lot of hard work, especially since there's no opportunity to edit once the next answer has been posted, and having to delete your answer might be very frustrating. – Reinis Mazeiks Mar 27 '18 at 14:00
• I think it would be a good idea to keep people from chaining of their own answers. Seems abusable. – Kamil Drakari Mar 27 '18 at 15:04
• @KamilDrakari it is abusable. Think CSPRNGs. – NieDzejkob Mar 27 '18 at 15:25
• @NieDzejkob That remains an issue though; the intermediate answer might simply wrap the previous one in a print statement and would remain highly compressible for the user with the key. – Dennis Mar 27 '18 at 15:27
• @Dennis Yeah, actually this seems to be a bigger problem. – NieDzejkob Mar 27 '18 at 15:29
• related. (That idea's on hold for the moment as I have a busy week of travel. I probably won't post it if you post this first.) – Nathaniel Mar 27 '18 at 19:48
• @NieDzejkob I forgot that rule, nice catch. I was pretty much copying the OEIS one. – Magic Octopus Urn Mar 27 '18 at 22:20
• Isn't it the same as this one? – Weijun Zhou Mar 28 '18 at 2:12
• @Dennis any better? – Magic Octopus Urn Mar 29 '18 at 18:17
• Better. I'd explicitly ban encryption, hashing, and PRNG though. Marking invalid answers non-competing isn't enough by the way. Our policy is to delete them anyway. – Dennis Mar 29 '18 at 18:36

# Polyglot in a box

Output the smallest bounding rectangle that fits around your code, with the border being of a different character than the inside.

For example, if your code is

ab
c  d

e


then the smallest bounding box is 7x6 since the code fits right in

######
#ab  #
#c  d#
#    #
#    #
#e   #
######


Hence, a valid output is

######
#    #
#    #
#    #
#    #
#    #
######


(note how the border # is different from the inside ).

and the bounded area is 5 × 4 = 20.

# Summary

• Output the smallest bounding rectangle your code fits in

• The border should be of a different character than the inside, neither can be newlines

• Only trailing/leading newlines are allowed, nothing else should be in the output

• Output to STDERR is ignored, and your program should not take any input

• Submissions must be full programs, functions are not allowed

• 0-byte programs are not allowed

• The program must run in at least 2 different programming languages and output the same bounding box in each one of them

# Score

This is a , so your program has to run in at least 2 different programming languages. Each of these languages must output the bounding box for the entire program. The winner is the submission with the most languages, with the bounding area (smaller is better) being the tie-breaker.

• I probably already know the answer, but it's not 100% clear from your current example since the box is 6x6: are the boxes always squares, or can the also be rectangles? I.e. if the e in your example would be one line lower, would the box be 6x7 or 7x7? – Kevin Cruijssen Mar 29 '18 at 19:52
• @KevinCruijssen I have edited the example so that it is no longer a square, so the box would be 7x6 – user41805 Mar 29 '18 at 20:00
• Hard to define what language is different when requiring a same result – l4m2 Apr 3 '18 at 8:16
• @l4m2 so what do you suggest? – user41805 Apr 6 '18 at 8:39
• @Cowsquack I don't quite know. Previous polyglot require different behavior on different language to force different language – l4m2 Apr 6 '18 at 10:38