515
\$\begingroup\$

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

To post to the Sandbox, scroll to the bottom of this page and click "Answer This Question", or click on the "Add Proposal" link below. Click "OK" when it asks if you really want to add another answer. Write your challenge just as you would when actually posting it. 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.

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

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

The Sandbox works best if you sort posts by "active".

Add Proposal

Search the Sandbox

Browse your pending proposals

Get the Sandbox Viewer to view the sandbox more easily

\$\endgroup\$
0

3270 Answers 3270

1
96 97
98
99 100
109
0
\$\begingroup\$

Riffle shuffle two arrays

Take two arrays and evenly riffle shuffle them together.

Process:

Take the first items of each and add them to the array in order.

Input 1: [5,6,7]
Input 2: [8,9]
Output: [5,8]

Then the second

Input 1: [5,6,7]
Input 2: [8,9]
Output: [5,8,6,9]

Repeat until you've gone through every item of each array. If an array doesn't have an item at that slot, just skip it.

Input 1: [5,6,7]
Input 2: [8,9]
Output: [5,8,6,9,7]

Bonus

-30% if your program can handle multiple arrays. Process is the same.

Testcases

[1,2,3],[4,5] => [1,4,2,5,3]
[6,7,4,2],[] => [6,7,4,2]
[7,2],[7,2] => [7,7,2,2]

Bonus only
[1,2,3],[4,5,6],[7,8,9] => [1,4,7,2,5,8,3,6,9]
[1],[2,3],[4,5,6],[7,8,9,10] => [1,2,4,7,3,5,8,6,9,10]

This is , so smallest score wins.

Meta

  • Should I keep the bonus? If so, should I change it?
  • Does this already exist (I don't think so)
\$\endgroup\$
1
0
\$\begingroup\$

Finding Distant Primes

\$\endgroup\$
2
  • \$\begingroup\$ I'm a bit confused, why is 23 a 9-distant prime when |2⁴ - 23| = 7. Why did you raise 2 to specifically the fifth power? Or is both, and also a 22, 21, 19, 15, 7, 9, 41, etc... distant prime? \$\endgroup\$ – Medix2 Mar 17 at 4:22
  • 1
    \$\begingroup\$ @Medix2 yes it is all of those. \$\endgroup\$ – Manish Kundu Mar 17 at 4:50
0
\$\begingroup\$

Add trailing whitespace

Sometimes, we accidentally have trailing whitespace in test cases, and some helpful person notices and fixes that. Thank you, helpful people.

But what if we want to take a string without trailing whitespace and add some?

Your challenge is to write a program that takes a string as input and adds between 1 and 10 spaces (randomly) to the end of each line.

Rules

Between 1 and 10 (inclusive) spaces (" ") must be added to each line. There must be a nonzero chance of getting any number of spaces on any line.

This is , shortest wins.

Apologies if this already exists - It's really hard to search.

\$\endgroup\$
3
  • \$\begingroup\$ "just before each newline and the end of file" "trailing whitespace"? \$\endgroup\$ – tsh Mar 23 at 1:42
  • \$\begingroup\$ @tsh Sorry for being confusing. Rewrote. Is this a good challenge? \$\endgroup\$ – A username Mar 23 at 8:08
  • \$\begingroup\$ Maybe to make the challenge a bit harder require an additional line to the file with random number of spaces, because then less trivial answers \$\endgroup\$ – ophact Mar 23 at 16:16
0
\$\begingroup\$

2D Pathfinding with Momentum

Posted to main

\$\endgroup\$
0
\$\begingroup\$

Posted

\$\endgroup\$
0
\$\begingroup\$

Count What You See

You may have heard of the Look-and-say sequence, which is generated by reading off the digits of previous entries in the sequence. Here, you will be tasked to generate the "Count-and-say sequence".

In general, the sequence can be generated as follows:

  1. Start with an arbitrary sequence of numbers (e.g. 1, 1, 1, 3, 2, 1, 2).
  2. Count the occurrences of each number as adjective noun pairs -> "four 1, one 3, two 2", in order of 1st appearance. In the example, this means that you must first count 1s, then 3s, then 2s, since that is the order in which the numbers first appear in the sequence.
  3. Write out the result from step 2 numerically ("four 1, one 3, two 2" -> 4, 1, 1, 3, 2, 2).
  4. Append the result from step 3 to the original sequence to get 1, 1, 1, 3, 2, 1, 2, 4, 1, 1, 3, 2, 2.
  5. Repeat the steps above to continue the sequence.

Task

Your task is to output the "Count-and-say sequence", such that the sequence starts with 1. You may choose to:

  • Take an input \$ n \$ and output the first \$ n \$ integers.
  • Take an input \$ n \$ and output the \$ n \$-th integer.
  • Output the sequence indefinitely.

For convenience, here are the first 100 numbers in the sequence (also A217780):

1, 1, 1, 3, 1, 4, 1, 1, 3, 6, 1, 2, 3, 1, 4, 8, 1, 3, 3, 2, 4, 1, 6, 1, 2, 11, 1, 5, 3, 3, 4, 2, 6, 3, 2, 1, 8, 13, 1, 8, 3, 4, 4, 3, 6, 5, 2, 2, 8, 1, 11, 1, 5, 16, 1, 10, 3, 6, 4, 4, 6, 7, 2, 4, 8, 2, 11, 3, 5, 1, 13, 18, 1, 12, 3, 9, 4, 6, 6, 9, 2, 5, 8, 3, 11, 4, 5, 2, 13, 1, 16, 1, 10, 1, 7, 22, 1, 14, 3, 11
\$\endgroup\$
0
\$\begingroup\$

Equalizing fractions

\$\endgroup\$
1
  • \$\begingroup\$ I've edited this down to a stub now that it's been posted to save space \$\endgroup\$ – caird coinheringaahing Apr 1 at 21:13
0
\$\begingroup\$

Node one-liner to fetch a URL, like curl

I'm interested in the shortest one-liner to output the contents at a given URL, using Node.js from the command line, for practical purposes. In other words, the equivalent of curl, written as a Node one-liner.

Not interested in other languages. Would this respect the site's rules, or does it belong on SO?

Rules:

  1. The URL is passed via the command line, so accessed via process.argv[1]
  2. Must invoke node with the -e argument, followed by the code, followed by the URL
  3. Only the length of the actual script passed to node via -e "..." is counted.

My best solution so far, with http://x.com as a conveniently short example, is:

node -r got -e "require('got')(process.argv[1]).then(r=>console.log(r.body))" http://x.com
\$\endgroup\$
1
  • \$\begingroup\$ You can make it a tips question \$\endgroup\$ – user Apr 2 at 12:03
0
\$\begingroup\$

Program-Write a program to display repeating terms of a given sentence.

Explanation-the program must output the repeating terms of two or more letters from the given input(input is a sentence seperated be spaces without any punctuation except the full-stop indicating the end.) For example, if input is the sentence "I am an ameture mathemagician" the outupt must be am, ma, an. ( not that em is not a valid output as it is separated by space)

Example-

input->International competitions are better than intercollege ones.

output-> Inter, ti, er, tion, io,on,ion, tio, co, on,.......etc (t, l must not be included as they are 1 letter.) (Upper lower Cases do not matter)

Test cases-

input-> aabcde cdec

output-> cde, cd, de

input-> aab aacab

output-> aa, ab

input-> aaa aabcaaa ababa

output-> aaa, aa, ab, aba, ba

Winning Criterion:- code golf

\$\endgroup\$
3
  • \$\begingroup\$ You say tt and ll aren't included, but then have aa as an example output. Also, what if two things overlap? In ababa, is aba included? \$\endgroup\$ – rak1507 Apr 3 at 13:33
  • \$\begingroup\$ Thanx edited accordingly. \$\endgroup\$ – Aatmaj Apr 3 at 13:44
  • \$\begingroup\$ Is the input always going to contain at least 1 space? And can input be taken as a list of words (e.g. ['aab', 'aacab']) instead of a space-separated string? Additionally, I'd suggest mentioning something about the case of the input. For example, case-wise, your example (International ...) only has inter repeated if case is ignored \$\endgroup\$ – caird coinheringaahing Apr 4 at 0:20
0
\$\begingroup\$

Getting to the root of the problem

While I was sleeping in my bed, unwilling to wake up, an idea entered my head: why is the syntax for powers, especially roots, so cumbersome? It would save so many bytes if we could just use the square root symbol instead, and easier to understand too. So, your challenge is to encode this in whatever format you choose, in as few bytes possible.

Answers should be able to:

a) convert a string such as 2**(1/2) into √2 or some other format that distinguishes it from 2√2 (note, if you choose to write 2√2 as 2 * √2 and write things like 2**(1/3) as 3√2, that is allowed).

b) Work for arbitrary powers (2**(1/50) should work fine).

c) Simplify roots. (4**(1/4) = √2)

and should be able to perform this on inputted strings.

Deduct 10% from your score if you can handle addition of roots, deduct a further 10% off that if you can handle the ret of the basic operators (-, *, /), another 10% if you can simplify expressions such as (2 - √2)/(2 + √2), another 10% if you can write 16**1/4 (for example) as √(2^2), and, if you're amazing enough to implement exponentiation, you can subtract 50%.

Input will be presented in the form of [0-9]**([0-9]/[0-9]), where the 0-9s can be any number of digits. Output should ideally be in the form of [0-9] * [0-9]√[0-9], again, with the 0-9s being any number of digits, but I will let other forms slide so long as as 3√2 (that's the cube root of 2) is distinguishable from 3 * √2.

Tags:

Lowest score wins. Good luck!

\$\endgroup\$
5
  • \$\begingroup\$ This is a good challenge, at least part A looks good, but it will need to be clarified. Ideally put a regex that objectively tells what input we need to handle (like whether we should handle whitespace (which we probably shouldn't have to)). The bonuses are most likely unnescessary. \$\endgroup\$ – Wezl Apr 4 at 1:50
  • \$\begingroup\$ The bonuses might be unnecessary, but if someone can write a creative answer that does all of that, it'd probably be an even better answer than one that just does the minimum, and might score lower (I was generous with the bonuses to encourage going the extra mile, and you can get a reduction of over 70% from them). About the input, I'll fix that now. \$\endgroup\$ – StackMeter Apr 4 at 10:02
  • \$\begingroup\$ Also this is going to be important to my tie-in puzzle, "Returning to the root of the problem", and having those bonuses done now will improve your overall score (yes this may well be a series). \$\endgroup\$ – StackMeter Apr 4 at 10:12
  • \$\begingroup\$ Should 72**(1/6) be 2V2*3V3? \$\endgroup\$ – l4m2 Apr 6 at 13:33
  • \$\begingroup\$ You can do it as such if you want to. \$\endgroup\$ – StackMeter Apr 6 at 13:51
0
\$\begingroup\$

Computer Tree

Consider an infinite amount of same computers building a tree, running same program. Each computer has infinite memory and infinite pins 0 to Infinity, where pin 0 connect to its parent, or the IO we see for the root; and pin 1..Inf connect to its childs.

Each connection is bidirectional, and has buffer in each direction. Writer put the value into buffer, and reader gets from it.

The computers need to support these abilities: (Here dest is a variable in the memory, and src1, src2 are either variable or immediate integers. [x] mean the memory in address x.

dest = src1 op src2, op in +,-,*
[dest] = src1
dest = [src1]
if(src1 op src2) goto inst, op in <,==,<=,!=
if((not)pin src1 writing) goto inst
if((not)pin src1 reading) goto inst
write src2 to pin src1, block if already writing
read dest from pin src1, block if not reading

It's fine if you need several elements to do one job above, but each job defined above should use same amount of time(In this model timing matters). It's also fine if you take input as some other formats, but to avoid taking too ready functions, an same-type input shouldn't lead to an infinite loop. Input for root is given when started and will never need to wait unless all input used up, but it doesn't always halt.

Shortest code win.

\$\endgroup\$
0
\$\begingroup\$

Tags:

Interpret a Cangjie Input Method String

The Cangjie input method is a method for inputting Chinese characters using a standard QWERTY-like keyboard. Each Chinese character is encoded as a sequence of Latin letters, each letter representing a radical, or part, of the character's form. Each letter encodes both the radical character it represents, as well as other, related radicals (such as E encoding as well as , and more).

There are 24 radicals encoded in Cangjie, as well as 3 other characters for wild cards and other purposes. For the purposes of this challenge, only the subset of the main 4 groups are used, shown below with meanings:

Philosophical group
A   日 sun
B   月 moon
C   金 gold
D   木 wood
E   水 water
F   火 fire
G   土 land

Stroke group
H   竹 bamboo
I   戈 dagger axe
J   十 ten
K   大 big
L   中 centre
M   一 one
N   弓 bow

Body parts group
O   人 person
P   心 heart
Q   手 hand
R   口 mouth

Character shapes group
S   尸 corpse
T   廿 twenty
U   山 mountain
V   女 woman
W   田 field
Y   卜 fortune telling

Cangjie Basic Rules

Characters are analyzed as such to create a Cangjie code (based on the Wikipedia article above):

  • Direction of decomposition: left to right, top to bottom, outside to inside
  • Geometrically connected forms: takes 4 Cangjie codes from the 1st code to the last code
  • Geometrically unconnected forms:
    • Forms in exactly 2 subforms: Follow the direction of decomposition rules, then take the first and last codes of of the first subform, and the first, second, and last code of the second subform.
    • Forms in more than 2 subforms: take the first and last codes of the first subform according to direction of decomposition, then break the remainder into subforms. Take the first and last codes of the first remainder, and the last code of the last remainder.

The Challenge

Write a full program or function that, when given a valid Cangjie code string as input, outputs its corresponding traditional Chinese character.

Additional Rules

  • Use Cangjie version 5.
  • Standard loopholes are forbidden.
  • An invalid Cangjie code string (not in our subset of codes) is undefined behavior when used as input.
  • If multiple characters match a Cangjie code string, you can choose to output both, or choose one. If you choose one, it must only output that character when given that code.
  • This is , so shortest code wins!

Examples

Input - Output (notes)
JWJ - 車 (connected, top to bottom: 十田十)
YRHHI - 謝 (3 parts: first is disconnected, take first and last YR;
           second is is disconnected, take first and last HH; last part take last I)
AN - 門 (special case: fixed decomposition)
OMN - 气 (another fixed decomposition; using version 5)
A - 日
BOB - 肭
JPHI - 蜜
GUMPC - 顤
STKR - 匿 or 𡲢 (if multiple characters exist for that code, pick one deterministically)
HXH - (undefined behavior, since X is not in the set of codes above)

Meta

  • Is it clear? Anything that needs adding/removing?
  • Any weird test cases I didn't put in?
  • Anything else?
\$\endgroup\$
1
  • 2
    \$\begingroup\$ It's not clear enough how to actually do the conversion (without looking at the Wikipedia article). Remember to always assume no pre-existing subject knowledge when writing challenges, and don't require users to use external resources to find out about it. \$\endgroup\$ – pxeger Apr 7 at 17:20
0
\$\begingroup\$

Text in aLtErNaTiNg cApS

Sometimes, we want to convey sarcasm in a text message or in a YouTube/Reddit comment. To this end, "alternating caps" is often used. Your task, should you wish to accept it, is to write code that turns the input text into its "alternating caps" version.

(This is a deleted rule. You should ignore this for the challenge) For most sans-serif web fonts, it is hard to distinguish capital I (for India) and lower-case l (for Lima). So we want to avoid either of these letters in our output. To achieve this, we are allowed to sacrifice "exact alternating-ness" of the output. Details below.

Input:

  1. A string of words involving [a-zA-Z], with one space in between each word.
  2. You may not assume whether or not the string ends with a space/newline/etc.

Output:

  1. The input, turned into "alternating caps form", with the first letter of each word being lower-case.
  2. (Deleted; you should not implement it. I have included it just to illustrate my thought process) You may not output any capital I (I, for India) or lower-case l (l, for Lima). To avoid these, you may continue outputting the same letter-case as the previous letter, but you must switch the letter-case at the earliest possible instance. (note to self: this requirement means there are sometimes more than two letters of the same case, which I don't really want)

  3. Non-suppressible output can be ignored.

Rules:

  1. Standard loopholes are forbidden.
  2. You must take input from and output to natural places, according to your language.
  3. This is code-golf, so the lowest byte-count wins. Ties are broken by earliest submission.
  4. Please provide a way for readers to test your code (e.g. TIO).
  5. An ungolfed version and an explanation for your code is appreciated, although not required for the challenge.

Examples

Input -> Output
---------------
alternating -> aLtErNaTiNg
lower case letters -> lOwEr cAsE lEtTeRs

Examples that follow the deleted rule (which you should not implement -- these are just for your interest:

I used dcode to find some of these examples. holding -> hOLdiNg radii -> rAdii (has more than 2 lower-cases in a row, if using my rules) fall -> fALL (has more than 2 capitals in a row, if using my rules) volleyball -> [even if you are allowed to change the previous letter-cases to try to stop 'ALL' (3 capitals in a row) from appearing, there is a non-unique way of doing so]

Good luck!

\$\endgroup\$
2
  • 1
    \$\begingroup\$ Unfortunately this has been posted before: codegolf.stackexchange.com/q/122783 \$\endgroup\$ – pxeger Apr 8 at 8:36
  • \$\begingroup\$ @pxeger That challenge is slightly different, as this one asks for alternating characters rather than alternating letters. lower case letters in that challenge would become LoWeR cAsE lEtTeRs (or lOwEr CaSe LeTtErS), neither of which are acceptable outputs for this \$\endgroup\$ – caird coinheringaahing Apr 11 at 14:02
0
\$\begingroup\$

Take two registers, zero-extend one to another one on x64 in a single instruction.

Here, registers are r0-r15(64-bit), r0d-r15d(32-bit), r0w-r15w(16-bit) and r0b-r15b(8-bit), where regs marking same number share same lowest part. In case there's no solution (e.g. writing into r0d, which the opcode would behave writing to r0), output something obviously not an opcode.

Opcodes:

90              do nothing
89 11sssddd     move 16/32/64-bit[1] from sss[2] to ddd[2]
88 11sssddd     move 8-bit from sss[2] to ddd[2]
0F B7 11dddsss  move from 16-bit sss[2] to 32/64-bit[1] ddd[2]
0F B6 11dddsss  move from 8-bit sss[2] to 16/32/64-bit[1] ddd[2]
101101dd 00     move from 8-bit 0dd[2] to 16-bit 0dd[2]             
[WIP]

Shortest code win. -35 Bytes if you support ax cx dx bx sp bi sp di aliasing r0w-r7w, and rax-rdi as r0-r7, eax-edi as r0d-r7d; - another 35 Bytes if you support al cl dl bl aliasing r0b-r3b and ah ch dh bh as theoretically r4b-r7b but without REXs.

\$\endgroup\$
0
\$\begingroup\$

Make an image with the pixels from another (WIP)


Given a target image and a source image, output an image that resembles the target image by rearranging the pixels of the source image.

You will be scored based on speed and accuracy.

$$ score = {similarity(Image_{target}, Image_{result}) \times {time_{reference} \over time_{program}}} $$

Higher scores are better

\$\endgroup\$
0
\$\begingroup\$

On a 150x150 area, each cell have 15% probable of being a mine. Opening a safe(non-mine) cell tells you amount of mines with <1.5 distance. Opening a mine makes you fail. Find most safe cells in 5 second.

\$\endgroup\$
2
  • 3
    \$\begingroup\$ This isn't very well specified. How will the grid be given, and will it be given via interactive I/O or do we need to provide a function that will be called multiple times? How will this be timed? Will testing be done via a fixed sample? Also, I am pretty sure that any reasonable implementation (doesn't even need extreme optimizations) will be able to clear an entire 150x150 board in well under 5 seconds. \$\endgroup\$ – hyper-neutrino Apr 10 at 17:22
  • \$\begingroup\$ @hyper-neutrino What about 1500x1500? Giving grid method quite flexible \$\endgroup\$ – l4m2 Apr 10 at 18:13
0
\$\begingroup\$

Packing numbers to interval

,

Interval notation is a way to write complicated range bounds more conveniently and concisely than writing an inequality.

Like a list 1, 2, 3, 4 can be written like [1,4].

There have been already challenges on interpreting interval notations to number ranges, but now we will do the reverse.

Some examples (test cases):

  • Input will be a list of numbers (can be positive, negative, 0, but not fractions)

  • Input list can be unsorted

  • If there is gap between the numbers (I mean in a list like 1,2,5,6, 3,4 is missing), you have to write multiple intervals seperate by Union sign (U)

  • There will be no leading 0s in input numbers

  • If there is only one number seperate in an interval (I mean like 2 in the list of 2,5,6,7) then make a seperate interval (for the example [2]U[5,7]

  • The intervals should go from smallest to largest (for example 1 2 5 6, [1,2]U[5,6] is valid but [5,6]U[1,2] not.

  • Input numbers can be separated by anything, it is up to you.

1 2 3 4 -> [1,4]
5 3 4 1 2 -> [1,5]
2 1 6 5 -> [1,2]U[5,6]
6 7 9 8 -4 -2 -3 0 2 1 -> [-2,-4]U[-0,2]U[6,9]

Standard loopholes apply, shortest code wins.

\$\endgroup\$
2
  • \$\begingroup\$ Could this be a duplicate of this? \$\endgroup\$ – Leo Apr 12 at 3:47
  • \$\begingroup\$ @Leo hmmm... i think its really a duplicate \$\endgroup\$ – Wasif Apr 12 at 3:56
0
\$\begingroup\$

Two player tic-tac-toe game

Create a Tic-Tac-Toe game that allows two human players to play against each other.

  • The drawn board can be either in ASCII or graphical (You can use 1-9 digits as a place holder in tic tac toe board)
  • Program should randomly choose whose turn is first and randomly give two players X or O
  • let both users know whose turn it is amd prompt for input
  • Check for winning, and when one player is won, let them both know about win (same for draw game)
  • Enforce all tic-tac-toe rules

Standard loopholes apply, shortest code wins

\$\endgroup\$
0
\$\begingroup\$

Hamming Distance Lookup Extravaganza

Note: I was originally just going to post this, but I was having trouble coming up with a good scoring strategy. I'd like to make sure that the instructions are clear and scoring strategy is fair and works. Thanks!

Note: This question is a WIP, and some parts may be incomplete or in the middle of editing!

Story

Bitty Benny runs a clothing factory, where, among other things, he produces bundles of shirts. Each shirt has a tag (don't worry, it's not itchy) describing what type of shirt it is.

Similar shirts have similar tags, and Bitty Benny wants to create an organization system, that, given a tag, will fetch the shirt with the most similar tag. Each tag is the same length, and lists a series of ones and zeros. To compare how similar tags are, Bitty Benny bought a Hamming Shirt Comparator (Mark II). Here's a loose schematic as to how the comparator works:

  1. First, the Comparator takes the two tags and lays them side by side, like so:
    +----------+
    | 10010100 |
    +----------+
    | 00101101 |
    +----------+
    
  2. Then, the comparator goes through each pair of numbers and counts the number of differences:
    +----------+
    | 10000100 |
    +-|---|--|-+
    | 00001101 |
    +-|---|--|-+
      x   x  x : 3 differences
    
  3. The comparator then laser-engraves the difference onto a marble stone tablet. Some argue that the Mark I was better, because it printed out results instead, but Bitty Benny likes the satisfying thunk of the tablet as it falls from the machine.

The lower the number the comparator outputs, the more similar the shirts are. A perfect match has a score of 0, an imperfect one has a score of the length of the tag.

Bitty Benny has a lot of impatient (but well-paying) clients who demand specific types of shirts. How can Bitty Benny organize and search through the shirts to find the closest-matching tag as quickly as possible?

Formal Definition

A tag is a bit-vector of size N, where N is a power of two. For this particular challenge we'll assume N to be 64.

Hint: On modern CPU architectures, a tag can be represented by a word (an unsigned 64-bit integer), and the difference between two tags can be written as an xor then a popcount (count the number of ones in the binary representation of the integer). This distance is generally referred to as the hamming Distance (lowercase 'h', of course) between two words.

Naïvely, using a linear search, finding a tag will take O(n) time. Faster solutions exist - can you find them?

Input

Your program will take two inputs:

  1. A list of random tags.
  2. a different list of target tags.

These lists may be of different sizes. The input format will be as follows:

<Size of random tags list>
<tag as a decimal number `0 <= n < 2^64`>
...
<Size of random target tags list>
<tag as a decimal number>
...

The competition input has been generated, and can be found here.

Task

For each target tag, determine the closest match in the random tag list, using hamming Distance as described above.

In the case of a tie, i.e. multiple tags have the same minimum distance, any one is valid.

Output

In the order of reading, print out the closest match of each tag as a number, in the appropriate base.

Scoring and Rules

The goals of this competition are to find solutions that are:

  1. Fast, in terms of execution time.
  2. Clever, in terms of algorithm used, amortized cost, and write-up.

To score your program:

Note: I have to finish writing example baseline program Note: I have to generate and upload the testing list. Ideally it should be big enough that the naive solution takes around 3 seconds on a modern computer.

  1. Translate this naïve idiomatic program from Rust to your language of choice.
  2. Time the naïve solution in your language of choice.
  3. Write an optimized solution in the same language, and time it using the same technique.
  4. Your score is the optimized execution time, in seconds + that times the speedup, lower scores are better:
    score = fast_time +  ((fast_time ** 2) / slow_time)
    

Time your programs using time, include the time taken for I/O.

Note: This scoring method is good for two reasons:

  1. In the case that there is no speedup compared to the baseline, the score is just 2x the time.
  2. Any speedups over the base version will decrease the score, but the score will never be less than the wall-clock time it takes.

To determine the answer with the best writeup, we'll also be running a popularity contest.

Entry Template

I'm no stickler, but here's a loose entry template if you'd like to keep things consistent:

## <Language> <Speed Score> (<Calculation>)
<Link to idiomatic solution>
```
<Optimized entry>
<If over a respectable size, put a link here instead>
```

## How it works
<breakdown of the code>
<and the method used>
<and any other interesting notes>

Good luck, and happy tagging! Bitty Benny awaits your entry!

\$\endgroup\$
0
\$\begingroup\$

Participant number

,

A math Olympiad will be held, and participants are being registered. The highest number of participants is 100. Each participant is given an ID number. It is given in a sequence like \$100, 97, 94, 91, 88, ...., 1\$, and when the first sequence is over, then \$99, 96, 93, 90, 87, ...., 3\$ sequence and so on.

Let's assume one of the participant's ID number is \$k\$ and he/she is the \$n^{th}\$ participant. Given the value of \$k\$, return the value of \$n\$.

Test Cases

59 -> 81
89 -> 71
16 -> 29
26 -> 92
63 -> 47
26 -> 92
45 -> 53
91 -> 4
18 -> 62
19 -> 28

There will be no leading zero in input. Standard loopholes apply, shortest code wins. In output there can be trailing whitespace.

\$\endgroup\$
1
0
\$\begingroup\$

Given a table(2D array of strings), arrange width of each column to shorten total width, such that containment in each cell can be fully shown with a space after it, being allowed to occupy next several cells if they are empty. In another word, for each column provide a width \$W_j\$, making \$\sum_jW_j\$ smallest, and for each non-empty cell in column \$i\$ , if there're \$k\$ empty cells on adjacent right, then its length is smaller than \$\sum_{j=i}^{i+k}W_j\$.

Samples:

"1234", ""  => [2,3] "1234 
"a"   , "b"           a b  "

"Date"  , ""  , "Sum"            "Date   Sum
"Mar"   , "1" , "220"             Mar 1  220
"Mar"   , "15", "130" => [4,3,4]  Mar 15 130
"Apr"   , "3" , "100"             Apr 3  100
"Sum_Up", ""  , "450"             Sum_Up 450 "

"aaa" ""    ""               "aaa
""    "bbb" ""    => [0,0,4]  bbb
""    ""    "ccc"             ccc"
\$\endgroup\$
0
\$\begingroup\$

Fastest unique finder

\$\endgroup\$
0
\$\begingroup\$

Given a string s, find a string t, containing only printable ASCII characters (32-126), such that PPCG53675(t)=s. You can assume such string exist.

Examples:

  • tmop => test (and 23 other possible outputs)
  • TEST => T5oV (and 23 other possible outputs)
  • !!!! => !!!! (and 17)
  • !! => ! (only one solution)
  • ~}}~ => ~|~~ (only one solution)
\$\endgroup\$
3
  • 1
    \$\begingroup\$ @RedwolfPrograms How? ac is not a valid output for ac \$\endgroup\$ – l4m2 Apr 13 at 18:35
  • \$\begingroup\$ Oh, didn't notice that it can be multiple characters. \$\endgroup\$ – Redwolf Programs Apr 13 at 18:38
  • 3
    \$\begingroup\$ It might be harder than it sounds (at least to solve efficiently), as there are edge cases involving values close to 32 and 126. Looks like a good challenge, though it needs some good test cases. Also needs a self-contained description. \$\endgroup\$ – Bubbler Apr 15 at 9:11
0
\$\begingroup\$

Meta-golf Branch integers without alphanumeric characters

Recently I created a new programming language, Branch (name thanks to caird coinheringaahing). Representing numbers is pretty easy (actually, trivial; you can just enter the number and it will set the value of the current node to that number).

However, until a recent revision, you could only enter one digit, and larger numbers needed to be generated by combining digits with various operations. This led me to think of this challenge - given any integer, you can represent it without needing the digits, actually.

Branch Specifications

Branch operates on a binary tree. Initially, there is just one node with a 0 as its value. Nodes hold long long ints. Any node that's created (unless otherwise specified) has a 0 initially.

Without the digits, here are the relevant instructions (you can also check them out on the wiki page):

Unary Operators

! - logical NOT; set the value to 1 if it's 0 and 0 otherwise
~ - bitwise NOT / complement; flip the bits; this is equivalent to -1 - x
_ - negate; set the value to -x
{ - decrement
} - increment

Binary Operators

+, -, *, :, %, ', <, =, >, &, and | are add, subtract, multiply, integer divide, modulo (keeps the sign of the right argument), exponentiation, strict less than (1 is true, 0 is false), equality, strict greater than, bitwise AND, and bitwise OR, respectively.

Division and modulo give 0 if the right argument is 0. The left and right arguments are the left and right children. Note that Branch will read from STDIN if these are missing, instead of initializing to 0, so for this challenge, you need to ensure that the children are defined before calling a binary operator, because reading from STDIN is not allowed.

The value of evaluating the operation will be stored in the current node.

Pointer Movement

/ - move to the left child (creates it if it does not exist)
\ - move to the right child (^)
^ - move to the parent of the current node (if it doesn't exist, a new node is created, and this node becomes the new node's left child)
? - conditional - if the current value is 0, move to the left child, and otherwise, the right child (creates the required one if absent)

Miscellaneous

" - set the parent's value to the current value (creates with this node as the left child)
; - set the current value to the parent's value (creates with this node as the left child and with 0 as the value)
@ - swaps the values of the children without changing the structure (creates both nodes with 0 if necessary)
[...] - loop; this works just like in BF; reaching the [ with 0 as the value skips to the matching ], and reaching ] with a non-zero value jumps back to the [

Finally, # outputs the current value as an integer. There are some other I/O commands and other random things but they won't be used for this challenge. I have registers too, but I've chosen to keep them out. Finally, I removed the rotations from this challenge because I didn't feel like dealing with them, even though they probably aren't too complicated especially for anyone who knows how to implement AVL trees.

Challenge Specification

For each integer from 1 to 100, you are to provide a snippet that produces that number as the current value. In other words, your snippet should not have # in it, and when # is appended to it, should output exactly that integer. You cannot do 1## to output 11 (assuming digits were allowed), for example.

Example

For 1, you could do something like /^\^', which creates the children as 0 and then computes 0 ** 0 which is equal to 1.

Details

  • this is a ; the submission with the least number of bytes total for all 100 snippets wins
  • standard loopholes apply
  • good luck and have fun!

Meta

  • is this clear enough?
  • is this too unnecessarily complicated; are there any things I could remove (like I did with the rotation operations) that would make this still interesting?
  • is this even interesting?
  • this is not a duplicate
\$\endgroup\$
0
\$\begingroup\$

Non-Hamming numbers

\$\endgroup\$
2
  • 1
    \$\begingroup\$ I would suggest including a definition of hamming (or non-hamming) numbers in the challenge description. \$\endgroup\$ – Delfad0r Apr 11 at 10:10
  • 3
    \$\begingroup\$ You definitely need to define non-hamming numbers - challenges should never require you to look at an outside source (the challenge you linked should too), and I would suggest providing a detailed example of how to compute them as well. Also, add the sequence tag. \$\endgroup\$ – pxeger Apr 11 at 10:25
0
\$\begingroup\$

Brainfuck to ESOPUNKS

Brainfuck use 8 instructions

byte(or bigint, your choose) a[inf]; bigint i;
+  ++a[i];
-  --a[i];
,  a[i]=getchar();
.  putchar(a[i]);
[  while(a[i]){
]  }
<  if(--i<0) undefined_behavior();
>  ++i;

ESOPUNKS have two registers X and T, two I/O ports #STDI(stdin, read like how brainfuck does), and #STDO(stdout, undefined behavior if written <0 or >255), use these instructions:

COPY a b     b=a; a,b,c can be X,T,#STDI,#STDO or integer as long as it makes sense(no giving integer a value, etc.)
ADDI a b c   c=b+a;
SUBI a b c   c=b-a;
MULI a b c   c=b*a;
DIVI a b c   c=b/a; Halt if a=0
MODI a b c   c=b%a; Halt if a=0
MARK label   label:
JUMP label   goto label;
TJMP label   if(T) goto label;
FJMP label   if(!T) goto label;
TEST a op b  T = (a op b); op = <, =(==), >
HALT         exit(0)

(Didn't cover all instructions from esolangs as some are not implemented in the interperter)

Now write a program that converts a Brainfuck program into a ESOPUNKS one. Your ESOPUNKS output should have O(1) lines.

Note:

  • It's possible to convert. Wiki shows a proof that applies with small removal.
  • It's possible for bounded lines to store unbounded info as unbounded integer behave as operator
  • Outputting may need a snippet repeating 256 times to allow any possible output; However I don't care length of output(as long as it's bounded), and the repeating can be generated with small code, so this shouldn't matter much.

Code-golf, shortest code in the language wins.

\$\endgroup\$
1
  • \$\begingroup\$ Unless I'm misunderstanding some aspect, this is unreasonably hard. Converting between a TM (brainfuck) and a 2 counter machine (Esopunks), while possible, has a lot of caveats that are delineated by the wiki page you linked, most relevantly that the input has to be given as an initialization of one of the counters as an integer encoding a TM. Then the actual conversion algorithm between TM and 2CM is also extremely involved, not least of which includes encoding 4 counters in one via the prime factorization \$2^a3^b5^c7^d\$. This is closer to a thesis project than a code golf... \$\endgroup\$ – kops Apr 27 at 1:28
0
\$\begingroup\$

Extract json, with only few bytes.

Extract the "name" of each dictionary in the json list.

You are allowed to use any package which can be installed on Ubuntu 20.04.

Example json:

[
    {
        "id":"d963984c-1075-4d25-8cd0-eae9a7e2d130",
    "extra": {
        "foo": false,
        "bar": null
    },
    "created_at":"2020-05-06T15:31:59Z",
    "name": "NAME1"
    },
    {
    "id":"ee63984c-1075-4d25-8cd0-eae9a7e2d1xx",
    "name": "NAME2"
    }
    ]

This script would work:

import json
import sys

for item in json.loads(sys.stdin.read()):
    print(item['name'])

Desired output:

NAME1
NAME2

But since I am very lazy, I am looking for a solution which needs less characters.

The solution with the minimal number of bytes wins.

Using non-ascii characters is not allowed.

Compressing into base64 or similar is not allowed. The solution should be "type-able" by a human.


Since the question does not fit ot code-gold, I published it here: https://stackoverflow.com/questions/67194693/filter-json-on-the-command-line

\$\endgroup\$
8
  • 3
    \$\begingroup\$ Welcome to the site, and thank you for using the sandbox. Note that, by default, we count code in number of bytes, not number of characters, to prevent abuse like compressing code into Unicode characters that might need up to 4 bytes each. \$\endgroup\$ – Adám Apr 20 at 9:45
  • \$\begingroup\$ @Adám I updated the question. It should be type-able. Do you think it is ok now? \$\endgroup\$ – guettli Apr 20 at 9:51
  • 1
    \$\begingroup\$ Why prohibit non-ascii characters? I can certainly type non-ascii characters on my keyboard, and I'm human. \$\endgroup\$ – Adám Apr 20 at 9:53
  • 1
    \$\begingroup\$ Why prohibit compression? If that gives me a better score, then why not use that? \$\endgroup\$ – Adám Apr 20 at 9:53
  • 1
    \$\begingroup\$ I'd use the word "extract" rather than "filter", since we're not reducing the number of dictionaries. Rather, we're extracting the "name" member of each. \$\endgroup\$ – Adám Apr 20 at 9:55
  • \$\begingroup\$ @Adám I search for a solution which I could easily apply in the future again. I need to extract data from json from time to time and I am searching for a pattern which I can re-use. That's why compression (like gzip/base64/...) makes no sense to me. I want the solution to be readable and more or less easy to understand. Maybe "bytes" is the wrong unit for what I want. \$\endgroup\$ – guettli Apr 20 at 19:25
  • 2
    \$\begingroup\$ I think your challenge is interesting and has potential, but please do not try to use this site as a place to get programming help. For that, try Stack Overflow instead. Be warned that people here will break all best practices and accept extreme inefficiency to save a single byte. If you try to circumvent this culture (which is the purpose of the site!) then you will be met with what can be perceived as hostility. \$\endgroup\$ – Adám Apr 20 at 19:54
  • \$\begingroup\$ Even though you've posted on SE, do you want to sort this out as a proper code golf challenge for this site too? \$\endgroup\$ – Adám Apr 21 at 11:53
0
\$\begingroup\$

Largest Compatible Maze

\$\endgroup\$
0
\$\begingroup\$

Generate a uncomputable number

An uncomputable number is a number that some digit can't be computed in finite time.

Now you're to generate and output one of them.

You can(and need to) use \b to undo an outputted byte, but every byte should stop changing from some time.

An example solution, assuming stepN(p, n) checks if program p halts in n steps, returning 0 or 1:

s = [];
output('0.');
for (i=1; ; ++i) {
    t = [stepN(j, i) for j in [1,n]]
    while (s is not a prefix of t) {
        output('\b');
        s.remove_last();
    }
    for (j=s.length; j<t.length; ++j) {
        s.insert_to_last(t[j]);
        output(t[j]);
    }
} // 0.s[0]s[1]s[2]s[3]..., s[i] mean if program i halt

Shortest code wins.

\$\endgroup\$
10
  • 1
    \$\begingroup\$ Where does your definition of "uncomputable number" come from? What I'm familiar with is "a number defined in terms of uncomputably fast-growing function". \$\endgroup\$ – Bubbler Apr 22 at 9:07
  • \$\begingroup\$ I can imagine that a slight modification of the challenge would work using my definition: Pick an uncomputable function f(n). Given n as input, output an infinite sequence of numbers, which should eventually produce an infinite stream of f(n) and nothing else. A possible answer in this case is a BF busy-beaver function, where you run each step of all syntactically valid BF programs of length n and update the answer whenever one of them halts. \$\endgroup\$ – Bubbler Apr 22 at 9:13
  • \$\begingroup\$ @Bubbler Defined as "not computable" \$\endgroup\$ – l4m2 Apr 22 at 9:51
  • \$\begingroup\$ Then I guess you should include in the first sentence that you want a real number, as opposed to an integer. I could find only one uncomputable real number, Chaitin's constant, which is a halting probability of a random program (in a hypothetical programming language with a specific property). Also, IMHO erasing digits with \b is superfluous and unnecessary, and you should allow outputting infinite stream of digit strings (and allow printing or returning them). \$\endgroup\$ – Bubbler Apr 22 at 10:14
  • \$\begingroup\$ Also, should the number be output in decimal, or can I output it in binary or other base? \$\endgroup\$ – Bubbler Apr 22 at 10:21
  • \$\begingroup\$ @Bubbler If an expressing is uncomputable in binary, it is for decimal \$\endgroup\$ – l4m2 Apr 22 at 10:22
  • \$\begingroup\$ @Bubbler If you don't use \b then it's not uncomputable \$\endgroup\$ – l4m2 Apr 22 at 10:24
  • \$\begingroup\$ I mean, if I want to revise an earlier digit, I can print a new number instead of overwriting the number. \$\endgroup\$ – Bubbler Apr 22 at 10:30
  • \$\begingroup\$ @Bubbler You mean the output method of this? \$\endgroup\$ – l4m2 Apr 22 at 15:32
  • \$\begingroup\$ Yes, something like that \$\endgroup\$ – Bubbler Apr 22 at 21:46
0
\$\begingroup\$

Write a fast-growing assembly function

Synopsis

Your goal is to implement the (asymptotically) fastest growing function within bounded code on a fictional CPU utilizing a quite limited, yet (probably) turing-complete instruction set.

Environment

The CPU utilizes unbounded RAM as well as two registers, the accumulator A and the program counter C, with words consisting of arbitrary integers, such that neither overflows nor underflows are possible. RAM is used to store data as well as code, allowing for self-modifying programs. Each instruction takes one parameter and therefore consists of two words; all instructions of your program are stored sequentially in RAM, starting at address 0. The following instructions can be used, P representing the parameter of the instruction:

Mnemonic Corresponding word Behavior
LOAD P 0 A := RAM[P]; C += 2
SAVE P 1 RAM[P] := A; C += 2
CNST P 2 A := P; C += 2
ADDT P 3 A += RAM[P]; C += 2
NEGA P 4 A := -RAM[P]; C += 2
JUMP P 5 C := P
JMPN P 6 If A <= 0 then C := P else C += 2.
HALT P every other number The program halts.

At each step, the instruction at address C will be executed using the parameter stored at C + 1. Both A and C will be initialized to 0 at the start of a program's execution. The word at -1 is supposed to be your input which can be guaranteed to be non-negative, other words not storing any instructions initially contain 0. The number stored at -2 will be considered your program's output, which must also be positive in all but finitely many cases.

Rules

At the initial state, your program may not occupy more than the first 2048 words, however, during execution, there are no bounds. Of course, you don't have to write your program in bytecode, using some assembly equivalent or ultimately any other language is fine as well, as long as you provide some rules/translator and show the result does not exceed the given bounds.

Every answer should come with some rough argument showing the program always halts, as well as some approximate lower bound on its growth rate. As the given space might very well suffice for some extremely fast-growing functions, it might be helpful to utilize the slow-/fast-growing hierarchy, as it provides a relatively simple way to compare two answers. Answers will be ranked by lower bounds that can be shown to hold.

Questions

I wonder what tags could be used in this case, atomic-code-golf, restricted-source and busy-beaver perhaps? Not entirely sure whether these fit. Also, is there any behavior left undefined? It doesn't seem like that's the case, but there might be some edge cases I forgot about.

\$\endgroup\$
7
  • \$\begingroup\$ 2048 words should be enough to run every possible program \$\endgroup\$ – l4m2 Apr 23 at 10:35
  • \$\begingroup\$ @l4m2 what do you mean by that? you surely can't just take the first <input> programs and run them, otherwise you'd have to solve the halting problem \$\endgroup\$ – univalence Apr 23 at 12:01
  • \$\begingroup\$ I mean there's, in any measure, way to make it better, in the 2048, and we don't want a "who say bigger number" game \$\endgroup\$ – l4m2 Apr 23 at 15:39
  • \$\begingroup\$ @l4m2 Ah, so you'd reduce the maximum size, correct? \$\endgroup\$ – univalence Apr 23 at 16:13
  • \$\begingroup\$ no, reducing to turing incomplete likely make it too weak \$\endgroup\$ – l4m2 Apr 23 at 16:44
  • \$\begingroup\$ @l4m2 not the RAM size, the allowed code length \$\endgroup\$ – univalence Apr 23 at 16:57
  • \$\begingroup\$ since this has been posted, it suggest shortening to one line and deleting to save sandbox space. \$\endgroup\$ – Razetime Apr 30 at 2:51
1
96 97
98
99 100
109

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .