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

How fast (slow) is your language?

This is a question both to test your coding skills but also to speed benchmark your favorite language. The code snippet will make a table of the fastest code per language. It is related to previous fastest-code [challenge]1 so you may find some of the code there a useful starting point.

The challenge is to write the fastest code possible for computing the permanent of a matrix whose entries are floating point in the range -1 to 1.

The permanent of an n-by-n matrix A = (ai,j) is defined as

Here S_n represents the set of all permutations of [1, n].

As an example (from the wiki):

In this question matrices are all square and will only have the floating point values in the range -1 to 1 (excluding both ends). I will construct all tests in such a way that the permanent is also in the range -1 to 1.

Examples

Input:

[[-0.34389946 -0.811193  ]
 [ 0.62778788 -0.09918764]]

Permanent:

-0.47514655471

Input:

[[-0.34389946 -0.811193  ]
[ 0.4783581  -0.56636227]]

Permanent:

-0.19326906099

The task

You should write code that, given an n by n matrix, outputs its permanent.

As the output will never be bigger than 1 in absolute value you do not have to worry about overflow. However you do have to worry about numerical accuracy. All answers should be correct up to 8 decimal places.

Languages and libraries

You can use any available language and libraries you like but no pre-existing function to compute the permanent.

More to be added..Work in progress

Answer 2

Directional Brainf*ck Compiler/Interpreter code-golf

Challenge: Write a Brainf*ck compiler with 4 extra commands.

L Set the direction to go left
R Set the direction to go right
D Set the direction to go down
U Set the direction to go up

The original commands (altered):

+ Increment the cell one
- Decrement the cell one
[ Start a loop, if the cell is 0 then go to the next ]
] end a loop if the current cell is 0. Else go back to the last [ read and continue from there (in the direction you were going last time it was read.
. output the byte at the data pointer.
, accept one byte of input, storing its value in the byte at the data pointer.
> point to the cell to the right
< point to the cell to the left

Compiler/Interpreter

In this case the compiler must either convert the code to another language or be an interpreter and run the code.

This is basically a directional version of brainf*ck. Directions should work the same way they do in ><>.

The pointer should start at the tape's beginning. It must be infinite in the right direction. Left infinite is optional (if you add it -10 to the score). Upon end of code output (in any reasonable form) the current values on all the stacks. If a ] is hit before a [ output a warning (with a message of your choosing). If a , is met at the end of the code you can do with it as you please. The program will terminate at the end of the file.

Standard loopholes apply.

Answer 3

Modular Reverse Recursion Sequence

Given any number n > 0, let r represent the reverse of the number n. Iterate until the final result is zero, passing the result of each iteration back into the function using recursion or a methodology of your choice by performing the below operation:

• If r > n for that iteration the result is r % n.
• If n > r for that iteration the result is n % r.
• If n % r = 0 or r % n = 0, you terminate iteration.

Take the intermediate result of each execution and store them in an array for the final answer.

Lets walk through an example where n=32452345.

54325423 % 32452345 = 21873078 # r > n, uses r % n
87037812 % 21873078 = 21418578 # r > n, uses r % n
87581412 % 21418578 = 1907100  # r > n, uses r % n
1907100 % 17091 = 9999         # n > r, uses n % r
9999 % 9999 = 0                # r % n = n % r = 0, terminated

Result: [21873078, 21418578, 1907100, 9999]     

Another example n=12345678:

87654321 % 12345678 = 1234575 # r > n, uses r % n
5754321 % 1234575 = 816021    # r > n, uses r % n
816021 % 120618 = 92313       # n > r, uses n % r
92313 % 31329 = 29655         # n > r, uses n % r
55692 % 29655 = 26037         # r > n, uses r % n
73062 % 26037 = 20988         # r > n, uses r % n
88902 % 20988 = 4950          # r > n, uses r % n
4950 % 594 = 198              # n > r, uses n % r
891 % 198 = 99                # r > n, uses r % n
99 % 99 = 0                   # r % n = n % r = 0, terminated

Result: [1234575, 816021, 92313, 29655, 26037, 20988, 4950, 198, 99]

A final example n=11000:

11000 % 11 = 0 # n % r = 0, terminated

Result: []

Answer 4

Simplified maze-solver

A spin-off from this question Textual maze solver

Write a program, that will take an bunch of 0's and 1's as it's input (see below), and a half-solved maze as it's output. The program should take 1's as walls and 0's as corridors. The output should should show 99's as walls and a number as the distance from the start of the maze. The maze should have no real entrance/exit; instead, the entrance is the square in the 2nd column of the 2nd row.

Examples (allowed cases):

Input               Output

1 1 1 1 1 1         99 99 99 99 99 99
1 0 0 1 0 1         99 00 01 99 05 99
1 1 0 0 0 1   -->   99 99 02 03 04 99
1 0 1 1 0 1         99 10 99 99 05 99
1 0 0 0 0 1         99 09 08 07 06 99
1 1 1 1 1 1         99 99 99 99 99 99 

{{1, 1, 1, 1, 1, 1, 1, 1, 1},         99 99 99 99 99 99 99 99 99
 {1, 0, 0, 0, 1, 0, 0, 0, 1},         99 0  1  2  99 16 17 18 99
 {1, 1, 1, 0, 1, 0, 1, 0, 1},         99 99 99 3  99 15 99 19 99
 {1, 0, 0, 0, 1, 0, 1, 0, 1},   -->   99 6  5  4  99 14 99 20 99
 {1, 0, 1, 1, 1, 0, 1, 0, 1},         99 7  99 99 99 13 99 21 99
 {1, 0, 0, 0, 0, 0, 1, 0, 1},         99 8  9  10 11 12 99 22 99
 {1, 1, 1, 1, 1, 1, 1, 1, 1}}         99 99 99 99 99 99 99 99 99

Examples (not allowed outputs and inputs):

11111 10101 10101 10001 11111  --> 9999999999 9900990699 9901990599 9902030499 9999999999

Notes:

• as seen above, the input and output must be bunch of numbers separated by whitespaces, commas, full stops, newlines, parenthesis (and so on), and mustn't be in a single row

• you can output 01 instead of 1

• cases where the distance is over 99 don't need to be covered

• the program doesn't need to solve the maze, just to find the distance from the start

• two fields connected diagonally aren't next to each other

• it's code-golf, so the shortest answer in bytes wins!

---

code-golf maze

Answer 5

Defs need to fix up layout

[Very much a WIP]

Maze battle

In this challenge, bots will team up, navigate around a maze and try to destroy the enemy team's artifact, and protect their own.

A maze might look like this. Note that the bots will receive numbers rather than ascii art, which represent their vision, and the objects they see.

+---------+-+---+-------+++-+-+---+-+-------+-+-----+
|         | |   |    #  | | | |   | |       | |     |
+-+ +-+-+ + + + +-+-+ +-+ + + + + + + + +-+-+ +-+ + |
|   |         |         |     | |   | | |   |     | |
| +-+-+ + +-+ +-+ + + +-+ + +-+ +-+ +-+ + +-+ +-+ + |
|       | |   |   | |     | |   |         | |   |   |
| +-+-+-+ +-+-+-+ + + + + +-+ +-+-+ +-+ + + + +-+ + |
|   |     |       |   | |   |   |     | | |       | |
| + + +-+-+ +-+ +-+ +-+ +-+ + +-+ + + + + + +-+ + + |
| |       |                 | |   | | |     |   | | |
| + + + +-+-+-+-+ +-+-+-+ + + +-+ +-+ + +-+-+-+ +-+-+
| | | |     |   | | |     |     |   | | |           |
| +-+ +-+ + +-+ +-+ +-+-+ +-+ + + + + + +-+-+ +-+ + |
|   | |   | |           | |   | | | |   | | |     | |
| +-+ + +-+ +-+ + + + +-+-+-+ +-+ +-+-+ + + + +-+ + |
|     | |       | | |   | | | | | |         |   | | |
| + + +-+ + + + + +-+ +-+ + +-+ + +-+ +-+-+ +-+ +-+-+
| | |   | | | | |   |   |       | |   | |       |   |
| +-+ + + +-+ +-+-+-+ +-+ +-+-+ + + +-+ + +-+-+ +-+ |
|   | |   |         |       |   |       |   |       |
+-+ +-+-+ +-+ +-+ +-+ + +-+ + + + +-+ +-+ +-+ + +-+-+
|   |   |   |   |   | | |     |     |   | |   |     |
| + +-+ +-+ + +-+-+-+ + + + +-+-+-+ +-+ + + +-+ +-+ |
| |       |   |   |     | |         | |   | |       |
| +-+-+ + +-+ +-+ + +-+-+-+ + + + +-+ +-+ +-+-+ +-+ |
| |   | | | |       | |   | | | | |   |     |     | |
+-+-+ + +-+ +-+-+-+-+ +-+ +-+ +-+ + +-+-+ +-+ +-+ + |
| | | | |   |           |     | |     |       | | | |
| + + +-+-+ + +-+ +-+-+ + +-+-+ +-+ +-+-+-+ +-+ +-+-+
|   |     | | |             |   | |   | |     |     |
+-+ +-+-+ + + + +-+ +-+-+-+ +-+ + +-+ + +-+ +-+ +-+-+
|   | |   |   |   | |     | |   |     |   |       | |
| +-+ + +-+-+ + +-+ + + +-+-+ + + + + + +-+-+ + + + |
|       | |           |       |   | | | |     | |   |
| +-+-+ + +-+ + +-+-+ + + +-+ + +-+-+ + +-+ + + +-+ |
|   | |   |         | | | |   |     |   | | | | |   |
+-+ + + + + + + +-+ + +-+-+-+-+ +-+-+ +-+ +-+-+ + +-+
|       |   | | |           |     | | |   | |       |
+-+-+-+ + +-+-+-+-+-+ + +-+-+ +-+ + +-+ + + + +-+ + |
|     |   | |         |     | |     |   |       | | |
+-+ +-+ +-+ +-+ + +-+ +-+-+ + + +-+ +-+ +-+ +-+ +-+-+
|     | | |     |   |         | |           |   |   |
+-+ +-+-+ + +-+-+ +-+-+ +-+-+ +-+ +-+-+-+-+ + +-+ + |
|               | |   |                 |   | |   | |
+-+-+ +-+-+-+ + + + + +-+-+-+-+-+-+ +-+ + + +-+ +-+ |
|       |   | | |   |   |           | | | |       | |
| +-+-+ + + +-+ +-+ + + +-+-+ +-+ + + + +-+-+-+-+ + |
| |       | | | |   | |       |   |     |           |
+-+-+ + +-+-+ + + +-+ +-+ +-+-+ + +-+ + + +-+-+ +-+-+
| |   |     |   | | |   |       |     | |     |     |
| + +-+ + + + + + + + + + + + + +-+-+-+ +-+-+ +-+-+ |
|       | | | |    #  |   | | | |       |     |     |
+-------+-+-+-+-------+---+-+-+-+-------+-----+-----+

Bots receive information about their current environment. They will receive a 8 lines of numbers, representing their view in each of the directions. vision is blocked by walls, and walls only, so at the end of the line of sight is a wall.

Numbers represent the following things:

• 0 represents a space with nothing in it.
• 1 represents a friendly bot
• 2 represents an enemy bot
• 3 represents your team's artifact
• 4 represents the enemy team's artifact

To destroy the enemy's artifact, you have to shoot it a bunch. heaps. So, you probably want to bring that artifact to your team, or your team's side, so that you can shoot it more.

When you die, you respawn after 5 turns.

At the start of the round, bots spawn into the first third of the maze on their side. when respawning, they also spawn into this area.

Answer 6

Format an XML file

Your task is to parse an XML snippet (not necessarily an entire file) and format it. I am explicitly making this simple to encourage extremely golfed code.

The formatter should transform XML like this:

<?xml version="1.0" encoding="UTF-8"?>
<body>
    <div class="community-option">
        <input id="communitymode" name="communitymode" type="checkbox"/>
        <label for="communitymode" title="Marking an answer community wiki encourages others to edit it by lowering the reputation barrier required to edit. However, you will not gain any upvote reputation from it. This cannot be undone.">community wiki</label>
        <a href="www.hoehel.be"><i>My inner web developer hates me</i></a>
        <b>BOLD</b>
    </div>
    <iframe/>
</body>

into formatted text like this:

?xml
body
    div
        input
        label
        a
            i
        b
    iframe

Rules

The main element does not get a indent, every layer deeper does get an extra indent. An indent is either a tab or 4 spaces.

When there are multiple root elements, they simply are added below eachother with no indentation. The ?xml element is not different from any other element.

The XML will have a space after each element name, so if there is a CDATA element, it will be formatted as <![CDATA[ (the data)]]> and will need to be formatted as ![CDATA[ at the correct indentation.

Also, the XML will not include > and < except for opening and closing elements.

Answer 7

Build a learning 20Q bot

Twenty Questions is a verbal game where an 'asker' asks you a series of yes or no questions about an object that you're thinking of. If the 'asker' gets the object correct after twenty questions, then the 'asker' wins the game. If the asker does not guess the question right after 20 questions, then the 'thinker' wins.

Input:

Your program needs to take 4 different inputs, non simultaneously. Those three inputs are:

• A category (valid categories are Animal, Food, Action, Person/Character, Thing)
• A yes / no input from the user to answer the questions.
• A question input to 'teach the bot', and an object input to show the bot what was being described.

Output:

Your program needs to play a game of 20 questions, wherein it follows this structure:

• Ask a category like so: "Select a category (Animal, Food, Action, Person/Character, Thing):"
• Ask questions based on the category.
• Make a guess of the object like so: "Is it a "[guess]"?".
• IF the guess was wrong, ask what the object was, and inquire the difference between the guess and the object described.
• your program must stop at 20 questions and make a guess. it doesn't have to be random.
• your program must progressively 'learn' as it is played. It must be able to add new questions and objects to guess.

Examples:

⇨Select a category (Animal, Food, Action, Person/Character, Thing):  
⇦Food  
⇨Is it  ?  
⇦No  
⇨What is it?  
⇦Marmite  
⇨What is the difference between  and Marmite?   
⇦It has a saying 'You either love it or hate it'  
⇨  
⇨Select a category (Animal, Food, Action, Person/Character, Thing):  
⇦Food  
⇨Does It has a saying 'You either love it or hate it'?   
⇦No  
⇨Is it Marmite?  
⇦No  
⇨What is it?  
⇦A Carrot  
⇨What is the difference between Marmite and A Carrot?  
⇦It has lots of vitamin C   
⇨  
⇨Select a category (Animal, Food, Action, Person/Character, Thing):  
⇦Food  
⇨Does It has a saying 'You either love it or hate it'?   
⇦No  
⇨Does it It has lots of vitamin C?  
⇦Yes  
⇨Is it a Carrot?  
⇦No  
⇨What is it?  
⇦A Yam  
⇨ What's the difference between a Carrot and A Yam?  
⇦It grows underground.  
⇨  
⇨Select a category (Animal, Food, Action, Person/Character, Thing):  
⇦Food  
⇨Does It has a saying 'You either love it or hate it'?   
Yes  
⇨Is it Marmite?  
Yes  
⇨Yay, I Win!  
⇨  
⇨Select a category (Animal, Food, Action, Person/Character, Thing): 

Etc.

Answer 8

Produce a quine of length n

Write a program that, given a number n, produces a quine in your language of length n. If your language cannot have a quine of that length, it does not need to be generated.

Standard loopholes are forbidden.

The quines that are generated must be proper quines.

Remember, this is code-golf, so the code with the smallest number of bytes wins.

code-golf quine

Answer 9

Rearrange the Words!

Given a string of text containing some words, which are separated by spaces, determine the best arrangement to fit it in the shortest number of pages.

If a word is shorter than the length of a page:

• If the word fits on the latest page, it stays on that page
• If the word does not fit, it goes to the next page.

If a word is longer than the length of a page, it stays on that page and overflows to the next page.

Words have one character between them if they are on the same page.

For example, if the length of the page was 10, and my words are hello my name is oliver ni!!, it would fit like this:

hello my
name is
oliver
ni!!       # 4 pages

However, one of the ways to rearrange it can get a shorter number of pages:

hello name
oliver is
my ni!!    # 3 pages

So the shortest way in this case would be 3 pages.

Remember, this is code-golf, so the code with the fewest bytes wins.

Answer 10

Change the type of a variable without introducing any new identifiers while preserving a value resulting from the conversion of the original one

Consider the variable which type you should change is declared/defined inside a function. Another thing to consider is that there wouldn't be any other identifiers manually defined/included before your function and the variable inside it (this includes referring to standard header/modules too). Also you aren't allowed to change the value or meaning of any existing identifiers (if any) except a after your code is finished, compared to before it started executing. (Of-course this doesn't forbids you to actually change them but after your code is finished they must be in the same state as before it was entered in, except a of-course)

As identifiers I mean reserved names of functions, variables and etc.

Example in C:

void f() //no identifiers defined/included prior
    //the function can't have any parameters

{ //inside function block

    int a = 67; //assign some constant value here

    //... your code here

    //no new identifiers introduced
    //and no existing one have changed meaning (or value) after this point
    //except 'a' of-course

    a ; //here 'a' must have different static type
        //with a value resulting from the conversion
        //of the one stored previously in 'a'


    //You are allowed to include libraries/modules (identifiers) here in
    //order to show us the value and type of 'a'
    //The unused statement above is used only as valid syntax containing 'a'
}

Of-course the above snippet is just a sample. In case of using actually C you are allowed to add all other kind of stuff (like additional block scopes, etc). The only important thing to target is that after you have declared some variable in your function you have to write some magic with the requirements given.

This question have intended solution in C. I'm not sure how applicable is it for other languages though because it depends on the concept of having some names (identifiers) referring to certain entities. Also it needs types and object values defined too.

The initial and target type of a aren't specified. Also if the identifier a of the variable is not allowed, you can use one that is.

Answer 11

Pluralize Words code-golf

(DISCLAIMER: In this challenge, several exceptions and rules are not accounted for. Many plurals are based on sound and not spelling, and still others have no set guidelines. Please do not use this as an actual set of rules for making plurals.)

A lot of questions here require using different Algebras. ... Algebra? Algebrae?

OK, that's it. We're going to get to the bottom of this.

Your challenge is to write a program that accepts a word as input and outputs the plural (in standard English rules).

Rules on making plurals

• Words ending in s, x, z, ch, sh, o, ex, or ix have es added to them. (For example, box -> boxes)
• Words ending in y preceded by a consonant have the y removed and ies added to the end. For example, cherry -> cherries. (Words like day with a vowel before the y are treated as normal.)
• Words ending in f or fe are treated as normal.
• Words ending in us have the ending changed to i. (For example, alumnus -> alumni)
• Words ending in is have the ending changed to es. (For example, oasis -> oases)
• Words ending in um are changed to a. (For example, medium -> media)
• Words ending in a are changed to ae. (For example, antenna -> antennae)
• All other words have s added to the end.

Several rules have been omitted for simplicity:

• You do not have to account for irregular plurals like sheep. If sheep was inputted, you would return sheeps.
• The o/f/fe/ex/ix rules have lots of exceptions. knives, matrices, etc. I can't find any pattern, however, so these are simplified to one rule.
• chateau -> chateaux, man -> men, child -> children, foot -> feet, and mouse -> mice have been left out due to ambiguity. You can replace these with chateaus, mans, childs, foots, and mouses, respectively.

• Words are counted based on spelling, not sound. TimmyD mentioned in the Sandbox:

  For example, Czech (as in, a person from the Czech Republic) goes to Czechs ("checks") since the ch is pronounced like ck.

  Here you would output Czeches (as it is spelled with a ch).

Input

A single word, like challenge. The input will only contain letters a-z.

Output

The pluralized word, based on the rules above, like challenges. You may have a trailing newline.

Output may be case-insensitive.

Test Cases

algebra
algebrae

shoe
shoes

fax
faxes

datum
data

bunny
bunnies

qlwlsh
qlwlshes

Meta Questions

UPDATE: I've answered these questions myself. Do you guys think it's ready for posting?

• Is this a duplicate? (No, other similar challenges have different scoring)
• Are there any special cases I left out? (Probably but they'd over-complicate things)
• When researching this I discovered there are a LOT of little rules. I've omitted some here, but is this too complex to be a feasible challenge? (No)
  • In addition, have I left out too many rules? (Adding any more would make it too complex)

Answer 12

Find the Mersenne Twister seed fastest-code

Given a sequence of N 32-bit unsigned integers, find a 32-bit seed for the Mersenne Twister PRNG (specifically, MT19337) such that the first N 32-bit unsigned integers produced are the input sequence.

Rules

• Solutions will be tested and timed on a free Cloud9 workspace (512 MB RAM, 1 8-core CPU). Full CPU specifications can be found in this Gist.
• There will be 50 sequences used to time solutions, each containing at least 20 and at most 50 integers. All sequences will be generated using CPython 3.4's MT19337 implementation (the source code can be found here).
• Brute force (by way of iterating through all possible seeds) is not allowed, as it would take an obscene amount of time to run all 50 timing cases with such a solution.
• Hard-coding seeds is not allowed, as it undermines the point of this challenge.
• I reserve the right to change the timing sequences to different sequences of similar complexity if needed, such as in the event that two seeds are found for the same sequence.
• Please include instructions on how to run your solution, including installation instructions for any software that is not included with a standard Ubuntu installation.

Test Cases

Note that the seeds given may not be the only seeds which produce the given sequence (if other seeds are found, please let me know). These smaller test cases are provided for verification purposes only, and will not be used for scoring.

[859552199, 418371998] -> 765976290
[3575669016, 3345750943, 1425199743, 3641622143, 468413882, 1201820413, 440223465, 4032367274, 1303769163] -> 3089232394
[3301913871, 2465802243, 3612732284, 2327984155, 3125193467, 1186355054, 3586515345, 1676699096] -> 3317482306
[1187719129, 4252341260, 3652285377, 2546267472, 259146681, 3132024105] -> 618872552
[567043356, 3386297553, 3291980436] -> 2064328469
[2371812852] -> 3402334589
[2169144927, 1612138200, 2367065602, 3106703576, 3360699020, 2044583150] -> 1508970517
[4264152408, 93510901, 2140553491, 2298459244, 3988997159] -> 3805008435
[815695699, 3390998580, 1837233431, 35472600] -> 1298560578
[2785297506, 692193253, 1505379580, 2810620241, 2299478120, 233996693] -> 1856467397

Timing Cases

These are the 50 sequences, along with the respective seeds that produced them, that will be used for scoring solutions. Once again, if any other seeds are found that produce the given sequence, please let me know.

[3626764237, 1654615998, 3255389356, 3823568514, 1806341205, 173879092, 1112038970, 4146640122, 2195908194, 2087043557, 1739178872, 3943786419, 3366389305, 3564191072, 1302718217, 4156669319, 2046968324, 1537810351, 2505606783, 3829653368, 3900315155, 938204377, 2167613558, 598176026, 1210484339, 600203567, 3246154361, 407295012, 2655874620, 3433407905, 1075916535, 4240245955, 3907330410, 2287343378, 4221031477, 3028691745, 3479856542, 2585149702, 3874773259, 631194409, 1332073689, 424185324, 3134603515, 316721330] -> 0
[3393124633, 2450474977, 1966463085, 3673681320, 1729202683, 1167867720, 325264180, 3917283871, 100160351, 791524511, 2930202830, 3113143968, 1502082504, 1809749915, 418618347, 1516663034, 578608165, 3127414055, 3472262548, 308161377, 135281507, 4131277967, 3953099834, 1042116387, 1985078128, 1789355090, 2975834429, 2756451880, 1853842973] -> 80552670
[3501423986, 1904817736, 3722254077, 4209805889, 624241735, 3072497443, 3348948634, 948724253, 2775088165, 653145320, 699931897, 2271688288, 965327734, 3611254581, 4021716510, 3489649715, 590896686, 2492882151, 2449284001, 1709766651, 2373030892, 1906330141, 3281376004, 542155191, 654946082, 3866707349, 675539429, 3153689518, 2192976919, 2369760520, 1789539597] -> 123863960
[161627675, 758641073, 3882484966, 1142624247, 4128058828, 2063104815, 1532506610, 4133456839, 2543581728, 18178196, 2276191025, 6278001, 3128406689, 2146406812, 39141315, 1050571803, 2511216100, 2411368419, 3269811767, 815334548, 3812711899] -> 178693462
[1006603821, 2040840228, 2217261808, 3301867033, 3944952417, 1692780898, 40334807, 2573488161, 1195239502, 1063781197, 758636410, 1944506134, 1022411961, 3709537934, 175021745, 3183030828, 1196557078, 11946672, 1551403327, 4143434962, 3283348277, 1825370082, 2293735756, 429108850, 745523037] -> 227497455
[2252079699, 1086590868, 525211993, 209343944, 1861419840, 2057307759, 2083384643, 2590024292, 4135416707, 3508386594, 1358765199, 3089076939, 3719484781, 516962076, 4107295833, 723033883, 1857756581, 434940583, 919038598, 2441529245, 1687894943, 13982251, 1940221612, 220848786, 1518435648] -> 260282679
[1821793358, 3054510267, 1906284293, 3380915352, 2593544407, 3915598365, 216223976, 4179796969, 2252681786, 35956624, 2373486206, 877849443, 3555235079, 3667331109, 2387597923, 2892840935, 1697182374, 4016309999, 3498537950, 2841634562, 3522184350, 1705717875, 4162597164, 2056807023, 2211204973, 3267303967, 3919558114] -> 325889376
[1201670212, 746140380, 1320204973, 751872422, 3310421711, 1963946901, 625374447, 2435010607, 3055683554, 3426449636, 4008426547, 337682689, 4056318014, 2315028303, 3896431367, 3153777187, 595649858, 3945299365, 113301178, 437820390, 2219035549, 284287245, 3156511236, 3954981533, 599197497, 3946167954, 3728124202, 733618224, 2033404503, 2973733622, 2705618778, 3966553008, 4036118888] -> 389267947
[1910148876, 4015517082, 1214608849, 988091919, 2525094197, 81939600, 3978887728, 2847303411, 66064807, 3605598571, 819502713, 233898591, 1970756897, 2621444751, 213250142, 3439913424, 1332746382, 4063692407, 869169264, 660008864, 2526902458, 3155477426, 1686496804, 3877857092, 4248058769, 2220603751, 465407251, 3418337662, 362811108] -> 424148743
[2663034465, 347641133, 1266329350, 494434286, 24416336, 1697535896, 233051569, 1134030615, 821790629, 1645020605, 2310228737, 63596966, 3832219398, 465243130, 4070794284, 1062758865, 2070536142, 2272514237, 440192702, 3490367376, 3000125608, 1175130963, 339129292, 1200804986, 3560746354, 1043913893, 489469329, 3588157041, 415367051, 1506938118, 519839008, 3921307375, 1017013313] -> 481818733
[2125426152, 580419999, 1942656966, 733532664, 1002041383, 4276401064, 3164003602, 1600445806, 87486541, 585241213, 1822489492, 3670405099, 2371866217, 293071217, 1698095716, 2860716495, 4096732631, 860271933, 1698519068, 1453446230, 2296564613, 1034887983, 3124580892, 3613882243, 3142206150, 1201496338, 262241539, 2658580629, 75299337, 1543495990, 1079614000, 1988996951, 1393947112, 3686457188] -> 503218192
[849928291, 3109119200, 641398141, 953565598, 1651963094, 2973763708, 2409024299, 2638872282, 3438675501, 2024561790, 2574711112, 2224233243, 2145875524, 2483785498, 832036542, 2756591965, 804169437, 1610259885, 1727659540, 3804671151, 2651460465, 3679117113, 3392652401, 4291100134, 3315401681, 4150630548, 3255282492, 1793428708, 4213220288, 1275054855, 3395683809, 126422719, 747072718] -> 529806420
[3795382423, 2318193600, 2941259533, 1429473204, 3841712189, 908410440, 2163447895, 2266401416, 1962272288, 2172290597, 903602965, 2493475709, 1557270830, 1269693466, 1882416966, 1675172531, 2727910931, 67882201, 982110502, 922191612, 1147478737, 1527639226, 1162436584, 3427111171, 1012039523, 775426178, 2235111095, 838473449, 3547292154, 2331447259, 2482093779, 3522096001, 978885775, 911597256, 4199754157, 884328339, 3958245046, 3701693539, 2205845644, 737996384] -> 594670421
[2281257517, 3184614238, 760843542, 2349085191, 3946149756, 3843515781, 357391440, 280771960, 1523563345, 1988608601, 3428233753, 100999796, 1858706576, 3053822297, 2013347998, 2869736987, 3049191880, 2683304507, 2165662057, 1644801829, 3174344328, 516799881, 2817748912, 680940874, 60488796, 440310808, 4238771580, 3333869324, 3437732706, 2291819087, 2904810286, 643100619, 2444662123, 2814934785, 3198564042, 3050641347, 2644737611, 1044358220, 2729428974, 2696207835, 1949284287, 2602160488, 4077269219, 843097934] -> 608761482
[2459044101, 3628291690, 21901316, 1607776779, 574126446, 2632595613, 1898457307, 1993218217, 2268071755, 2262630078, 1334308000, 2756814507, 1322265974, 493521136, 3513003023, 1998755513, 501729387, 461623974, 2703701229, 3074392802, 2895338933, 1257991758, 1147599903, 2188879650, 2802233695, 1049885503, 67969151, 3855902849, 1481701505, 2592817148, 3215907335, 3924969407, 91996333, 857125517, 3408363147, 4006870634, 998389513, 1316925910, 1621658875, 2583060764, 3809067813, 4122609293, 3970592027, 529557207, 1717219729, 2504378950, 418151974, 1944676036, 4136632810, 2747386509] -> 672575322
[58833619, 2580439730, 3693390914, 2286941505, 2380251005, 860188183, 1775128121, 1286129564, 1885665593, 2208299577, 4157266729, 3426550994, 3918528183, 4277973044, 3399609402, 1027156209, 2127983039, 4014806283, 1680366681, 2338809246, 2450101289, 2369487851, 2470761981, 4146252501] -> 758102662
[1228778451, 3161629785, 956090791, 2661866534, 3797423759, 387813121, 686718911, 1671912681, 3122216050, 3708361254, 2450007821, 562470295, 2371567740, 594715145, 1539207036, 1044745741, 3799733486, 3957279143, 3072889407, 43156136, 564713293, 3478075046, 3706967146, 3687044887, 992776898, 3807405066] -> 829276193
[4181681092, 472808862, 2820379353, 1971138909, 957029949, 383690688, 1619203644, 40060279, 799380031, 2522476881, 3052161194, 1101783645, 550394884, 1003243703, 1139176364, 637909704, 1746995412, 3569010375, 2962331845, 1221693446, 1622613434, 2503259347, 1956882342, 3173044265, 1239439145, 842693462, 2538205226, 2451274505, 4212820092, 3591867315, 1233020299, 978021001, 3148810648, 1811827712, 2638973530, 815364991, 1169900461, 1109925685, 856009157, 3254416301, 2037813477, 3945026418, 1535198958, 4259784019, 573350683, 1682977388, 1817703645, 2576589136] -> 898248134
[3182465441, 38281954, 424174823, 2654611156, 2877159272, 723093605, 1443837986, 3392781854, 2463922103, 4286449851, 538962217, 2130457280, 2178815165, 3486677232, 4058242555, 491907811, 162839736, 1759357975, 870141283, 1495756753, 1216746993, 1937724479, 1514235325, 4184006461, 3436845854, 2401877503, 610797147] -> 913459250
[1149034119, 2642531102, 1662163608, 3290983280, 819699523, 515983953, 2696922239, 2166479741, 1179733281, 2022256392, 1626594590, 543353369, 3692263091, 2392093428, 4014491227, 1041518429, 1713650051, 3538550903, 3376348599, 4277108217, 2867735513, 82177527, 10764183, 2126826329, 1028783725, 2271873691, 213268477, 2609718986, 3495904404, 913207638, 1265558725, 2980124058, 303469040, 253105205, 495410356] -> 931867201
[1077541173, 465200833, 3196368211, 1288748206, 2815478016, 1065298665, 2884065004, 392702413, 3587996620, 2894220485, 3226548573, 145951050, 956741233, 2456765795, 3978933657, 1007424556, 2169150234, 3651822773, 1565891297, 510586439, 2219790712, 422126653, 1640535295, 2992880885, 3691821384, 1555208492, 2642710071, 2625348100, 578265950, 592730275, 2092195932, 2504727970, 2149376041, 3179917702, 141987426, 2680075044, 656985656, 2153196909, 4149347932, 2216899428, 2639954700, 3190665042, 2786390314, 2974431514, 1505784370, 3602363995, 1699665616, 327189341, 335160466] -> 945442081
[1284631810, 3717268552, 2270237312, 1334241593, 1477854231, 3138477902, 3837857694, 3586498067, 1959233909, 3891506078, 2756512687, 2553842301, 964459746, 1395510385, 1185295577, 3096625618, 3145085801, 2953203657, 412902939, 3850708910, 2893328412, 2046860068, 86811187, 1188173782, 1294786028, 3044338056, 1040690464, 2128428491, 2571424043, 467837042, 3752155615, 4020048256, 3119445970, 2240289832, 1491368301, 3651270856, 2456196179, 378459336, 188104463, 777143930, 1824526143, 4060407078, 3866701738] -> 1005490735
[329511653, 2198540059, 2154958918, 378488687, 1460553211, 2529097663, 2295211009, 68583162, 1430570391, 1601101442, 1075009348, 2795773614, 833830658, 903181786, 633114581, 3292534356, 3245176784, 2582500259, 3943169203, 1130082435, 3079387854, 3150805871, 1721482617, 2291158702, 3225790458, 1468813727, 862011357, 4268175908, 3661137987, 464141661, 3956758980, 353701536, 1341361227, 809582799, 3968372465, 4111098095, 2898048807, 1509470117, 3255194829, 1330296075, 3520527115, 3736908846, 168999059] -> 1056211089
[1981947965, 3374825360, 3953254353, 1846368367, 1512467473, 3858309918, 4274851313, 787575622, 1876080592, 73919936, 3951066372, 730226758, 3289279637, 768907525, 1773361296, 821210337, 823248190, 869737395, 1360958003, 37854528, 426098214, 2732039516, 64754302, 3276807872, 3816769165, 991587659, 2262236344, 2500333010, 544193426, 1576372318, 2228843007, 2361635236, 2149913894, 3651360213, 2399010654, 4269441712, 1500948518, 3962883634, 1885037482, 2608182179, 3516218188, 513897987, 4242749462, 3892663321, 3922003874, 2123606394, 1383207752, 2867973529, 3840556114, 2969243741] -> 1071722183
[2514263486, 742731713, 3234620175, 3101660088, 2571087369, 3985627296, 3534135449, 2957356517, 2720311929, 2985074784, 2621199558, 3407431088, 2711831197, 1247421057, 3794320157, 1180925811, 1569942151, 2629267152, 173488457, 1406704148, 3969219352, 291552269, 1333806964, 2203738485, 1554560925, 496218017, 1379546509, 2539796280, 4118468566, 2328295795, 884528669, 123600717, 1597383076] -> 1093875318
[1521547521, 982639096, 3108583938, 3860926389, 1477036165, 2087376039, 953332718, 1432039007, 836148138, 3081500185, 396473811, 1621365414, 3796659618, 3939606659, 4248871833, 2917576264, 2729341943, 2981171481, 2311970081, 150264587, 2215220955, 995666639, 452785817, 758560294, 2134005122, 39617150, 1283053470, 4198921194, 2492185018, 595457083, 1042642207, 545670342, 4068770955, 749869737, 984770127, 663196981, 1849907933, 1443537561, 3860175505, 1016163998, 3260982442, 3769639327, 2728953690, 1556597597, 1877966580] -> 1155984918
[1198705327, 1935517658, 503589232, 1577874702, 627636752, 3338218922, 1157893341, 3491377096, 158028724, 2472091015, 1488124620, 2401465711, 3064309912, 1501000204, 3549612642, 2584717560, 1744885213, 4114571438, 1885581118, 2912594621, 3206412254, 4218195409, 2855464167, 2517461088, 685010709, 2000660923, 3562767265, 1193468772, 1470300123, 819551295, 2007863203, 980161306, 717575858, 2022655390, 1011703442, 1190149434, 182438707, 4158211886, 2175561856, 3060913999, 1239412823, 2397907962, 3942897187, 2435381198, 4007365042, 1591831562, 1664232451] -> 1198085477
[3487615865, 4016084043, 1447817513, 2774535999, 1987172957, 3906060658, 3082008686, 88752056, 1947416015, 3376238098, 3503927625, 342228658, 2709452172, 1070052314, 3791872618, 1290870698, 587900606, 1133043554, 671196454, 3876594873, 526665632, 165876551, 3122917378, 4053700531, 1298948490, 1351144611, 563691115, 322287271, 2461185743, 3663527460, 4222266716, 3553092834, 4168116886, 1291668088, 2033147092, 17653398, 3675413239, 2758765766, 2242336270, 734645239] -> 1234710497
[4199109099, 1728109096, 1057011054, 312030739, 490158329, 2571270959, 1337574406, 3037342898, 2943362559, 468588625, 1215641907, 891368463, 3446982561, 146537280, 1406572684, 1996341215, 1239450385, 3239123491, 2654855274, 584040319, 664433665, 3282777560, 3498456462, 398718226, 3318895203, 4109932784, 435092929, 3761442422] -> 1281039914
[330441100, 3682376585, 1548511518, 1012361554, 1641750013, 1347050521, 2746331107, 363031882, 3664742187, 263887825, 3045968855, 4047861721, 4201376344, 2013802400, 43925321, 2057073856, 974221675, 1240944962, 3823005386, 3154676709, 1649841356, 3211264096, 355417272, 2640980835, 2706339938, 987877841, 110633642, 4200784138, 3756125284, 471091914, 3370617977] -> 1307906352
[3242988428, 4255969082, 867271806, 415292052, 3609803438, 416630352, 3232953772, 4269951801, 350204559, 4181264343, 2332795572, 2668659134, 2628956236, 3596517643, 2454368561, 1369266677, 3672701863, 388613580, 1479812495, 2141142524, 2486572053, 2320908196, 393062185, 1938229604, 231136143, 1626064567, 1493467817, 1983339349, 894785483, 44315897, 1514887732, 1864793575, 3953707615, 3492718672, 3522516821, 289358385, 2227856486, 256540739, 4213343606, 200728817, 3396994332, 3845507785, 220892851] -> 1358830177
[3696325595, 95369954, 135918350, 487636311, 825705453, 3049392697, 841126004, 1979734631, 507462131, 1964376824, 3031319264, 3487421046, 2192402845, 3792297163, 3808487536, 1516405605, 664293073, 613658148, 4063050354, 1921745034, 2258497732, 3473698642, 3256102715, 1916456581, 1185919167, 3315712023, 2955859300, 1784025278, 2641317925] -> 1394873382
[2775177776, 3943074566, 1008831348, 423577731, 2936039382, 3419907541, 3346657170, 1767888023, 2549910502, 1510292917, 609091982, 3619041655, 1071140841, 4210891014, 4197129534, 4002247218, 1785145415, 773140313, 850187206, 3695148850, 1699963321, 2029501148, 2273345989, 2045294772, 2490424114, 3670522622, 1903814852, 2845243988, 547217989, 814736327, 1178316093, 3421797242, 583834194, 560861293, 1728122240, 1143281622] -> 1418337751
[3909221229, 1543378013, 3578599386, 1821301593, 382025872, 3090149061, 2799832135, 2969167740, 3214053618, 2459088339, 61851869, 2988154510, 3405155263, 1143312722, 3055626916, 1306722473, 2424970867, 3838250998, 2541260784, 3634562987, 91009990, 228167376, 144739158, 69758376, 1416179539, 175832649, 1058618668, 3141319060, 2603813691, 3448922532, 3563483339, 2187253777, 3939459963, 729053170, 348198400, 2818894106, 4163690148, 4269596985, 1550179869, 2888474224, 977138852, 2267335031, 1039633247, 331897176, 3493431132] -> 1440945260
[548460784, 2008846553, 4095226690, 2537987040, 1412322911, 295388541, 388770296, 2073124976, 4254588769, 2032785043, 3714052855, 653890260, 3378524009, 4169809326, 1850329785, 2009334592, 2701527530, 260935905, 1081271463, 3349408130, 187425716, 588199859, 1037983019, 3586620795, 4254384458, 3345512384, 1424865889, 1577623131, 3897199153, 2727265103, 3204931862, 4089210973, 1909632078, 3588030047, 1946727191, 502364265, 2290334448, 2873594561, 1542446006, 3459132329, 4292608386, 3741690622, 165647068, 1253913368, 1993997790, 2812680991, 2352267270] -> 1500826128
[888893887, 2614777345, 2033163377, 4036989271, 3569896418, 1268962278, 1146226964, 107044610, 2147272927, 3436615686, 1202308143, 1325516848, 2994121867, 973196789, 3793281340, 3099942299, 2472036270, 1798140896, 2858254867, 2204354371, 3472459738, 826142039, 4066377434, 2519409484, 1777413266, 3493671143, 551412865, 886786197, 3882384707, 1172607108, 636563066, 190968362, 3994307050, 3757375918, 2755608252] -> 1566530912
[2820693508, 1716694240, 2268887698, 1296436510, 2916995305, 3041798596, 3096982293, 177546898, 3065170162, 933607211, 102294817, 1801218436, 102569645, 2901869379, 2714886480, 119387632, 656198271, 1388322584, 2775933520, 255861774, 653410879, 121504271, 3607745288, 2230556561, 2594802791, 1189055855, 1111240008, 2530579856, 936965766, 3263165681, 1646076782, 3215192313, 2313499990, 1836078863, 76222274, 3537625615, 3448299995, 1142686967, 2783169043, 1481999457, 407759227] -> 1596242054
[2829936706, 3129475899, 3747369794, 3436426639, 2221019177, 2711897885, 2281503984, 3142203725, 1105679393, 2240453588, 21256724, 1976207648, 2233823367, 3867572431, 883054004, 3828587385, 55294132, 3869553795, 815613304, 1561650320, 1751491302, 3021430621, 3344018026, 1092797427, 2270330908, 872186202, 1096541534, 2148792176, 3302750004, 1221765447, 2805795772, 779878772, 758662454, 4154291008, 1400703216, 2661407119, 3653090591, 674866675, 688479370, 757212805, 2546987102, 3742892714] -> 1598478846
[1350161655, 3410944815, 579310510, 2035583578, 2536805685, 2120035014, 3911683567, 137430281, 676637211, 80424819, 2031627279, 1805522976, 2901778769, 2558787384, 2175054, 1588147737, 1750628274, 1642903038, 2323086809, 204561611, 3017703970, 66172789, 3753895397, 1082808709, 343477515, 3245691790, 2098802152, 2796851615, 3416307802, 1023857834, 1965832789, 412854529, 354175981, 3277463158, 2311727857, 3748028931, 75711999, 605941926, 4268457500, 1591192393, 2493456550, 1285360546, 160198834, 3576865205, 188890618, 1853564214, 4281264410] -> 1682874144
[1759970266, 4134439683, 1532925684, 269299343, 4192017837, 3267142052, 2227585380, 917508171, 2947539107, 1298614074, 3027970270, 3512964090, 78445334, 3939961135, 1550341966, 891964846, 882505655, 314334452, 536698283, 4073297092, 1362911951, 10583051, 4102282272, 39722618, 817646395, 635913246, 3395599638, 114835278, 2721016640, 1301397743, 3359042468, 1967603896, 1842991024, 797964890, 4075738194, 1833629245, 222121931, 3323140076, 3669797521, 2149358182, 3096189598, 4128620833, 1053919363, 3716968416, 1538927892, 3456625069, 3320651259, 2424645618, 3487090498, 1836457156] -> 1757912108
[3206311438, 3995119122, 875115076, 1697246932, 1819127701, 3119338948, 4287411440, 398614242, 2014590172, 1247230330, 4290547991, 2948954546, 3744789096, 2104418209, 185774855, 4253667876, 2202426919, 3397365003, 2934331500, 2095666656, 996668853, 249650538, 3668868008, 1615410768, 492066747, 3451532273, 3886898259, 1151021320, 1782145434, 2431016438, 2907780443, 2152384331, 800661361, 2028554209, 1103300513] -> 1779025760
[1744880977, 2233651387, 56617556, 1115479166, 2611598968, 1306003390, 2910946867, 1496609711, 4077408131, 3512362374, 2281393975, 3418144659, 1773074316, 1601343734, 807592751, 2365582522, 1446242874, 847706414, 2850851126, 414921605, 2617956981, 4205647553, 4063233713, 142946783, 1975643220, 1993142296, 3392343515, 1515671667, 1948071803, 3991728328, 968499177, 2198785340, 1321024334, 3781705466, 3920003634, 727611412, 30865083, 1239101335, 3511359132, 3435471655, 2332994209, 3451243757, 2388153527, 3219135587, 3239646757, 130935018] -> 1815085532
[3742736007, 3013982958, 950712805, 590882231, 2021027712, 1687735825, 2840162788, 236595715, 1966708028, 3189262610, 1430349774, 533579944, 2649611396, 2583295302, 3582250057, 2565346361, 396439695, 4153603028, 3342863641, 209226977, 3673492099, 1470755570, 1265241721, 755285979, 1871568539, 1835865540, 614068679, 1981443993, 570207739, 4057872936, 636526617, 3083893122] -> 1892006865
[2363102448, 2664740190, 3782032362, 2321087205, 3789479744, 439476800, 267092854, 559662253, 3052920007, 1039904017, 882951865, 1185772050, 121779049, 1255320891, 3898061704, 4160716348, 1870139159, 1739210570, 2851269822, 866317206, 559870442, 3322246740, 419503690, 1438071640] -> 1972485478
[3678708758, 283072981, 1128708041, 648928081, 516617525, 2562088844, 2077772312, 454404108, 2773100394, 3731939823, 3956390266, 1273038228, 711119494, 1889950256, 2150587570, 2368988611, 3083613740, 136402153, 3706807002, 1951409673, 646402003, 1965112544, 3799779787, 2727912100, 3934407652, 3190480389, 2893737274, 3503914114, 1242998415, 3673986521, 3585553888, 1356707071, 2892703448, 2503698089, 677538230, 3777556915, 4131625633, 3989648217, 3371399362, 916533795, 438016809, 1888923541, 4018783570, 35576878, 1439895305] -> 2006012423
[4186976930, 1468422130, 2127537262, 3013431126, 1014175853, 619237775, 2251537150, 2635437352, 2529830434, 270079805, 2249885826, 4160741826, 1799997550, 90064691, 1707888518, 4191506978, 1400211336, 4260528976, 1777462871, 3522395605, 3184921911, 1289756682, 1204481339, 2320228865, 1382458891, 2585094069, 1807393027, 904952345, 2418050161, 3944759600, 850396791, 2010841661, 911793010, 2814160212, 3917390566, 1742258451, 312330630, 1509247515, 3622596041, 2381664940, 792997581, 1348701222, 4231392479, 1492858603, 841395446, 1732373831, 2792829070, 1232839054, 4133086979, 1330710519] -> 2023628655
[1447486536, 1589601829, 2711407664, 2671174482, 755815460, 2739822893, 624189525, 3881531582, 2104935742, 3877151275, 4029158122, 3270473853, 2397135808, 541842801, 4159848352, 1265295340, 2924665155, 1697146316, 1323336501, 1887970585, 3957105141, 4080944661, 1260974434, 2538893190, 1418098060, 1087907449, 1555085135, 517760467, 1165667983, 1976195378, 899913113, 3298189181, 2844731428, 2587250768, 419676280, 3669952139, 1008835697, 2109855126, 2204851528] -> 2080799654
[3057502862, 2753037643, 586428454, 875470641, 763920856, 1915854920, 960628797, 3268824212, 155894276, 326435370, 4153187586, 3266725420, 3421441761, 984314678, 134133671, 1571569456, 3290768531, 1270814441, 3360280927, 63041059, 1367587866, 3837387650, 3016828154, 1932299196, 2677431226, 118282642, 4274320011, 2842715068, 3590275349, 3385213492, 3669399717, 23889551, 1990874337, 2065027029] -> 2124973901
[404963327, 970175530, 2315604326, 759401990, 3265128006, 3886300253, 2428903513, 2547895316, 2394147688, 1256335272, 54823458, 1121206884, 1587348808, 1813532729, 475467047, 2240315018, 4228484438, 3836003837, 1713780997, 1021495744, 1667817101, 3431813061, 1741019894, 244489142, 4185223756, 2154392407, 1130398867, 2200660986, 1655353090, 824162463, 269754245, 853115597, 554916755, 3901389184, 3490586038, 2387525212, 3363338561, 2848158299, 1365520662, 65222054, 969608783, 3832404018, 797302386, 220365549, 998915816, 3880644358, 1656707899, 113713704] -> 2200030708
[1182658594, 858230724, 1872357797, 2818651205, 2361035630, 2882362708, 774158555, 1780906106, 1245895866, 1925774739, 1695790856, 1650553385, 3918997115, 1289270838, 1080124671, 1854179057, 4032572199, 3398178415, 2660852575, 2126762197, 2845072225, 3916118969, 2961311910, 3490728772, 2152765282, 925727050, 2046977563, 3481846724, 3016398740, 3170193754, 3947157907, 2318811664, 665856332, 2694492251] -> 2222600201

Answer 13

Implement the Terducodec

In this challenge we'll be implementing a tersum duplicate coder/decoder; aka, a terducodec. This is a reciprocal substitution cipher, so the encoder and the decoder are the same.

Definition

The tersum duplicate of a number x is 2x using base 3 without carries. Alternately phrased, the tersum duplicate of x in base 3 is simply x in base 3 with the 1 and 2 digits swapped.

For example, the tersum duplicate of 47 is 64, because 47=1202b3, and 2101b3 is 64. Note that since this is simply a result of swapping base 3 digits, the tersum duplicate operation is its own inverse.

Terducoding

We code at an octet level, using values in the range 0 to 255 and the tersum duplicate operation. To keep the result in the range 0 to 255 the operation is applied to each of the following subgroups:

• 0 through 242
• 243 through 251
• 252 through 254
• 255

Given n in the range 0 to 255, let s be the lowest value in the same subgroup as n. Then n can be terducoded as follows:

• Subtract s from n
• Calculate the tersum duplicate of this result
• Add s back to the above

Examples

The value 195 is in group 0 through 242. This group's s value is 0. Thus, we simply take the tersum duplicate of 195=21020b3, which is 12010b3=138.

The value 246 is in group 243 through 251. This group's s value is 243. Thus, we take the tersum duplicate of 246-243=3=10b3, which is 20b3=6, and add s back in to get 249.

The value 252 is in group 252 to 254. This group's s value is 252. Thus, we take the tersum duplicate of 252-252=0=0b3, which is just 0b3=0, and add s back to get 252.

The Challenge

Write a program or function that implements the terducodec. Your program or function should accept as input an ordered sequence of octets, and produce as output a corresponding ordered sequence of terducoded values. The input/output mechanism may use standard input and standard output, arrays, etc; however, your chosen mechanism must be able to represent any sequence of octets where each octet has the full possible range.

This is code golf. Standard loopholes disallowed. The smallest terducodec in bytes wins.

Test Case

A single test case doubles as a list of all possible encodings. Here, the decimal representation is used for each octet.

  0   2   1   6   8   7   3   5   4  18  20  19  24  26  25  21
 23  22   9  11  10  15  17  16  12  14  13  54  56  55  60  62
 61  57  59  58  72  74  73  78  80  79  75  77  76  63  65  64
 69  71  70  66  68  67  27  29  28  33  35  34  30  32  31  45
 47  46  51  53  52  48  50  49  36  38  37  42  44  43  39  41
 40 162 164 163 168 170 169 165 167 166 180 182 181 186 188 187
183 185 184 171 173 172 177 179 178 174 176 175 216 218 217 222
224 223 219 221 220 234 236 235 240 242 241 237 239 238 225 227
226 231 233 232 228 230 229 189 191 190 195 197 196 192 194 193
207 209 208 213 215 214 210 212 211 198 200 199 204 206 205 201
203 202  81  83  82  87  89  88  84  86  85  99 101 100 105 107
106 102 104 103  90  92  91  96  98  97  93  95  94 135 137 136
141 143 142 138 140 139 153 155 154 159 161 160 156 158 157 144
146 145 150 152 151 147 149 148 108 110 109 114 116 115 111 113
112 126 128 127 132 134 133 129 131 130 117 119 118 123 125 124
120 122 121 243 245 244 249 251 250 246 248 247 252 254 253 255
 ->
  0   1   2   3   4   5   6   7   8   9  10  11  12  13  14  15
 16  17  18  19  20  21  22  23  24  25  26  27  28  29  30  31
 32  33  34  35  36  37  38  39  40  41  42  43  44  45  46  47
 48  49  50  51  52  53  54  55  56  57  58  59  60  61  62  63
 64  65  66  67  68  69  70  71  72  73  74  75  76  77  78  79
 80  81  82  83  84  85  86  87  88  89  90  91  92  93  94  95
 96  97  98  99 100 101 102 103 104 105 106 107 108 109 110 111
112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127
128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143
144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159
160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175
176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191
192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207
208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223
224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239
240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255

code-golf cryptography abstract-algebra polynomials

Answer 14

Minimize Your Code's SHA-256 Hash code-challenge

Write a program or function that outputs its own SHA-256 hash as a hex digest. The winner will be the program with the smallest output (when interpreted as a hexadecimal integer).

Rules

• Accessing the program/function's source code is allowed (a la cheating quines).
• The output must be in hexadecimal, optionally padded with zeros to 64 hex digits.

Example (Python 2)

import hashlib
print hashlib.sha256(open(__file__).read()).hexdigest()

Ideone link

Output/score:

fe58e530aa530b34535cadc001383750a3343634c644539901a04659b41a7308

Answer 15

Shooting range

Print/output this exact text:

                   _
                  / \
                 / _ \
                / / \ \
               / / _ \ \
              / / / \ \ \
             / / / _ \ \ \
            / / / / \ \ \ \
           / / / / _ \ \ \ \
          / / / / / \ \ \ \ \
         / / / / / _ \ \ \ \ \
        / / / / / / \ \ \ \ \ \
       / / / / / / _ \ \ \ \ \ \
      / / / / / / / \ \ \ \ \ \ \
     / / / / / / / _ \ \ \ \ \ \ \
    / / / / / / / / \ \ \ \ \ \ \ \
   / / / / / / / / _ \ \ \ \ \ \ \ \
  / / / / / / / / / \ \ \ \ \ \ \ \ \
 / / / / / / / / / _ \ \ \ \ \ \ \ \ \
/ / / / / / / / / / \ \ \ \ \ \ \ \ \ \
| | | | | | | | | |x| | | | | | | | | |
\ \ \ \ \ \ \ \ \ \_/ / / / / / / / / /
 \ \ \ \ \ \ \ \ \ 9 / / / / / / / / /
  \ \ \ \ \ \ \ \ \_/ / / / / / / / /
   \ \ \ \ \ \ \ \ 8 / / / / / / / /
    \ \ \ \ \ \ \ \_/ / / / / / / /
     \ \ \ \ \ \ \ 7 / / / / / / /
      \ \ \ \ \ \ \_/ / / / / / /
       \ \ \ \ \ \ 6 / / / / / /
        \ \ \ \ \ \_/ / / / / /
         \ \ \ \ \ 5 / / / / /
          \ \ \ \ \_/ / / / /
           \ \ \ \ 4 / / / /
            \ \ \ \_/ / / /
             \ \ \ 3 / / /
              \ \ \_/ / /
               \ \ 2 / /
                \ \_/ /
                 \ 1 /
                  \_/

Trailing whitespace after line ends allowed, trailing/prepending newlines also are. You can write either a full program or just the function. This is code-golf, so shortest code (in bytes in your languages preferred encoding) wins.

sandbox:

• any better wording?
• anything I'm missing?

---

code-golf kolmogorov-complexity

Answer 16

Paint the Path

First shot ever on something like this...

You got stuck in snow and have to get out somehow. You only have a paper left with some letters on it signing the directions you had to go marked with NESW. To make sure to not get lost you want to make yourself a map with the pathing. You grab your laptop and start coding. After you are done you try your function/program and check if it works as intended. It does! You grab yourself thick clothing and a shovel and work yourself through the snow.

Your task

Your task is to write a program or function that takes a series of characters into your standard way of input. This might be a string, a list/array of characters/strings only consisting of the letters NESW and ouputs a map with the characters ^>V< as arrows signing where to go. Each sign has to follow directly after the one before at the correct position (>^ is correct ^> is not).

Input

You can take the input in a way of your choice as described above.
You may assume that the way will never cross.
You may assume that you will never go further North nor further West than your house is.
You may assume, that you will never have to walk back directly (eg SNWE).
You will always start in the top-left/north-west corner.

Output

The output should represent a kind of a map with the characters^>V< as movement signs. You may use spaces or dots to separate to quickly find the way.

Examples

Input: EEEE
Output: >>>>

Input: SENE
Output:

V>
>^

Input: SEESENESSENNNE
Output:

V    >              
>>V>V^              
  >^V^              
    >^ 

Input: EEESESWSSSEEENNENWNNEEE
Output:

>>>V  >>>            
   >V ^              
   V< ^<             
   V  >^             
   V  ^              
   >>>^              

Scoring

This is code-golf so the shortest answer in bytes wins!

Sandbox questions

Has there already been something like this?
Is the story redundant or acceptable?
Did I miss something? Like a requirement?
What tags should be used (except for code-golf)? I am not familiar with the tags and welcome any suggestion.

Answer 17

Self-Verifying Quine Variant quinecode-golf

We have plenty of challenges that ask you to output your program's source code, but I couldn't find any where you input your program's source code and verify it.

The challenge:

Your code is to accept some text as input, and return truthy if the input is identical to your source code, and falsy if it is not identical to your source code.

For the purposes of this challenge, your code need only verify against the actual code that you typed, not any runtime flags you used or implicit code the compiler/interpreter adds on.

Standard loopholes are disallowed, and standard quine rules apply (no reading your source code from disk).

This is code-golf, so fewest bytes wins.

Answer 18

Wordsearch programming

cops-and-robbersgrid

(Todo: example submission + format)

Your task

• Write a full program that takes no input and prints any message under 100 characters to STDOUT.
• This program must print the same message every time it is run.
• Arrange your program into a wordsearch puzzle.
• Post the wordsearch and language, along with the desired output.
• Robbers will try to reconstruct the original program.
• If they create any program that produces the desired output from the wordsearch within a week, your submission is cracked and the robber gets some points.
• If your wordsearch survives the week, you get some points.
• You must reveal what your original code was after the week for it to earn points.
• Any code snippets in the wordsearch must be at least 4 characters long.
• Whitespace doesn't count in the wordsearch puzzle (int var would become intvar in the wordsearch. The robber can choose to interpret that as int var, intvar, or even in tvar).
• Code snippets can overlap in the wordsearch as long as no code snippet is located completely inside another snippet.
• The wordsearch is case-sensitive.
• There is a cap of 25 rows or columns of the wordsearch.
• No standard loopholes.

Scoring

Safe submissions earn the cop

100/(number of cells ^ (2/3)) points

For example, a 20x20 submission would receive

100/(400^(2/3)) = 100/54.3 = 1.84 points

A 10x15 submission would receive

100/(150^(2/3)) = 100/28.2 = 3.54 points

Cracked submissions earn the robber

(number of cells ^ (2/3))/10 points

For example, a 20x20 submission would receive

(400 ^ (2/3))/10 = 54.3/10 = 5.43 points

A 10x15 submission would receive

(150 ^ (2/3))/10 = 28.2/10 = 2.82 points

Your total points are the points that you receive from all of your safe submissions plus points from cracking other submissions. The user with the most points by (date a few weeks from challenge posted) wins.

Example submission

For the example submission, let's say that the program is a simple "Hello, World!" program in java:

public class ictc{
  public static void main(String[] args){
    System.out.println("Hello World!");
  }
}

The first step to the submission would be to strip all whitespace:

publicclassA{publicstaticvoidmain(String[]args){System.out.println("HelloWorld!");}}

The submission would look something like this:

Java, 10x10 grid

publicvgra   
lut.ptotto
n[b;main(S  
(]Slatd{}y
"a{{iiints
Hrintcount 
egnirts;Se
lssalcrram    
l);}}{;;;.
o{World!"o

Output:

Hello World!

Answer 19

Determining the Dominant Bit code-golf string

Challenge

Your code, which can be a standalone program or a function, should take an input string. You can assume the string only consists of ASCII characters.

The program should then print or return 0 if the text contains more 0-bits, 1 if it contains more 1-bits or something else (see below) if the number of 0-bits and 1-bits is equal.

Details

The number of bits in a text is determined on a per-character basis: you take the ASCII code of the character (which is 0-127 in pure ASCII) and convert it to 7 bits of binary, then count the number of bits that are either set (1) or cleared (0). The occurrences of these bits are then summed over every character of the input string.

If the number of 0-bits and 1-bits is equal, the program should return or print something else than 0 or 1. This can be returning or printing a negative number, printing nothing or returning null (or similar), etc.

The input will only have a single line and will not have any trailing newlines. You will only need to support the set of printable ASCII characters (ASCII codes 32-126) in the input. If the input is empty, act as if it had an equal number of 0-bits and 1-bits.

Example

Code Golf

Convert to ASCII codes:

67 111 100 101 32 71 111 108 102

Convert the numbers to 7-bit binary:

1000011 1101111 1100100 1100101 0100000 1000111 1101111 1101100 1100110

The number of 0-bits is 28 and the number of 1-bits is 35, so 1-bit is the dominant bit. Therefore, the program should print or return 1.

Test Cases

Assuming equal number of 0-bits and 1-bits causes nothing to be printed:

Input: Code Golf
Output: 1

Input: DETERMINING THE DOMINANT BIT
Output: 0

Input: Equal Number of BITS?!
Output: 

Remember, this is code-golf, so the valid code with the fewest bytes wins. Standard loophole rules apply.

Answer 20

Piet (Mondrian)'s Puzzle code-challenge tiling optimization

For more information, watch this video.

The Mondrian Puzzle (for an integer n) is the following:

Fit non-congruent rectangles into a n*n square grid. What is the smallest difference possible between the largest and the smallest rectangle?

For 6, the optimal difference for M(6) is 5, and can be demonstrated like so:

 ___________
| |S|_______|
| | |   L   |
| |_|_______|
| |     |   |
| |_____|___|
|_|_________| (fig. I)

The largest rectangle (L) has an area of 2 * 4 = 8, and the smallest rectangle (S) has an area of 1 * 3 = 3. Therefore, the difference is 8 - 3 = 5.

Keep in mind that currently, no optimal solutions for n > 24 have been found.

Your task is to create a program that generates a Mondrian grid that contains a (non-optimal) solution, given an integer n.

You will be tested on the numbers from 100 to 150. Your score for each test will be the difference between the largest and smallest rectangle. Your total score is the sum of your scores for all the tests from 100 to 150.

You must present your output like so:

{number}
{grid}

Where number is the score (the difference between largest and smallest), and grid is either:

• A multi-lined string, or
• A two-dimensional list.

The grid MUST clearly show where a rectangle starts and ends.

Rules:

• Your program must fit within your answer.
• Your program must generate the same solution for an integer n every time the program is run.
• You must provide a link to the outputs of all 50 solutions (using Pastebin, Github Gist... anything, really).
• You must have at least two rectangles on the square grid for your solution.

Meta:

• Is this a dupe?
• What tags?
• Can I improve on my explanation?

Answer 21

Lasers & Mirrors

ah lasers. they're a modern marvel. From the most common colors of blue, red, and purple to the more exotic cyan, green, and Occasional yellow. One of the most fascinating properties of lasers is their tendency to travel in a straight line, and bounce off mirrors. What fun! Let's simulate that.

consider a square grid of arbitrary size. This grid has four elements, Mirrors, walls, spaces, and a single goal

Mirrors:

Mirrors comprise only 2 characters: / and \. each of them represents a mirror which is reflective on BOTH sides, and is angled at 45 degrees and -45 degrees respectively. If a laser fits a mirror, it will change direction by 90 degrees, as it would in real life. the direction that the laser goes is dependent of the angle of incidence.

Walls:

Walls also comprise of 2 characters: | and _. A wall is simple in that it stops a laser, and ends the beam. The Direction of the wall is irrelevant. | and _ are functionally the same! If a laser hits a wall before the goal, then the solution is faulty.

Goals:

There is one goal per puzzle input to the program. The goal is represented by a * somewhere on the grid. The objective is to get the laser to pass through the goal from any cardinal direction.

Spaces:

Spaces are the easiest to recognize, as they're any character that's not already mentioned. for the purpose of the puzzle, you can assume that all spaces are . (dots).

Input:

Your input will be a square grid with grid elements and one goal. The grid will always be square, and will always have a goal. grid elements will be entered in a list that is either 1 row tall (eg: the 3x3 example puzzle would be [".","_",".","|","*","|",".",".","."]) or in a square set of arrays (eg: the 3x3 puzzle would be [".","_","."],["|","*","|"],[".",".","."]).

Output:

Your output will be a number which represents where the laser should be shot from in order to get to the goal. You can see how outputs are numbered below. If there is more than one solution, you may either output any or all solutions.

Examples:

 ..9
0._.8
1|*|7
2...6
 345

Output:4

This example shows how a grid will be numbered. it is numbered counter-clockwise starting in the top left at 0 such as there are 2 numbers for each row and column.The laser is placed at the position of the number and shot in at a multiple of 90 degrees.

The correct answer is 4 because the goal is enclosed by walls except where the 4 is located, which the laser gets shot in (in this case up). In the picture below, you see the same puzzle, but numbered correctly, along with another test case.

_{the directions on each example show the direction of travel for the laser for each number}

This is a code golf, so the shortest code will win! good luck!

Answer 22

The evolution of integers

code-challenge game-of-life restricted-source source-layout

---

The game of life (GOL) is a famous cellular automaton where cells turn on and off depending on how many neighbors they have. For a quick overview, the rules are:

Every cell is either alive or dead. Each generation:

• Every live cell with fewer than two live neighbors dies

• Every live cell with more than three live neighbors dies

• Every live cell with two or three live neighbors lives to the next generation, and

• And every dead cell with exactly three live neighbors is brought back to life.

You can play around with it here to see what happens with these rules.

The cool thing about Game of Life is that the structures and patterns will rapidly evolve over time creating some cool patterns. Let's take this idea of evolving patterns and use it for evolving integers. Here's what your submission must do:

1. Pick a starting configuration of the GOL. We'll call this your "template". Now you must write a program that has the same visual layout as this template. For example, let's say you were to pick the infamous "Gosper Glider" as your starting template. For reference, it looks like this:

    * 
     *
   ***
   

   Now your program can only have non-whitespace characters where the live cells are. So in my fictional programming language "Spam", this is a valid program:

    a 
     b
   123
   

   Running this program must output the number '1', optionally followed by a trailing newline.

2. Evolve your program. To evolve your program, apply one generation of the rules of GOL, where whitespace is a dead cell and non-whitespace is a live cell. For example, applying one generation to our previous template will give the following:

    * *
     **
     *
   

   Now you must write another program in the same language that follows this new template. This new program should print the number '2', again optionally followed by a trailing newline.

3. Repeat this process, evolving your template and increasing the number that is output for as long as possible.

Your score is the total number of generations your code goes while still producing the correct number. If someone manages to create a program that works to infinity, for example by using a gun or something similar, the winning criteria will be the number of live cells in the starting configuration. Earlier posting date will be used as a tiebreaker.

Any questions?

Answer 23

Print the missing primes

number primes code-golf

---

The Task

Write a program or function that, when passed a numerical input x, prints or returns the primes beneath the square root of x¹ that are not factors of x.

Examples

Let f(x) be the function called:

>>> f(5)
[2]

>>> f(20)
[3]

>>> f(60)
[7]

>>> f(100)
[3, 7]

>>> f(10000)
[3, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]

Bonus Rules

• You may use any builtins that your language provides.
• Your program must support an x input as high as the upper bound defined by your language.

---

¹ Using the square root as only primes below the square root can actually be involved within the factors of x. Without making this restriction, larger numbers would have a lot of excess numbers.

---

Meta

More specification?

Answer 24

3-way Polyglot Prime Checker code-golf

Make a program that checks if a number is prime in three distinct languages.

• Two versions of the same language aren't considered distinct languages.
• Standard loopholes apply

Answer 25

Generate the Collatz series

number-theorynumbermathalgorithmfastest-code

The Task

Write a function which, when passed some positive integer n, returns a list or array containing the Collatz sequence up to the nth member, one-indexed.

Definition

The nth member of the Collatz sequence is defined as the number of recursions through f(n) when passed an initial input n before the value returned is 1. f(n) is defined as:

Examples

Let g(x) be the function described in the task:

>>> g(8)
[0, 1, 7, 2, 5, 8, 16, 3]

>>> g(16)
[0, 1, 7, 2, 5, 8, 16, 3, 19, 6, 14, 9, 9, 17, 17, 4]

More examples may be found in OEIS entry A006577.

The Rules

• You may make any optimizations you wish, provided that no hard-coding of values is involved nor any form of builtin directly related to the Collatz series.
• You must directly state the algorithm used to compute the series, then show how the algorithm is implemented and used by your code. If your algorithm can be disproved, then your answer is invalid.
• Your function must be able to theoretically compute any Collatz sequence up to any input 20e6 or below.

Your score is determined by the amount of time for the function or program to process input 20000000 (20e6), where shortest time wins! All code will be tested in this workspace, which is a x86_64 machine running Ubuntu 14.04.3 LTS.

Answer 26

Get some info about a Stack Exchange site

Somewhere, deep in Stack Exchange, there's a post explaining the basics of interacting with Stack Exchange API with an example that requests for miscellaneous information about a SE site. In other words, it contains the print("Hello, World!") equivalent of SE API.

Let's take that example one step further.

Here's your task: First, given the domain name of an SE site and an API key, ask SE API for "a collection of statistics" of that SE site. Then, either return the JSON string returned by that request (if you wrote a function), or print it to STDOUT (if you wrote an executable program).

• Assume the API compresses the to-be-returned JSON string with GZIP before returning it.
• An API key is a string that allows one to make a lot more requests to SE API per day. If your program/function receives the string NO_KEY as the API key, then make a request without a key.
• The domain name is guaranteed to not be stackexchange.com, area51.stackexchange.com and discuss.area51.stackexchange.com.
• You do not need to format or parse the returned JSON string.
• You do not need to set up special handling for API-side errors. Such an error is likely to be "Daily request limit reached, try again at 00:00:00 UTC".
• Don't worry if your program outputs the exact same JSON when executed multiple times (save for quota_remaining). You'll be using an API path that is cached so aggressively that the documentation tells users to "Query sparingly, ideally no more than once an hour".
• Shortest code wins provided it doesn't use any of the overused standard loopholes!

Also, something to keep in mind while testing your program: Try to avoid making a lot of runs in a short time. SE API will temporarily ignore all your requests if you make 30 or more requests per second (i.e somehow run your program >=30 times/sec).

Test cases case

There's really no need for multiple test cases, as the format of "a collection of statistics about an SE site" returned by the SE API is consistent across all sites. Here's the one test case:

1. Run your program with codegolf.stackexchange.com as the domain name and NO_KEY as the API key
2. Go to https://api.stackexchange.com/2.2/info?site=codegolf.stackexchange.com on your favorite browser
3. Compare the JSONs given by your program and your browser. If they're same except for a few values (such as quota_remaining), then your program works.

code-golf stack-exchange-api json compression

---

• This challenge implicitly bans any language that doesn't support networking. Is that OK?
• I suspect I shouldn't tag this with compression and json, as they're there just because SE API's responses are compressed JSON strings.
• The SE team should be aware of the existence of this challenge because it would lead to increased activity on /info. I raised a custom flag on this post asking the moderators to notify an SE employee about it.

Answer 27

Give your processor a break!

code-golf code-generation kolmogorov-complexity

---

Introduction

Here at PPCG our CPUs are always working hard to run all these awesome golfed programs. Now nobody can work hard continuously without a break. So it's time to give your CPUs a break. For a CPU, such a break is called NOP. Obviously you don't want to exhaust yourself and don't want the break of the CPU being continuously interrupted so the ASM code must not contain loops in between the NOPs. And because time is money you have to write your program quick (=short).

Input

There is no input and you must not take any.

Output

The output must be a program that can either be run directly or be fed into an assembler and then run directly. Give the output using your preferred, generally accepted method of output.

What to do?

To give the CPU an adequate break, you want it to run on 1 million NOPs. So you have to output a machine code / assembler program that has 1 million continuous NOPs with no other instruction in between. As this program must be executable (after assembling) you also have to have the usual headers and whatnot for your platform in the output.

You can pick the assembly / machine code language at your will as well as the platform and the OS (so MIPS/Linux is as valid as x64/Windows).

Who wins?

This is code-golf so the shortest code (in bytes) to generate the correct output wins! Standard rules apply.

Answer 28

Gerrymander for the Americastanian Liberation Front code-golf

Briefing:

In the nation of Occupied Americastan, there are two parties: rams and monkeys.

---

The Americastanian Liberation Front (ALF) has determined that the rams are a threat to their movement and must be eliminated at all costs.

_{***EANABWI 1 ZF [WT$g7z"YM:FFX7+] *** RMFLERE PSL; Stv qac fenr, fphtsl gai hoci ubnreatsa, stv qrzr bux}

Task

You are given a rectangular grid of Rs and Ms, for example:

RRMRM
RMRRM
RMMMM
MRRMM

and an integer number, D, of districts.

Create D districts, maximizing votes as computed in:

votes = 0
for each district:
   if there are more Ms than Rs in the district:
       votes += area of district

• districts must be contiguous, by Von Neumann neighborhood.
• D will be greater than zero, less than the the area of the grid.
• width and height of the grid are greater than 3 and less than 10.
• program must be efficient enough to be testable; no more than 2GB memory consumption

Output format

Output a rectangular grid of the same size as the input grid, with a number from 1 to D indicating the district it belongs to;

RRMRM
RMRRM
RMMMM
MRRMM

Todo

• Testcases

Answer 29

What C++ type should I use? / Parse a CFG code-golf

Given as input I, as defined by this Context-Free Grammar:

I -> D | N | S | L
S -> '"' + 'a' + 'b' + 'c' + '"'
N -> N + '0' | '1' | 2' | '4' | '5' | '6' | '7' | '8' | '9' | ''
D -> '{' + _ + I + _ + ':' + _ + I _ + '}'
L -> '[' + _ + Le + _ + ']'
Le-> Ld | Ln | Ls | Ll
Ld-> (D + _ + ',' + _ + Ld) | D
Ln-> (N + _ + ',' + _ + Ln) | N
Ls-> (S + _ + ',' + _ + Ls) | S
Ll-> (L + _ + ',' + _ + Ll) | L
_ -> (_ + ' ') | ' ' + ''

Output a C++ type corresponding to the input, without std::. For example:

{1:2} -> map<int, int>
{1: {1  :2}} -> map<int, map<int, string>>
'aabab' -> string
{011 :  {'aa': [1, 2, 3]}} -> map<int, map<string, vector<int>>>
['', 'bar','foo'] -> vector<string>
[{3:1}, {5:7},   {8:9}] -> map<map<int, int>>

More formally, perform the task

• Parse the input according to the CFG, generating a tree.
• Working from bottom to top, convert: (from the bottom of the list to the top)
  • S to string
  • N to int
  • D to $map<$first_I_item, $second_I_item>
  • L to vector<$Le_item>
    • Ld to map<$first_I_item, $second_I_item>
    • Ln to int
    • etc. for L*
  • _ to <none>
  • Le to $child_value

Rules

• You will only receive valid inputs.

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

Answer 30

Note to readers: Not finished, currently working out examples

Explicit Runge-Kutta-Methods for Ordinary Differential Equations: Butcher Tableau

Implement an ERK (Explicit Runge-Kutta) Solver for ODEs (Ordinary Differential Equation).

Background:

An initial value problem is given by:

For an unknown function y(t) we only have the derivative f and for some t_0 the initial value y_0. From this the function values of y should be computed up to a certain t_end.

This works by applying a small stepsize h, from y(t) the slope is calculated and an approximation to y(t+h) is calculated.

For example the Euler-Method with h=0.1:

• y(0) = y_0
• y(0.1) = y(0) + h*f(0,y(0))
• y(0.2) = y(0.1) + h*f(0.1,y(0.1))
• y(0.3) = y(0.2) + h*f(0.2,y(0.2))
• ...

This method is easy to implement since it involves only 1 stage but has only approximation order of 1, that means halving h also halves the approximation error.

There are however better methods like Heun's method:

• y(0) = y_0
• y~(0.1) = y(0) + h*f(0,y(0))
• y(0.1) = y(0) + h/2*(f(0,y(0)) + f(0.1,y~(0.1))
• y~(0.2) = y(0.1) + h*f(0.1,y(0.1))
• y(0.2) = y(0.1) + h/2*(f(0.1,y(0.1)) + f(0.2,y~(0.2))
• ...

y~ is an intermediate value. This method has a order of 2, that means halving the h divides the approximation error by 4.

The classical Runge-Kutta method has an order of 4:

with

That means halving h divides the approximation error by 16.

Butcher Table

To generalize all methods there is the Butcher Tableau:

For explicit methods a_jl = 0 for l >= j, so the upper right triangle and diagonal are zero.

Then for each timestep do:

• Calculate the intermediate slopes k_j:

(the summation actually only needs to be done up to j-1)

• Combine to get the next y:

Task

Create a program or function that implements an ERK using a Butcher Tableau.

Input:

• Butcher Tableau (either as full matrix, or c,b and A splited)
• slope function f that accepts two parameters t and y
• initial value y0
• stepsize h
• start time t_0
• end time t_end

Output:

• List of values y(t_0), y(t_1), y(t_2), ..., y(t_end)