493
\$\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 the first try can be difficult. There is a much better chance of your challenge being well received if you post it in the Sandbox first.

To post to the Sandbox, scroll to the bottom of this page or click on the "Add Proposal" link below, 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. 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, replace the post here with a link to the challenge and delete it.

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

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

| |
\$\endgroup\$

2996 Answers 2996

1
75 76
77
78 79
100
0
\$\begingroup\$

The Challenge

The goal is to write a complete program that prints out every possible tetris block made up of #.

The blocks must have an equal chance of printing in any order and must appear exactly once each. The blocks may have any rotation, rotation may be consistent between executions. No two blocks can be touching. All blocks must have settled on the "floor".

ValidExample.exe
                    #   #
## ###      ##   ## #   #
##  #  ####  ## ##  ## ##

TouchingExample.exe
      #
      #  # ##
## ####  #  # ##   ## 
##  # # ##  #  ## ##   

FloatingExample.exe
       #   #             
## ### ## ## #     # ####
##  #   # #  ### ###     

Use the language of your choice, lowest number of bytes wins

Questions

  • Is the wording clear enough?
  • Does the challenge meet the expectations for a challenge here?
  • What can I do to remove any ambiguity if there is any?
  • Is the formatting for the question / examples ok?
  • Would the challenge be "better" if the blocks had to be made up of their corresponding letter (IOJLZST)
| |
\$\endgroup\$
  • \$\begingroup\$ This could be a dupe of codegolf.stackexchange.com/questions/2223/polyomino-generator \$\endgroup\$ – Sok Mar 21 '18 at 9:22
  • \$\begingroup\$ @someone is the new wording better? Replaced random order with a requirement that each order have equal odds. \$\endgroup\$ – Southpaw Mar 21 '18 at 10:02
  • 1
    \$\begingroup\$ I think it is. I don't think the blocks-made-of-letters is a good idea. \$\endgroup\$ – the default. Mar 21 '18 at 10:04
  • \$\begingroup\$ @Sok No input, random order, only tetrominos, no floating restriction. Those seem to be the main differences. Are they enough to distinguish it? \$\endgroup\$ – Southpaw Mar 21 '18 at 10:05
0
\$\begingroup\$

Euler's Formula for the Quaternions

Euler's famous formula, e^iθ = cosθ + isinθ, can be used to calculate the exponential of arbitrary complex numbers: e^(a+ib) = e^a(cosb + isinb). That's cool and all, but what if we want to go even further?

The quaternions are an expansion of the complex numbers, where instead of just having i*i = -1, you have i*i = j*j = k*k = i*j*k = -1. Quaternions can be represented as a + bi + cj + dk or (s, v) where s is a scalar and v is a 3-Dimensional vector.

Euler's formula can be extended to the quaternions; for an arbitrary quaternion q = (s, v), e^q = e^s (cos|v|, (v/|v|)sin|v|), or, if q = a + bi + cj + dk and r = sqrt(b^2 + c^2 + d^2), e^q = e^a (cosr + (bi + cj + dk)(sinr)/r).

The task:

Write a program or function to exponentiate arbitrary quaternions. Built-ins are allowed. You may represent a quaternion in any sane manner.

Examples

Here, quaternions are represented as a four element array.

Input                                    Output (approximately)
0 3.14159 0 0                            -1
0 1 1 1                                  -0.160557 0.56986 0.56986 0.56986
1 2 3 4                                  1.69392 -0.78956 -1.18434 -1.57912
0.095767 0.601479 0.285658 0.926716      0.458433 0.527339 0.250447 0.812487
-0.654682 -0.925557 -0.409382 0.619391   0.194782 -0.37576 -0.166202 0.251462
| |
\$\endgroup\$
  • 1
    \$\begingroup\$ There's a missing ) in e^q = e^a (cosr + (bi + cj + dk)(sinr)/r \$\endgroup\$ – Peter Taylor Mar 23 '18 at 21:53
0
\$\begingroup\$

Brainfuck Compiler!

Your goal is simple: Compile brainfuck to x86 assembly (NASM style), and do it with as small of a program as possible. You will be able to choose your compiler's input and output model, as long as the input is brainfuck code and the output is NASM style x86 assembly.

The brainfuck code should read from STDIN and output to STDOUT

Your compiler must be fully compliant with no extensions, and must support a infinite (to the max the computer's memory can sustain, running out of space on either end can be treated as a crash.) number of unsigned 8 bit cells both forward and back, with the tape Your output assembly should provide the exact same outputs for the corresponding inputs as the brainfuck code.

Your program's output must be compilable to a ELF binary that runs on Linux using the NASM compiler. Your program will be linked with libc, so you can use any function in the C library.

What is Brainfuck?

Brainfuck is a language with 8 instructions, and a tape memory model composed of an infinite amount of unsigned 8 bit (1 byte) cells. The pointer always points to one of those cells, executing its operations on the current cell. Each instruction is executed one at a time, and are as follows:

  • + Increment the current value under the pointer
  • - Decrement the current value under the pointer
  • . Output the value under the pointer as an ASCII character
  • , Get a character from input, and wait until one is received.
  • > Move the pointer to the right
  • < Move the pointer to the left
  • [ Jump to the matching ] if the value under the pointer is 0
  • ] Jump to the matching [ if the value under the pointer is not 0

If a [ doesn't have a matching ] (or vice versa), you can consider that undefined behavior.

Anything not listed here should be considered a NOP, or in the case of a empty program (EOF), simply a blank, noncrashing program.

Test cases.

To allow competition, and varying compilation results, my test cases will show what each test program should output.

Program:

"++++++++++[>+++++++>++++++++++>+++>+<<<<-]>++.>+.+++++++..+++.>++.<<+++++++++++++++.>.+++.------.--------.>+.>."

Outputs (no input):

"Hello, World!"

Program:

+[,.]

Outputs:

"I am a test string" -> "I am a test string"

"Golfing is fun!" -> "Golfing is fun!"

Program:

`+[]`

Outputs:

Nothing. This program loops forever.

Program:

+[<+]

Outputs:

This program can be considered undefined behavior, because it will eventually run out of memory.

TODO

More test cases?

| |
\$\endgroup\$
  • \$\begingroup\$ is the tape left bounded? also you should specify input behaviour on EOF \$\endgroup\$ – Destructible Lemon Mar 26 '18 at 22:05
  • \$\begingroup\$ "to the max the computer's memory can sustain" -- I feel that requirement quite problematic. For example, a submission using 16-bit cell (and only use the lower 8-bit, for whatever reason) will only be able to handle half as many cells as one using 8-bit cell. \$\endgroup\$ – user202729 Mar 27 '18 at 0:55
  • \$\begingroup\$ @user202729 I'd say a submission like that would be rare enough it's a non issue. \$\endgroup\$ – moonheart08 Mar 27 '18 at 1:40
  • \$\begingroup\$ @DestructibleLemon The tape is unbounded, both left and right. \$\endgroup\$ – moonheart08 Mar 27 '18 at 1:40
  • \$\begingroup\$ For a doubly infinite tape, to the max the computer's memory can sustain definitely needs more clarification. For example, if I "run out of space" on the right end, but still have space on the left one, do I need to shift things around? \$\endgroup\$ – Dennis Mar 27 '18 at 1:42
  • \$\begingroup\$ Alright. I'll fix that now. \$\endgroup\$ – moonheart08 Mar 27 '18 at 1:43
  • \$\begingroup\$ I think it's better to use 1 side unbounded, as that's usually the convention i think \$\endgroup\$ – Destructible Lemon Mar 27 '18 at 2:02
0
\$\begingroup\$

Fill a virtual World Cup Sticker Album

As the World Cup is due to kick off (pun intended), the inevitable sticker book comes along as well.

According to this BBC article , at a cost of £0.80 for a pack of 5 and with a total of 682 stickers needed to complete the book it could cost up to £700 or more to fill, taking duplicates into account.

Write the shortest program possible to

  • Buy a virtual pack of stickers (at 0.80 per pack), which will be 5 random numbers between 1 and 682 (or 0 and 681)
  • Repeat until all numbers have been picked at least once
  • Output how many packs were bought and a final cost.

Output should be in the format "Bought number packets at cost of number"

Sample un-golfed Python 2 code

import random
total = 682
remain = total
cost = 0.8
spend = 0.0
packs = 0
got = [0 for i in range(total)]

while remain > 0:
    # buy a packet of stickers
    for i in range(5):
        got[random.randint(0,total-1)] += 1
    spend += cost
    remain = got.count(0)
    packs += 1

print 'Bought %d packs at cost of %.2f' % (packs,spend)

Sample output

Bought 865 packs at cost of 692.00

QUESTION

  • Writing the Python script for myself is what made me think of this question - does it help to include it, or clutter the page? (This is my first attempt at a question here)
| |
\$\endgroup\$
  • \$\begingroup\$ You need to flesh out what we're doing? Your code isn't super greatly commented and I'm not sure how much a pack costs, how many packs are needed. etc. should it always output the same amount? \$\endgroup\$ – Rɪᴋᴇʀ Mar 29 '18 at 20:57
  • \$\begingroup\$ What does "simulate" mean here? Beware the curse of the non-observable requirement. \$\endgroup\$ – Peter Taylor Mar 29 '18 at 22:28
0
\$\begingroup\$

Navigate my Taxi

Introduction

Taxi is an esoteric programming language simulating a taxi. You can pick up passengers (values) and drop them at special places to modify them. For example, this program squares the input. The places are all in Townsburg:

Map of Townsburg

To travel from one place to another, you have to tell your taxi where to go:

Go to the Post Office: west 1st left, 1st right, 1st left.

And you need gas to drive, your car gets 18 miles per gallon. So it's best to find the shortest possible way between two places. That leads me to ...

The Challenge

Input

You get an incomplete Taxi program, consisting of the following statements:

  • Pickup a[nother] passenger going to [the] <place>.: Pickup a passenger, you may ignore it for this challenge
  • "<string>" is waiting at [the] Writer's Depot. / <number> is waiting at [the] Starchild Numerology.: Create passengers, you may ignore this, too
  • Go to [the] <place>.: Go to a place, you have to add directions (see below)
  • [<label>]: A label for jumping, you have to parse those to know where the taxi is. They don't do anything if passed. You can assume that you are in the same location, regardless of where you reach the label from.
  • Switch to plan "<label>".: Unconditional jump, follow these to know where the taxi is
  • Switch to plan "<label>" if no one is waiting.: Conditional jump, you have to support both ways

If the input program contains anything else, you may do anything you want (undefined behaviour).

Conversion

Following all jumping instructions, you have to add directions to the Go to commands. It has to be the shortest possible way (I want to save gas!)

Directions consist of a cardinal direction (north, east, south, west or NESW) and a comma-separated list of turns, consisting of a number (1st 2nd 3rd or 1 2 3) and left/L or right/R.

Examples:

Go to the Post Office: west 1st left, 1st right, 1st left.
Go to Post Office: W 1 L, 1 R, 1 L.
Go to Tom's Trims: N.

The cardinal directions do have the following meanings (xstart means x pos of the starting point, yend means y pos of the next corner/intersection/place):

  • north: ystart > yend
  • south: ystart < yend
  • west: xstart > xend
  • east: xstart < xend

(Coordinates from the top left corner)

Here is a list of all intersections/corners/places/streets, extracted from the interpreter.

Some additional info:

  • The taxi starts at the Taxi Garage.
  • If the taxi reaches the Taxi Garage, the program ends.
  • If the program reaches its end and the taxi is not in the Taxi Garage, that's an error, so you'll have to add 'Go to the Taxi Garage: ...' at the end if it's missing.

Output

  • Your program or function has to output a valid Taxi program (online interpreter) or a list of instructions (which, when concatenated, form a valid Taxi program)
  • You may use the long (north 1st left) or short (N 1 L) syntax.
  • The ways chosen have to be the shortest possible (droven distance, i.e. sum of Euclidian distances between any two consecutive points on your way)
  • If there are multiple equally long ways, you can use any of them

Additional Rules

  • Standard loopholes are forbidden
  • Your score is the number of bytes in your program
  • Lowest score wins

Test Cases

TODO

  • Is any part of the specs confusing?
  • Should I not input a full program, but just start and destination?
  • Should I add the map in some format as an additional input?
| |
\$\endgroup\$
  • \$\begingroup\$ Thanks for using the sandbox, but I'm sorry that it's not very active. We decided that "typical desktop computer" is not clear enough, so you should change it. \$\endgroup\$ – user202729 Feb 24 '18 at 14:54
  • \$\begingroup\$ What is "shortest" measured in? Euclidean distance? What if there are multiple equally long paths? \$\endgroup\$ – user202729 Feb 24 '18 at 15:09
  • \$\begingroup\$ @user202729 Edit: time is now on TIO, distance is sum of Euclidian distances between any two consecutive points on the way. I'm thinking about writing a program that calculates the distance \$\endgroup\$ – wastl Feb 24 '18 at 16:37
  • \$\begingroup\$ TIO is still not usable for time-related things. See codegolf.meta.stackexchange.com/questions/12707/… . \$\endgroup\$ – user202729 Feb 24 '18 at 16:39
  • \$\begingroup\$ Is it guaranteed that the taxi will be in the same location regardless of how we reach a label? \$\endgroup\$ – Nitrodon Feb 24 '18 at 17:08
  • \$\begingroup\$ @user202729 Ok, removed time limit \$\endgroup\$ – wastl Feb 24 '18 at 17:09
  • \$\begingroup\$ @Nitrodon finally, I got what you meant. Sure. Although theoretically, if both points lie on one street, one could do that ... (I would not recommend it) \$\endgroup\$ – wastl Mar 16 '18 at 23:02
0
\$\begingroup\$

Left Turn at Euqreuqebla

Write a quine, according to the standard definition of a quine, that outputs itself when executed. However, when your code is reversed it should output each character of your source code separated by a newline instead.


Example

If your program was:

ABCDEFGH
IJKLMNOP

The unedited program should output:

ABCDEFGH
IJKLMNOP

However the reverse of the program should output:

A
B
C
D
E
F
G
H


I
J
K
L
M
N
O
P

Rules:

  • Outputting a single trailing or preceding newline is acceptable.
  • If your code contains newlines, they do not require rotation, treat them regularly.
  • Standard loopholes are disallowed.
  • Ensure that your "quine" is actually a quine.
  • This is , ; lowest byte-count wins.
| |
\$\endgroup\$
  • \$\begingroup\$ an example with code with newlines would be useful (as those I'd naturally rotate 90 degrees :p) \$\endgroup\$ – dzaima Mar 29 '18 at 21:04
  • \$\begingroup\$ @dzaima which way do you think is better, not requiring "natural rotation" to support Java and the like better? Or supporting natural rotation for the esolangs? \$\endgroup\$ – Magic Octopus Urn Mar 29 '18 at 21:07
  • \$\begingroup\$ a thing to consider is that if natural rotation would be required, everyone would just try to keep everything in a single line to make the challenge way easier \$\endgroup\$ – dzaima Mar 29 '18 at 21:10
  • \$\begingroup\$ @dzaima I could make it optional? I don't see that hurting the challenge too much either way to be honest, it just lets languages to what they do best. \$\endgroup\$ – Magic Octopus Urn Mar 29 '18 at 21:11
  • \$\begingroup\$ that'd be a good compromise if there's no better solution \$\endgroup\$ – dzaima Mar 29 '18 at 21:12
  • \$\begingroup\$ @dzaima ehhh? decent? \$\endgroup\$ – Magic Octopus Urn Mar 29 '18 at 21:17
  • \$\begingroup\$ usually it's bad to have multiple ways to solve the challenge, though here it's pretty easy to tell which method's gonna be the easiest \$\endgroup\$ – dzaima Mar 29 '18 at 21:18
  • \$\begingroup\$ @dzaima exactly, that's why I want to allow it to see if SOGL or some other language with crazy flipping commands can do this the "harder" way. \$\endgroup\$ – Magic Octopus Urn Mar 29 '18 at 21:19
  • \$\begingroup\$ If you're going for Albuquerque spelled backwards, that's not how it's spelled. \$\endgroup\$ – AdmBorkBork Mar 30 '18 at 13:25
  • \$\begingroup\$ Shouldn't the example have a gap of three newlines between the H and the I, not two? \$\endgroup\$ – praosylen Apr 1 '18 at 0:00
  • \$\begingroup\$ @AidanF.Pierce great catch. \$\endgroup\$ – Magic Octopus Urn Apr 2 '18 at 11:50
0
\$\begingroup\$

Radioactive Quine Sums

Related: Radioactive Quines

Challenge

Write a program that takes an integer as input and....

  1. When the program is run it outputs the input.
  2. When you split the program in half, each sub-program should take as input the output of the original program, and output a number. The sum of the two numbers should equal the output of the original program.
  3. Repeat the procedure with each valid sub-program.

Your score is byte count/[valid programs]2 (lowest score wins).

Specs

  1. When you split an odd-length program in half, the program on the left gets the extra character.
  2. For a sub-program to be valid, the sum of its output and its pair's output must be the input, for every possible input n, -100≤n≤100.
  3. A sub-program that doesn't compile/doesn't output a number is invalid (along with its pair).
  4. If a program is invalid, it can't be split further.
  5. A program that outputs "0" for more than one input can't be split further.

Testcases

Pseudo-langauge: A adds a 0 to the stack, Q adds the input to the stack. - negates the element to the right of it.The output is the sum of the stack elements.

  1. Q Score: 1/1 = 1
  2. AQ Score: 2/3² = .222 (AQ -> input, A + Q -> 0 + input)
  3. AAQ Score: 3/3² = .333 (AAQ -> input, AA + Q -> 0 + input) [Since the output of AA is 0, you can't split it any further]
  4. QAA Score: 3/5² = .12 (QAA-> input, QA + A -> input + 0, Q+A -> input +0) [Since QA -> input, Q and A are valid sub-programs, since the sum of their outputs equals the output of QA.]
  5. QAQ Score: Infinity [Since QAQ outputs 2*input, it is invalid and can't be split further.]
  6. QQ-Q Score: 4/5² = .16 (QQ-Q -> input+input-input,QQ+-Q -> (input+input)+(-input), Q+Q->input+input, -+Q->error) [Q and Q are valid subprograms of QQ because the sum of their outputs is 2*input, which is the output of QQ.]

Feedback Appreciated

| |
\$\endgroup\$
  • \$\begingroup\$ 0=0+0=(-1)+1, why can't it be splitted further? \$\endgroup\$ – user202729 Apr 2 '18 at 6:38
  • \$\begingroup\$ @user202729 because someone would just leave it always zero \$\endgroup\$ – l4m2 Apr 2 '18 at 15:30
  • \$\begingroup\$ However I still think score->0 solution exist, so \$\endgroup\$ – l4m2 Apr 2 '18 at 15:31
  • \$\begingroup\$ For 0=(-1)+1: Language W=output the input 0=output zero Q=quit WQ0Q0Q0Q0Q0Q0Q0Q has low score \$\endgroup\$ – l4m2 Apr 2 '18 at 15:33
  • \$\begingroup\$ @l4m2 and user202729 look at rule 5 in Specs. \$\endgroup\$ – geokavel Apr 2 '18 at 17:01
  • \$\begingroup\$ @geokavel we know the rule, just analysing whether they are good here \$\endgroup\$ – l4m2 Apr 2 '18 at 17:03
  • \$\begingroup\$ @l4m2 yeah, i see your point about WQ0Q0.... scaling infinitely. \$\endgroup\$ – geokavel Apr 2 '18 at 17:04
0
\$\begingroup\$

Heroes of Might and Magic 0: A Numerical Boxing Match

It's time to program a game!

Well not a game, precisely. More of a stripped-down version of a game, without graphics or real-time input... or really much of anything. But it'll modify numbers on screen, and isn't that why we play games in the first place?

To elaborate:

If you're unfamiliar with the Heroes of Might and Magic franchise, here's the very most basic workings of the combat system: A stack of creatures of a single type (say, 2 green dragons or 1000 marksmen) will simultaneously attack another stack of creatures of a single type. Each creature does a specific amount of damage, and that's reflected in how many troops in the opposing stack die.

For example, let's have 5 angels vs. 100 skeletons, and let's have the angels go first. If they hit 50 damage each, then 5*50 = 250 damage will be done to the skeletons. If the skeletons each have 10 health, then 250/10 = 25 skeletons will perish, leaving 75.

Next, the skeletons attack. If the skeletons deal 2 damage each and angels have 100 health each, the skeletons will do 2*75 = 150 damage to the angels. But how can we kill 150/100 = 1.5 angels? What happens is that one angel will die, and then the remaining 150-100 = 50 damage is dealt to the top angel in the stack. This angel will be the first to receive damage on the next round and will only require 100-50 = 50 damage to die, but can still deal damage like normal in the meanwhile.

Then angels attack skeletons, skeletons attack angels, angels attack skeletons... repeat until only one stack of creatures remains!

There are loads of other mechanics involved in actual combat, but the fundamental one is attacking, and that's what you'll be programming today.

Technical Specification

Two stacks of monsters will be attacking each other. Each of these stacks has three properties:

  1. Size, positive integer. This is how many total monsters are in the stack.
  2. Health, positive integer. This is how much damage is needed to kill ONE.
  3. Damage, positive integer. This is how much damage EACH monster in the stack will deal.

When a stack of monsters A attacks a stack of monsters B, all of the monsters attack, dealing

A_size * A_damage

total damage. This kills a total of

floor(A_size * A_damage / B_health)

monsters in B. If the damage dealt isn't an even multiple of B_health, then the remaining

(A_size * A_damage) - (B_health * floor(A_size * A_damage / B_health))
= (A_size * A_damage) % B_health

damage is dealt to the top monster in B, which will persist into the next round.

Input

You'll receive two groups of three numbers, each of which contains information about one stack of monsters: The total number, the health of each individual, and the damage dealt by each individual.

[(A_size, A_health, A_damage), (B_size, B_health, B_damage)]

You can receive this as two lists/tuples/arrays of three, six separated values in a single line, or six newline-separated values. The first group of numbers represents the monster that attacks first.

Output

After the fight is finished, you must output the number of remaining troops in the winning stack.

Examples

Input: [(1000, 10, 2), (500, 15, 3)]
Output: 763

Input [(1, 2, 3), (4, 5, 6)]
Output: 4

Input [(100, 100, 1), (100, 100, 1)]
Output: 10

Lowest byte count wins!

Feedback

  • Is the challenge clear? I feel like it's simple and maybe I'm being too verbose in explaining it, but maybe it isn't.
  • Are there any other good ways to accept input?
  • Does it seem like it'd make a fun challenge? If not, are there any changes I could make to make the challenge more interesting?
  • Anything else?

Thanks everyone!!

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

See all the blocks

In a 3D coordinates, a block (a,b,c) takes the place of x<a<x+1, b<y<b+1, c<z<c+1.

  1. Is there a point that can see every block? (Exist point P, For each block K exist point Q, segment PQ don't go across any block but K)
  2. Is there a way that can see every block? (Exist non-zero vector w, For each block K exist point Q, for each positive number t, Q+wt is not in other blocks than K)

Output four values to represent the four possibles.

Shortest code in bytes win.

| |
\$\endgroup\$
  • 2
    \$\begingroup\$ Although the challenge idea is good, we generally expect people to make the challenge reasonably-complete in the sandbox ("write your challenge just as you would when actually posting it"), and not just the ideas. (for example: what is the winning criteria?) \$\endgroup\$ – user202729 Apr 4 '18 at 6:55
  • 2
    \$\begingroup\$ Also, it appears that there are 2 different challenges here that needs to be solved in very different ways. Consider having 2 different posts. \$\endgroup\$ – user202729 Apr 4 '18 at 6:56
0
\$\begingroup\$

Write a program that, in different languages, output a different permutation(the exact source is counted as one permutation) of the code.

Proper quine rule apply. Largest (Language count)^6/(Code length) win.

Sample: If your code is AAB and running in several languages return ABA, AAB, AAB, then its score is 2^6/3.

| |
\$\endgroup\$
  • 2
    \$\begingroup\$ "Shuffle" implies randomness. I'm assuming that this isn't what you want: "Ordering" is a better term: You want a set of programs that output the same bytes, but in different orders. \$\endgroup\$ – Nathan Merrill Apr 7 '18 at 5:31
  • \$\begingroup\$ Or "permutation". \$\endgroup\$ – user202729 Apr 7 '18 at 6:08
  • \$\begingroup\$ Do the output need to be valid (executable) source code or it may be mess of reordered characters? \$\endgroup\$ – tsh Apr 8 '18 at 6:46
0
\$\begingroup\$

The 3n+1 problem

The legendary problem in UVa Online Judge, with over 775k submissions and over 85k people who solved it. I, personally, have solved it in many ways, even reaching the best time below 0.01 sec.

Even though the problem is interesting from the algorithmic point of view, insofar as reasonable time constraints would be easily able to force people to think about some sane approach to caching and use data structures like the segment tree, it is actually not the case here: the time constraints, on UVa, are so lax that even a purely naive algorithm is accepted by the judge. Since we are on CodeGolf and not on a programming contest, we aim here to write shortest code, and not necessarily fastest one, so for most part you don't need to care about performance - that is, as long as it is not horrible even beyond the lax allowances of the online judge; more on that below.

The input

The input will consist of several lines, each containing a pair of integers i and j, such that 0<i,j<1,000,000.

The output

For each line of input, you are to print one line of output that will consist of integers i and j, in that order, followed by one number that will denote the maximum length of the Collatz sequence (also known as the 3n+1 sequence), over all numbers between and including i and j. Note that while in mathematics the terminal number 1 usually doesn't count to the length of the sequence, in this problem it does.

The Collatz sequence is defined as follows: If an is odd, then an+1:=3*an+1; or, if an is even, then an+1:=an/2. The sequence ends when it reaches number 1.

Sample input (taken from UVa):

1 10
100 200
201 210
900 1000

Sample output (taken from UVa):

1 10 20
100 200 125
201 210 89
900 1000 174

Additional notes:

  • There is no guarantee that i<=j. The input may contain lines with i>j. However, even in these cases, you are supposed to print out i and j in the output in the correct order (that is, i comes before j, not min(i, j) before max(i, j).
  • There is a guarantee that, while computing the Collatz sequence terms, no term will overflow a 32bit integer.
  • As of now, the problem specification gives incorrect input boundaries, claiming that all numbers will be less than 10,000. The correct bound seems to be 1,000,000 instead, which is present in the archived version of the problem specification. Since last time I checked the judge required accepted programs to be able to process numbers up to 1,000,000, we retain that requirement in our problem.
  • Your program must perform actual computations. Hardcoding all sequence lengths for numbers between 1 and 1,000,000 is unacceptable. So is fetching them from external sources.
  • Your program must read from standard input and write to standard output. Your program must format its output as required by UVa Online Judge for this program.
  • Of course, we do not retain the original harsh requirements on acceptable programming languages. Any programming language is OK as long as it doesn't violate the standard loopholes.
  • Your program must correctly process all lines until EOF and then exit gracefully. Your program must not wait endlessly on EOF, enter an infinite loop on EOF, crash on EOF, exit with an error, etc.
  • Performance restrictions:
    • Basically, the intention is to allow everything but most horribly underperforming programs.
    • To be more specific, the naive algorithm that, for each line of input, computes once the whole sequence for each number in the required range is allowed (example of an allowed program). It is also allowed to keep an array caching lengths of all sequences starting with numbers from 1 to 1,000,000 (example of an allowed program), or to keep a dictionary caching lengths of all sequences starting with any encoutered numbers so far (example of an allowed program); however, it is not allowed to keep an array caching all encountered lengths, since that array would be unreasonably sparce and thus unreasonably large (example of a disallowed program); it is also not allowed to precompute a 1,000,000x1,000,000 array that would keep all maximums of lengths in all valid ranges (example of a disallowed program). Your program may precompute lengths even for numbers that would otherwise be disallowed by the guarantee of not overflowing a 32bit integer (example of an allowed program), if you wish.

Shortest code wins.

| |
\$\endgroup\$
  • 4
    \$\begingroup\$ From a golfing perspective, this looks like basically the usual Collatz challenge, taking the max over an interval but with Cumbersome I/O and non-observable performance requirements. \$\endgroup\$ – xnor Apr 8 '18 at 7:03
  • \$\begingroup\$ @xnor , I don't think these requirements are non-observable, my intention was to disallow everything the judge disallows without imposing the programming language restrictions; anyway; a 1,000,000x1,000,000 array of integers is around 3.5TB!! - I think disallowing this makes sense? Basically my intention was to prevent saying that "In a computer with unlimited resources this program would complete and is therefore valid". If I want to disallow this, am I supposed to rather prepare my own test case and run the program on my computer to see if it fits in reasonable time/space requirements? \$\endgroup\$ – gaazkam Apr 8 '18 at 12:56
  • 2
    \$\begingroup\$ I think I'm not understanding the restrictions then -- is what you intend is just a hard bound on run-time and memory, and the types of programs that work are just examples? Regardless though, I expect it not to matter as golfed programs will just compute the whole sequence for each number in the range, which you allow. All the optimizations seem like they'd take more characters. \$\endgroup\$ – xnor Apr 8 '18 at 23:45
  • 1
    \$\begingroup\$ ... yes, to have such requirements you have to run it yourself (or ask someone to do this for you) Although, if as you said (almost every algorithm) are allowed, what's the point in having another challenge? I would call this a dupe. \$\endgroup\$ – user202729 Apr 9 '18 at 15:13
  • \$\begingroup\$ One more point: If there exists a programming language where hardcoding 10⁶ terms is shorter than computing them, you should reconsider the challenge. \$\endgroup\$ – user202729 Apr 9 '18 at 15:14
0
\$\begingroup\$

___ encrypting

Given two text a and b, both contain only lowercase letters

  1. Write each charactor in a into 5 digits of binary (a => 00001, z => 11010)
  2. Write each charactor in b where such place of the binary list is 1 is written into a different style (uppercase, bold, etc., but should be consistant)
  3. If some char remain in b, either keep them all in the 0 style or remove them. You can assume b has enough chars.

Sample:

a = cat, b = programmingpuzzlescodegolf

  1. Write a into binary 000110000110100
  2. So the output can be proGRammiNGpUzz, proGRammiNGpUzzlescodegolf, programmingpuzzlescodegolf, etc.
| |
\$\endgroup\$
  • \$\begingroup\$ You should probably mention a specific win condition. \$\endgroup\$ – Nissa Apr 10 '18 at 13:07
0
\$\begingroup\$

A Magic Ritual

Given an input string N perform a sequence of steps.

  1. Delete all spaces from the string.
  2. Delete all other occurrences that come after the first one of the same letter from the string.
  3. If the string contains the letters needed for zero, delete these letters and add the corresponding digit 0 to the end of the string. Repeat this for 0 to 9.
  4. Order the characters left in the string by the alphabet, then by their numeric values.

Input

May be received as a string, an array of characters or any other reasonable input for text.

You may assume that the input will only consist of characters including a-z (lowercase) and spaces.

Output

Same as input, or may be directly written to stdout.

Rules

  • This is , the shortest code in terms of bytecount wins.
  • Standard loopholes are forbidden.

Test Cases

a magic ritual -> acgilmrtu
sixone -> 16
codegolf -> cdefglo
the quick brown fox jumps over the lazy dog -> abcdfghjklmnpqtuvwy06
qwertyuiopasdfghjklzxcvbnm -> abcdfghjklmnpqtuvwy06
| |
\$\endgroup\$
  • \$\begingroup\$ Do second occurrences include 3rd 4th etc? \$\endgroup\$ – l4m2 Apr 10 '18 at 8:14
  • \$\begingroup\$ @l4m2 Yes, I'll clarify. \$\endgroup\$ – Ian H. Apr 10 '18 at 8:15
0
\$\begingroup\$

Count the Matches


Given a stripped-down regular expression, estimate (rules below) the number of lower-ASCII-only strings that it matches fully (meaning it matches the whole string).

You should handle the following:

  • Literals/sequencing
  • Vertical bars ...|...
  • Groups (...) or (?:...)
  • Special characters escaped with a preceding \
  • Character classes [...]
  • Complemented classes [^...]
  • The standard classes ., \d, \w, \s, \D, \W, and \S
  • The escape sequences \f, \n, \r, \t, and \xhh
  • The quantifiers ?, {x}, and {a,b}

Estimation Rules

Literals

Literals, obviously, match only one string.

aaaaa --> 1

Classes

The estimate for a class is the number of characters that it can match. If multiple are seen, then their individual counts can be multiplied. There are also the standard classes: \d is [0-9], \w is [_A-Za-z\d], and \s is [ \n\t\r]. \D, \W, and \S are the complements of their lowercase versions.

a.b --> 127
\D --> 118
[a-gd-k] --> 11
[^\w$A] --> 64
[abc][xyz] --> 9
\d\d\d --> 1000

Switches

Switches (vertical bars) should be estimated as the sum of the component expressions.

a|a --> 2
a|b --> 2
(0|1)[01] --> 4
0|1[01] --> 3
optional| --> 2

Quantifiers

With a static quantifier, you can treat it as a power function. With a variable quantifier, you can use the geometric sequence formula to get the estimate:

a1 is the first term, in this case the estimate at the lower bound. r is the common ratio, for which you should use the estimate for the group quantified. n is the number of terms, which is the upper bound minus lower bound plus one for the quantifier.

[01]{10} --> 1024
.? --> 128
[01]{3,10} --> 2040
0|[12]{3} --> 9
(0|[12]){3} --> 27
\d{30,40} --> 99999999999000000000000000000000000000000
(?:a{2,3}){2,3} --> 12

Shortest code in bytes wins.

| |
\$\endgroup\$
  • \$\begingroup\$ The examples require support for sequencing, which is not listed as something which must be supported. The standard classes with upper case are not explained. (?:...) is mis-labelled: it's a non-capturing group. \$\endgroup\$ – Peter Taylor Apr 12 '18 at 10:49
  • \$\begingroup\$ Also what's the charset? 0-127? \$\endgroup\$ – l4m2 Apr 12 '18 at 14:49
  • \$\begingroup\$ @l4m2 it's lower ASCII, so yes. \$\endgroup\$ – Nissa Apr 12 '18 at 15:54
  • \$\begingroup\$ ASCII sometimes onlt mean 32-126 though \$\endgroup\$ – l4m2 Apr 12 '18 at 17:19
  • \$\begingroup\$ @l4m2 that's printable ascii. \$\endgroup\$ – Nissa Apr 12 '18 at 17:27
0
\$\begingroup\$

Tell SMILES from FROWNS


The Simplified Molecular-Input Line-Entry System file format is used to store structures of organic molecules. For information on why there is an actual file format called "smiles", consult this comic from PhD Comics. As a summary of the format:

  • Start the file with a root chain of atoms.
  • Put each branch group in parentheses after the atom it connects to.
  • Use = for a double bond and # for a triple bond.
  • Break aromatic rings and number the bonds broken; add those numbers after the atoms bordering them.
  • Put metal atoms and any ions in square brackets.
  • Omit hydrogens attached to carbons. Their presence is assumed.

For example, 1-chloro-3-ethylbenzene could be C=1(CC)C=CC(Cl)=CC=1.

Challenge

Let's make a new acronym, FROWNS: Fraudulent, Ridiculous, Overbonded, Wacked, or Nonexistent SMILES. Basically, a SMILES string is a FROWNS string if any of the following apply:

  • A loop is unclosed or closed twice.
  • An atom from period 2 (Li, Be, B, C, N, O, F, Ne) has more than 4 total bonds.
  • A neutral nitrogen atom has 4 total bonds.
  • An oxygen atom has more than 2 difference of bonds - charge.
  • A fluorine atom has anything other than exactly 1 bond.
  • Noble gasses other than xenon are bonded.

Your program should determine whether a given SMILES string is a FROWNS string.

Here are some examples of FROWNS:

C1=CC=CC=C
CC(C)(C)(C)C
C1=CC=CC=C1C=CN1
C#C#C
C=N=C
CC#O
OFO
FKr(F)(F)(F)(F)F
FXeF(F)(F)

These, however, are not FROWNS:

C1=CC=CC=C1
CC(C)(C)C
C12=CC=CC=C1C=CN2
C#C
C[N-]C
CC=O
OClO
FXe(F)(F)(F)(F)F
Xe(F)(F)(F)(F)

May the shortest code win.

| |
\$\endgroup\$
  • 1
    \$\begingroup\$ SMILES is a relatively complicated format, so it might be a good idea to define your own subset of it and set it out in the question, so that people don't have to worry about whether they have to implement aromatic bonds or stereochemistry or what have you \$\endgroup\$ – Nathaniel Apr 13 '18 at 15:53
  • \$\begingroup\$ @Nathaniel my subset called FROWNS is somewhat strictly defined, so that shouldn't be a problem. \$\endgroup\$ – Nissa Apr 13 '18 at 17:50
  • 1
    \$\begingroup\$ I don't think it's well defined enough. Is F/N=N/F a FROWNS string, for example? Technically yes, because it is a SMILES string containing an N with 4 bonds. But do you really need people to support stereochemistry for this challenge? I don't think you do, which is why I suggest you define your own subset of SMILES instead of relying on the relatively complex standard. This will also have the advantage that people won't need to understand organic chemistry to compete in the challenge. \$\endgroup\$ – Nathaniel Apr 15 '18 at 4:29
0
\$\begingroup\$

Rock, Paper, Scissors, Load, Shoot, Block, Mirror, Plasma-shot, Ammo-block, Punch, Bazooka, Super load, and so on and so forth

This is an abomination of a challenge. Two bots are fighting to the death, but the rules keep changing.

Each turn both bots have the same set of 3 random actions from this list as their input:

L - Load. Gives you 1 ammo.

S - Shoot. Costs 1 ammo, you win.

B - Block. Prevents the opponent from winning this turn

P - Paper. If your opponent chooses the first option in the list, you win.

C - Scissors. If your opponent chooses the second option in the list, you win.

R - Rock. If your opponent chooses the third option in the list, you win.

H - Punch. You win.

A - Plasma. Costs 2 ammo, you win

O - Ammo Block. Costs 1 ammo, prevent the opponent from winning this turn

Z - Bazooka. Costs 3 ammo, you win. This cannot be blocked.

E - Ammo Paper. Costs 1 ammo, if your opponent chooses the first option in the list, you win.

X - Ammo Scissors. Costs 1 ammo, if your opponent chooses the second option in the list, you win.

K - Ammo Rock. Costs 1 ammo, if your opponent chooses the third option in the list, you win.

U - Super Load. Gives you 2 ammo.

D - Defeat. Instantly Lose.

I - Strike. Prevent your opponent from winning. If your opponent wasn't trying to win, you win.

N - Nothing. Does nothing.

M - Mirror. If your opponent would win, you win instead.

W - Wild. Allows you to do anything.

T - Take. Take 1 ammo from your opponent.

G - Gloat. Win if you have more ammo than your opponent

J - Joker. Does a random action.

Q - Quintuple Load. Gives you 5 ammo.

Y - Lucky. 50/50 chance of winning or losing.

V - Victory. Win the game, unblockable.

Each bot must choose 1 action to do. Actions happen simultaneously, and if two players win at the same time, then the player who spent more ammo to win is the winner (So a Punch would lose to a Plasma).

NOTES

Each bot is played 1000 times against every other bot. The winner is the bot with the most total wins.

The 3 actions are selected before each turn. Actions can appear multiple times ("PPB" is possible).

Your bot can see what the opponent did, the set of actions available, ammo counts, and move histories.

If you don't have enough ammo, then your action is treated as an N.

If you choose an invalid action, then you lose.

| |
\$\endgroup\$
  • \$\begingroup\$ Some things to consider: Do bots start with no ammo? This could be a problem if the first round picks only ammo moves. Why is nothing an option? Maybe nothing can be a "no move" pick to avoid forced suicide when no ammo is left. How do RPS work if the there are multiple options? Can bot 1 pick P1 and bot 2 pick P2, giving 2 the win? What is the difference between Joker and Wild? What is the point of an ammo-costing block? Currently doesn't seem to do anything. Mirror is likely to cause only draws since there's (hardly) any reason to pick anything else. Strike is similar. cont. \$\endgroup\$ – aoemica Apr 18 '18 at 6:30
  • \$\begingroup\$ Do Lucky/Coin Flip (duplicate effect by the way) cause your opponent to win, or just you to not win? Load, super load, and take don't seem to be often worth a turn. Is there ever a reason to play defeat? I think you should focus a bit more on the core ammo preservation/more ammo beats less ammo theme. Personally I feel that right now there are too many unrelated/underpowered moves that water down the best aspects of this challenge. Going with an unweighted random pick, ammo consumption in moves seems way higher than ammo resupply allows. \$\endgroup\$ – aoemica Apr 18 '18 at 6:41
  • \$\begingroup\$ And along with that pile of questions, welcome to the site! \$\endgroup\$ – aoemica Apr 18 '18 at 6:51
  • \$\begingroup\$ If the only inputs are 3 of the differents actions, how are we able to know opponent informations ? \$\endgroup\$ – The random guy Apr 18 '18 at 7:32
  • \$\begingroup\$ "if two players win at the same time, then the player who spent more ammo to win is the winner (So a Punch would lose to a Plasma)" but what if they both play the same 'winning' move? \$\endgroup\$ – Nathaniel Apr 18 '18 at 8:29
  • \$\begingroup\$ @aoemica Yeah I kind of wrote them all down at 10 o clock trying to get one for every letter in the alphabet, so there were bound to be some mistakes. First of all, Joker does something random, while Wild means any action can be chosen (With "PBW" you can choose "M" because of the wild). Lucky can cause you to lose. I'm probably going to replace Coin Flip with Four Load, so you can get more ammo. Rock Paper and Scissors are based on the order. For example, "RNH" means that Rock would beat Punch. It's based on the order "RPS". I'm also going to remove the negative ammo thing. \$\endgroup\$ – JacksonMerg Apr 18 '18 at 13:00
  • \$\begingroup\$ @aoemica About the Ammo block, it is pointless if you can do Block, but because the actions you can do are random, you might get Ammo block without Block. \$\endgroup\$ – JacksonMerg Apr 18 '18 at 13:04
  • 4
    \$\begingroup\$ -1 This challenge has too much randomness, and requires the bot to understand all of those rules to be competitive. \$\endgroup\$ – Nathan Merrill Apr 18 '18 at 15:08
  • 3
    \$\begingroup\$ What does "unblockable" mean? Is Mirror blocking? Strike? \$\endgroup\$ – Nathan Merrill Apr 18 '18 at 21:13
  • 1
    \$\begingroup\$ This is too complicated. I suggest reducing it to the first 6 items on the list, which should all be available at all times. Or better yet, have the Rock/Paper/Scissors + load variants, shoot, and block \$\endgroup\$ – Beefster Apr 19 '18 at 18:53
0
\$\begingroup\$

Do other programming languages allow post-assignment, like R? Can you force it?

In many programming languages assignment works like this, where a value such as 5 is assigned to x.

int x = 5; // C++

x = 5 # etc ... // Python 

But in R, you can do this (and this is the first I've ever heard of this):

5 -> x # where 5 is assigned to x in reverse order.

This has some advantages. You can do several operations and then save the results to a variable at the end, stopping the operations. As an example,

library(dplyr) # allows then (%>%) statements 

(1:10) %>% square() %>% sum() -> y

where I define an array of numbers 1 to 10: {1, 2, 3, 4, 5, 6, 7, 8, 9, 10},

square each of those: {1^2, 2^2, 3^2, 4^2, 5^2, 6^2, 7^2, 8^2, 9^2 , 10^2},

sum up the sequence 1^2 + 2^2 + 3^2 + 4^2 + 5^2 + 6^2 + 7^2, 8^2 + 9^2 + 10^2

and assign that sum of squares to variable y.

y holds a value of 385, matter of fact.

To do something like that, though I would have to define a square function:

square <- function(x){return(x * x)}

You assignment is to create a post-assignment overloaded operator like "->" which allows assignment like 5 -> x.

Bonus points if the overloaded assignment operator is variable type insensitive, working on numbers, characters, strings, etc ...

| |
\$\endgroup\$
  • \$\begingroup\$ This will need an objective winning criterion. \$\endgroup\$ – Nathaniel Apr 25 '18 at 9:32
  • 3
    \$\begingroup\$ It'll need to be more tightly specified as well? E.g. what precisely counts as 'a post-assignment overloaded operator like "->"' and what doesn't? Bear in mind that the concept of "overloaded operator" doesn't exist in a lot of languages. \$\endgroup\$ – Nathaniel Apr 25 '18 at 9:33
  • 1
    \$\begingroup\$ I don't see the advantage in your example. C# can do var y = Enumerable.Range(1,10).Select(x => x*x).Sum() which seems to accomplish the same thing without needing post-assignment. \$\endgroup\$ – Kamil Drakari Apr 25 '18 at 16:12
0
\$\begingroup\$

Go Fish!


"Go Fish" is a childhood card game where you try to obtain pairs by either drawing from the deck or taking them from the other players.

The rules can vary by who you ask, but the rules that this challenge will use are these:

  • Everyone starts with a hand of five cards.
  • Play goes in a circle.
  • On your turn, you can call a card and another player.
    • If that player has that card in their hand, then you get it from them.
    • Otherwise, you draw a new card from the deck. If the deck is empty, you don't get anything.
  • If you have two of the same card, then both are removed from your hand and set aside.
  • The game lasts until the deck and all players' hands are empty, or until the deck is empty and there are no pairs made for 2 full circles.
  • The winner is the player that ends with the most pairs.

There will be 20 rounds with every bot in them in random order. The winner will be the bot that gets the most cumulative matches across all rounds.

The Deck

There will be 40 unique cards in the deck, each identified by a string. Each one will appear twice in the deck for each bot in play.

Implementation

To do as soon as I finish the runner.


For the unique cards, I was thinking of doing a fish theme. Examples include:

  • Water-type pokémon
  • State fish for various states
  • Commands, functions, or programs in ><> and *><>

Any other ideas?

| |
\$\endgroup\$
  • \$\begingroup\$ 1. "There will be 40 unique cards ... Each one will appear twice". If they appear twice, they're not unique. 2. This is missing important details about the tournament structure. How many bots per game? How many games will each bot participate in? What will determine the opponents? What are bots allowed to remember between games? Are there points for finishing second, third, etc? \$\endgroup\$ – Peter Taylor Apr 26 '18 at 13:47
  • \$\begingroup\$ @PeterTaylor unique meaning different. \$\endgroup\$ – Nissa Apr 26 '18 at 14:01
  • 1
    \$\begingroup\$ I'd recommend just using numbers to identify the cards, just to prevent bloating the challenge too much \$\endgroup\$ – Jo King Apr 27 '18 at 0:13
0
\$\begingroup\$

Clebsch-Gordon coefficients

Clebsch-Gordon coefficients are numbers that arise when adding two quantum mechanical angular momenta. Angular momentum is a vector in three-space and can be described by two numbers j and m. The magnitude of the momentum can be determined by j and its z-component can be determined by m (more on this below).

For quantum mechanical particles, j can only take on nonnegative integer or positive half integer values (0, 1/2, 1, 3/2, 2...). Additionally, its z-component m can only take on values between j and -j inclusive in integer steps. For example if j=1, m can hold values -1, 0 or 1. If j=3/2, m can have values -3/2, -1/2, 1/2 or 3/2.

If an angular momentum has magnitude j and z component m we say it is in the state |j,m⟩. The state can be thought of as a column vector in an infinite dimensional vector space (Hilbert space). It is infinite because there is no upper bound for the value j can take on. From now on when I refer to an angular momentum I will just use it's state to reference it.

j2 and jz operators

I have picked the states |j,m⟩ such that they are eigenvectors of the operators j2 and jz. These operators can be thought of as matrices in the infinite dimensional vector space. Eigenvectors of j2 have eigenvalue equal to a states total angular momentum squared. The eigenvalue of a state operated on by jz is the state's z-component of its angular momentum. The eigenvalues for a state |j,m⟩ are shown below.

j2|j,m⟩=j(j+1)|j,m

jz|j,m⟩=m|j,m⟩.

In words, the square of the magnitude of the angular momentum of state |j,m⟩ is j(j+1) and the z-component of the angular momentum of this state is simply m.

Side notes which do not affect the challenge and you can choose to ignore:

  • We could have just as easily chosen x or y instead of z but the ji operators do not commute so we must decide on one only to create our basis vectors. All ji commute with j2.
  • I have set ħ=1.

Now let's say we have a composite angular momentum with total angular momentum J and z-component M made up of two individual angular momenta. As you might have guessed, this is the state |J,M⟩. We can make equivalent operators J2= and Jz. In order for |J,M⟩ to be an eigenvector of both of these operators is equal to a linear combination of outer products between states |j1,m1⟩ and |j2,m2⟩.

If the angular momenta that compose |J,M⟩ are in states |j1,m1⟩ and |j1,m1⟩...

Clebsch-Gordon explicit formula

Image from wikipedia.

Sandbox

This is an early stage of writing the challenge, but feedback is welcome. If you are familiar with Clebsch-Gordon coefficients I would appreciate any input. They are important in group theory but I am less familiar with that side of them, so if you have a good way of explaining them in that context that would be helpful.

I plan on asking for the square of the coefficients so as not to worry about floating point numbers.

  • Should I require sign of the coefficients as well or just magnitude?
| |
\$\endgroup\$
  • \$\begingroup\$ Might be useful: Mathematica's built-in ClebschGordan, which you can test on the open sandbox. \$\endgroup\$ – user58632 Apr 19 '18 at 9:06
  • 1
    \$\begingroup\$ It's not clear to me what the inputs are, and therefore what the outputs are. It's also not clear what the range of the sum is: the entire support? \$\endgroup\$ – Peter Taylor Apr 19 '18 at 10:05
  • \$\begingroup\$ @petertaylor yes, thanks I still need to addbthatvinfo \$\endgroup\$ – dylnan Apr 19 '18 at 12:55
  • \$\begingroup\$ @lastresort thanks! I did see there was a built in :) \$\endgroup\$ – dylnan Apr 19 '18 at 12:56
  • \$\begingroup\$ What's the challenge here? \$\endgroup\$ – LastStar007 Apr 27 '18 at 9:24
0
\$\begingroup\$

PPCG Generalist Countdown

Write a function or program that takes no input and returns or outputs the current minimum number of new questions required for PPCG to hand out Generalist badges. Internet access is only allowed to the Stack Exchange API.

The badges are handed out when the top 40 tags (measured by question count) each have at least 200 questions.

Standard loopholes are disallowed. This is code-golf, so the shortest entry wins!

| |
\$\endgroup\$
  • \$\begingroup\$ You need to explicitly say what internet access is allowed, as accessing the internet is disallowed by default \$\endgroup\$ – Nathan Merrill Apr 30 '18 at 11:55
  • 2
    \$\begingroup\$ I'm not sure this adds much beyond the 30+ stack-exchange-api questions we already have ... \$\endgroup\$ – AdmBorkBork Apr 30 '18 at 15:33
  • \$\begingroup\$ @AdmBorkBork Perhaps try to solve it and see how hard it is to port? \$\endgroup\$ – user202729 May 2 '18 at 8:50
0
\$\begingroup\$

Building a Structured Outline

In a fictional document management system, input documents are structured with weighted headings. Lowest weighted headings are the most important.

This is a sample document:

H1 All About Birds

H2 Kinds of Birds

H3 The Finch

H3 The Swan

H2 Habitats

H3 Wetlands

From this document we would like to produce an outline using nested ordered lists in HTML, which would look like this when rendered:

  • All About Birds

    Kinds of Birds

    The Finch 
    
    The Swan 
    

    Habitats

    Wetlands
    

Your code only needs to take the input list and transform it into the expected data structure, which will be printed and checked against the expected output.

| |
\$\endgroup\$
  • \$\begingroup\$ What's the winning criteria? (did you know what does "winning criteria" mean? Read the on topic page of the help center) \$\endgroup\$ – user202729 May 1 '18 at 15:41
  • \$\begingroup\$ 1. Are the blank lines in the sample document going to be in actual input, or are they just there to avoid the lines merging? (If the latter, ending a line with two spaces inserts a line break; and formatting as code using four spaces at the start of each line is a better option for sample input anyway). 2. Will all lines begin with H, a number, and a space? 3. What is the range of possible numbers? 4. Does whitespace matter in the output? 5. When you say "expected data structure", does that mean that the output is something other than a string? \$\endgroup\$ – Peter Taylor May 1 '18 at 16:21
  • \$\begingroup\$ 1. The child items are indented (as as result of parsing them as HTML later) 2. yes, exactly as in the sample input. 3. <h1> to <h6> 4. no, it will be parsed as HTML 5. yes, List \$\endgroup\$ – Tlink May 1 '18 at 16:44
  • \$\begingroup\$ Unrelated to this challenge, but I've just created this Sandbox post based on your deleted Time challenge. Let me know if you want to post it yourself in 72 hours, since it was originally your challenge. If you don't want to post it anymore I'll post it myself (with your permission). Either is fine by me. :) \$\endgroup\$ – Kevin Cruijssen May 2 '18 at 9:50
  • \$\begingroup\$ Please edit the post to add more information instead of answering in a comment. \$\endgroup\$ – user202729 May 2 '18 at 11:11
0
\$\begingroup\$

Given equations, determine values (what would be a good title?)

Given these equations as input, write a program that determines which variable has the greatest, and which has the smallest value.

Equations:

x             <   y
2x            <   y + z
2x + 2y + z   <   2x + y + z
x,y,z         !=   0


Rules:

  • Your code must mathematically determine which variable has the greatest/smallest value.
  • As this is the shortest answer in bytes wins
| |
\$\endgroup\$
  • 5
    \$\begingroup\$ 1. These aren't equations: they're inequalities. 2. One example does not constitute a specification. What limits are there on the number and type of variables, equations, terms, etc? 3. The given example doesn't have a solution. I think the only basic relationships that can be deduced are x < y < 0. z could be smaller than x or greater than 0. \$\endgroup\$ – Peter Taylor May 1 '18 at 16:13
0
\$\begingroup\$

The true spirit of "Hello World!"

A hello world program is traditionally the first program you write in a language you've never tried before. So we're gonna make some true hello world programs here. Your challenge is to golf a hello world program in a language you've never used before.

Once you've posted your best attempt, you are welcome to accept help from others in the comments, including those who've used that language before, but please leave a copy of your original attempt, and use strikethrough on previous byte counts.

Rules based on honesty of participants:

  • Really pick one you've never used before. Different versions (python 2 / python 3) don't count.

  • Don't look at any other codegolf pages other than "tips for golfing in [your language]". Hello world has been golfed in many languages on PPCG but copying would be boring. The point is for each participant to have fun trying something new.

Objective rules, copied from the Hello World catalog challenge (who's answers you are not allowed to look at):

  • Each submission must be a full program.
  • The program must take no input, and print Hello, World! to STDOUT (this exact byte stream, including capitalization and punctuation) plus an optional trailing newline, and nothing else.
  • The program must not write anything to STDERR.
  • Submissions are scored in bytes, in an appropriate (pre-existing) encoding, usually (but not necessarily) UTF-8.

Notes for the Sandbox:

-Will people understand the point of this challenge? I want people to realize that, while PPCG is unlikely to see any novel solutions here, this challenge will still be a challenge for each participant. In fact, even the top-scoring master golfers will have a challenge: to find a language they haven't used ;).

-Is the title obnoxious? Suggestions?

-This is supposed to be a fun challenge for learning and teaching. Will people get that, or will people get really competitive and look for loopholes in the honesty-based rules?

-Should I tag it popularity-contest despite asking for golfed code, just so that people realize it's not supposed to be super-competitive?

| |
\$\endgroup\$
  • 7
    \$\begingroup\$ Although the idea is interesting, I don't think this should be hosted on this site (because the answer length would be >= length of existing post anyway). Perhaps in chat? Or make a chat room for that? \$\endgroup\$ – user202729 May 3 '18 at 16:58
  • \$\begingroup\$ I see what you're saying with the >= existing answers thing. Would that still be an issue if it was tagged popularity contest? \$\endgroup\$ – Jared K May 3 '18 at 18:29
  • \$\begingroup\$ Popularity contests are notoriously difficult to get right. Only 3 of the past 15 have been accepted as good by the community. As-is, this would likely get closed as Too Broad because it's basically "Do X Creatively." \$\endgroup\$ – AdmBorkBork May 4 '18 at 12:29
  • 2
    \$\begingroup\$ It would probably also get tagged as a dupe of the original Hello, World! question \$\endgroup\$ – Jo King May 5 '18 at 0:25
0
\$\begingroup\$

Infer the type

(This is not finished yet.)

Task

Implement the type inference algorithm for Hindley-Milner lambda calculus.

Data Types

The data types in this challenge is (in Haskell):

data Kind  = Star | KindFunc Kind Kind
data Type  = TypeName String  | TypeVar String | App Type Type
data Value = ValueName String | ValueFunc String Type | App Value Value 

If your language doesn't support ADT or if using it will make the program longer, you can use any isomorphic representation.

You can assume that there is no name conflict, nor unbound name.

Theory

Value

In Hindley-Milner system,every value has a single most general type. For example the type of Just 5 is Maybe Int (Note that in Hindley-Milner type system, unlike Haskell, doesn't have any typeclass).

If a function value has type A -> B, you can call it with argument with type A to produce B. Additionally, you can use a lambda. A \x -> y has type type(x) -> type(y). (type(x) means the type of value x). However, if you try to apply a value of type A to function with type B -> C type unification between A and B occurs (explained below)

Type

Like a value, type is composed from smaller type, so that if K has kind "a -> b", and a has type "a", the type K a has kind "b". The example of the type is String, ->, Maybe, Either String, and EitherT String which has kind *, * -> * -> *, * -> *, *, and (* -> *) -> * (Assuming EitherT has kind * -> (* -> *) -> * -> *. Every value has type *. However, the type can be generic. So a value of Nothing has type Maybe a. Here, a can stand for any type.

Type Unification

(TODO : To be filled tomorrow)

Input

The input is a:

  1. list of pair of type name and the its kind
  2. list of pair of value name and its type
  3. and a value to be infered

Output

Either the type of the supplied input or error if there is type mismatch.

Example

(Here we use Haskell notation for the input, it is not recomended in actual challenge because it will unecessarily make the program longer)

> Types  : Maybe :: * -> *, Bool :: *
> Values : Just :: a -> Maybe a, Nothing :: Maybe a, True :: Bool, False :: Bool, maybe :: (a -> b) -> b -> Maybe a -> b, compose :: (a -> b) -> (c -> a) -> (c -> b)
> Infer  : \f -> maybe (compose Just f) Nothing
> Result : (a -> b) -> Maybe a -> Maybe b
> Infer  : \f -> maybe (compose Just f) True
> Result : Type error
| |
\$\endgroup\$
  • \$\begingroup\$ 1. A question should be self-contained. What is the specification of the type inference? What are a kind, a type, and a value? 2. A question should avoid imposing non-observable requirements. In other words, the specification should say what types should be inferred, but not dictate the algorithm. 3. It's not obvious how to map the example to the data types given above. I don't see any constructor names. \$\endgroup\$ – Peter Taylor May 3 '18 at 10:39
0
\$\begingroup\$

Page size changing

Given positive integer m and n both > 1, and array(maybe-empty ordered list) A consist of integers in [0,m)(0-based) or (0,m](1-based), output an array B consist of integers in [0,n)(0-based) or (0,n](1-based) such that, when given input m'=n, n'=m, A'=B, the output is A.

You are not allowed to use built-in large number. To be clear, the number you use should be at most polynomial to (m+n)*arrlength. (discussing, ban/penalty/just allow)

Example: if you output [1,2,3] for m=6, n=8, A=[4,3,2,1], then you have to output [4,3,2,1] for m=8, n=6, A=[1,2,3].

Shortest code win.

| |
\$\endgroup\$
  • \$\begingroup\$ Is there any way simpler than implementing bijective base conversion? Otherwise it's just "implement big integer division"? \$\endgroup\$ – user202729 May 4 '18 at 13:59
  • \$\begingroup\$ I think there be \$\endgroup\$ – l4m2 May 4 '18 at 14:01
  • \$\begingroup\$ you use "array" presumably this means a non-empty ordered list .. a tuple .. thus A and B are each in a space isomorphic to Z but with representations in base m and n respectively .. why not say so \$\endgroup\$ – jayprich May 5 '18 at 11:10
0
\$\begingroup\$

Palindromic Sum

For some all bases g ≥ 5, we prove that any positive integer can be written as a sum of three palindromes in base g.

This is the theorem proven in this paper by Cilleruelo, Luca, Baxter.

Challenge

Given a positive integer n and a base g ≥ 5 find three palindromic numbers in base g that sum to n.

Details

  • You cannot use leading zeros to make a number count as a palindrome, that means the most significant digit of a palindrome must be nonzero. (In base 10, the number 01210 = 1210 is not considered as a palindrome.)
  • The submissions must be able to process any aribtrarily large input n (within the memory limits). It is not sufficient to use finite precision integers, i.e. 32-bit ints.
  • The integers in the input and output can be in the format of native integer types, as strings in any fixed base (not dependent on g), or as list of digits in any fixed base (not dependent on g) or in the base g or as number in the base g.
| |
\$\endgroup\$
  • 2
    \$\begingroup\$ Forbidding finite precision integers doesn't sit well with me, and it doesn't seem particularly vital to the challenge. \$\endgroup\$ – Kamil Drakari May 5 '18 at 15:10
0
\$\begingroup\$

Pressure unit conversion

In my line of work I often need to convert between four different pressure units: bar, psi, MPa and kgf/cm2.

Challenge

Write a program or function that does the following:

  • The user enters a value, the original unit and the conversion unit
  • The program or function makes the conversion
  • It then prints out the result in the form: [Starting value] [Starting unit] = [Converted value] [Converted unit] with spaces between all items.

For example with inputs 15.25, psi and kgf/cm2, the program would print out the following:

15.25 psi = 0.07030695796 kgf/cm2

Rules

  • The allowed range of input values can be in your language's standard floating-point type.
  • Input can be arguments, come from STDIN, or whatever is your language's preferred form of input.
  • The input units don't have to be literal strings - you can use other pre-defined values if you want.
  • However, the output must use the literal of the units: bar, psi, MPa and kgf/cm2.
  • Both kgf/cm² and kgf/cm2 are acceptable.
  • If printing out the result isn't feasible then you can return the string that would have been printed out.
  • This is code golf - shortest answer wins!

Conversion values

The conversion values are:

1 bar = 14.50377377 psi
1 bar = 0.1 MPa
1 bar = 1.019716213 kgf/cm²
1 psi = 0.06894757293 bar
1 psi = 0.006894757293 MPa
1 psi = 0.07030695796 kgf/cm²
1 MPa = 10 bar
1 MPa = 145.0377377 psi
1 MPa = 10.19716213 kgf/cm²
1 kgf/cm² = 0.980665 bar
1 kgf/cm² = 14.22334331 psi
1 kgf/cm² = 0.0980665 MPa

Some test cases:

33.4 bar = 484.426044 psi
19 kgf/cm2 = 1.8632635 MPa
65 MPa = 650 bar
-59.002 kgf/cm2 = -839.2057018 psi
23 bar = 23 bar
0 psi = 0 kgf/cm2
1 MPa = 1 MPa

I took these sample values from here. You can use it too for more test cases.

Sandbox Questions

  • Is four pressure units all right, or is it too many? My gut tells me that four makes it just complex enough, but I'm also worried that it's just adding extra information without any extra challenge.
  • I'm not certain if I should restrict the input as well as the output. I think restricting the output format adds to the challenge, but restricting the input would make the challenge too, well, restrictive.
  • I should display the conversion values in a more machine-readable form, but I'm not sure how. Any ideas?
| |
\$\endgroup\$
0
\$\begingroup\$

Intro

Many fans of high-powered editors like to learn new tricks. For example, vimgolf.com: "Real Vim ninjas count every keystroke".

Goal

Produce this diagonal matrix in a text editor:

0000000000
0100000000
0020000000
0003000000
0000400000
0000050000
0000006000
0000000700
0000000080
0000000009

Winning criterion

Fewest keystrokes wins

Rules

  • Need to do it in a text editor
  • All pre-existing packages are allowed
  • Must start from an empty page
  • No copy/pasting external content

Explanation

  • Say which editor
  • Present the total number of keystrokes
  • Provide a list of keystrokes, and say what each one does
  • Link to any packages used, so we can check them out!

See Is editor golf on-topic? for more info on editor golf.

| |
\$\endgroup\$
  • \$\begingroup\$ -1 for text editor restriction, -1 for pre-existing packages, "must start from empty page" and "copy/pasting" are common sense/standard loopholes. "say which language/number of keystrokes/provide a list of keystrokes" is required in all code-golf challenges \$\endgroup\$ – ASCII-only May 8 '18 at 8:09
  • \$\begingroup\$ Hi, welcome to PPCG! First of all good job for using the Sandbox, since a lot of new users do not. The tags you've added both doesn't exist, [tag:matrix] does exist however, but editor-golf not (tag lists). I'm also a bit confused about the challenge. Do we need to use any programming language, and create that output in a .txt file? Or do we actually use text editors like Notepad, Notepad++, VIM editor, etc. and use their default commands to get the result in as few commands / key-pressed as possible. I'm assuming the second if I read correctly. \$\endgroup\$ – Kevin Cruijssen May 8 '18 at 8:09
  • 1
    \$\begingroup\$ re: packages - for all we know someone has already made a package to do it in one key :P \$\endgroup\$ – ASCII-only May 8 '18 at 8:09
  • 3
    \$\begingroup\$ See codegolf.meta.stackexchange.com/questions/4816/… for more info on editor golf. \$\endgroup\$ – Hatshepsut May 8 '18 at 8:12
  • \$\begingroup\$ @KevinCruijssen Right, the intent is to use the commands available in a text editor like vim or emacs. \$\endgroup\$ – Hatshepsut May 8 '18 at 8:19
  • \$\begingroup\$ @ASCII-only If there's a package for doing cool stuff like that in one key, I want to know about it! : ) \$\endgroup\$ – Hatshepsut May 8 '18 at 8:22
  • \$\begingroup\$ What determines whether something is a "text editor" or not? Is Microsoft Word one? Because that would allow you to use VBA macros. How about a programming environment like Eclipse? You can edit text documents in such a program. This needs to be a little better defined before it gets my upvote. \$\endgroup\$ – AdmBorkBork May 8 '18 at 13:11
  • \$\begingroup\$ Challenges should not limit possible languages. I can't see any problem from allowing e.g. Python to compete. \$\endgroup\$ – user202729 May 8 '18 at 16:09
  • \$\begingroup\$ Although, let people vote. Note Please upvote if you think that limiting it to editors only is good (despite the fact that it can be ambiguous, as AdmBorkBork said in the comment above), or downvote it if you think that this can be made language agnostic. \$\endgroup\$ – user202729 May 9 '18 at 11:36
  • \$\begingroup\$ This is the latest well-received language-specific challenge, if I recalled correctly. \$\endgroup\$ – user202729 May 9 '18 at 11:36
0
\$\begingroup\$

How Many Cards Can You Play This Turn?

Given a deck of cards L, where each card has an nonnegative integer mana cost, and two nonnegative integers x, representing the mana you have this turn, and n, representing the number of cards you draw from the deck, output the average highest number of cards you can play this turn.

i.e. given an array of nonnegative integers L and nonnegative integers x and n, create the subset N by choosing n random elements of L. Find the average of the maximum number of elements in N that sum to no greater than x.

Examples

For example, L = [0, 1, 2, 3, 4, 5, 6], x = 1, n = 1. You get 1 mana this turn and draw 1 card at random, from a deck of cards with mana cost 0...6. Since there is a 1/7 chance of drawing any card and you only have 1 mana, there is a 2/7 chance you can play the 1 card you draw (0 or 1) and a 5/7 chance you can’t play the card you draw (2...6). Therefore the average max number of cards that can be played is 2/7 = 0.286

For a more complicated example, L = [0, 1, 2, 3, 4, 5, 6], x = 10, n = 4. You get 10 mana and draw 4 cards from the same deck as above. There are 7 choose 4 = 35 different possible hands. Of this, there are only 2 hands in which only two cards can be played (3,4,5,6 and 2,4,5,6). There are 22 hands where 3 cards can be played and 11 hands where 4 cards can be played. Therefore, the average max number of cards that can be played is (2*2 + 3*22 + 11*4) / 35 = 114/35 = 3.257

Specifications

  • The input must be a list of nonnegative integers, L, and two nonnegative integers, x and n.
  • You may assume n <= len(L), i.e. you cannot draw more cards than are in the deck
  • The output must be either a decimal which has at least 3 digits of precision or an exact fraction
  • The distribution for each element of L must be equal
  • Standard I/O methods apply and standard loopholes forbidden
  • This is code golf so shortest answer in bytes wins

Test cases

Input: L (the deck), x (mana), n (cards drawn)
-> Output: average max # of cards played this turn (fraction for reference)

[0, 1, 2, 3, 4, 5, 6], 1, 1 -> 0.286 (2/7)
[0, 1, 2, 3, 4, 5, 6], 2, 2 -> 0.810 (17/21)
[0, 1, 2, 3, 4, 5, 6], 3, 3 -> 1.457 (51/35)

[0, 1, 2, 3, 4, 5, 6], 10, 3 -> 2.686 (94/35)
[0, 1, 2, 3, 4, 5, 6], 10, 4 -> 3.257 (114/35)
[0, 1, 2, 3, 4, 5, 6], 10, 5 -> 3.762 (79/21)

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

[0, 16, 4, 9, 3], 7, 2 -> 1.2 (12/10)
[11, 0, 3, 19, 6, 8, 15], 20, 4 -> 2.686 (94/35)
[14, 3, 2, 11, 5, 3, 9, 2, 10], 20, 6 -> 3.976 (334/84)
| |
\$\endgroup\$
0
\$\begingroup\$

Take an expression containing variables and these functions, check whether it's true:

1 int  one()          1
- int  neg(int)       -a
+ int  add(int, int)  a+b
- int  sub(int, int)  a-b
* int  mul(int, int)  a*b
> bool gt (int, int)  a>b
< bool lt (int, int)  a<b
= bool eq (int, int)  a==b
& bool and(bool,bool) a&b
| bool or (bool,bool) a|b
! bool not(bool)      !a
 bool nand(bool,bool) !(a&b)
^ bool xor(bool,bool) a^b, or (a&!b)|(!a&b)
  bool imp(bool,bool) !a|b
... (any bool function, with any amount of input)
E bool any(var, expr) whether a be any value make expr true
A bool all(var, expr) whether a be all value make expr true

You can take input in any reasonable format. You can define what "variable" look like as long as there can be infinite possible different variables. Removing some functions is allowed as long as it doesn't reduce the ability of expressing, i.e. some calculatable function can convert expression with all functions possibly exist into the model you removed something. Redefining the function name or merging some symbols is also allowed.

To solve the problem, you are given another input source G. You need to solve the problem correctly when G[0] -> inf, G[1] > any_function(G[0]), G[2] > any_function(G[1]) ....

Sandbox Notes:

it's quite a fix of this one, but it's using haltable as output while I use another input source to help solve.

| |
\$\endgroup\$
  • 2
    \$\begingroup\$ I understand what you're doing here. If you're OK with it, I'll adapt my version and post it, since it's more complete at the moment. \$\endgroup\$ – Esolanging Fruit May 12 '18 at 0:20
  • \$\begingroup\$ Now it looks similar to your previous "solve the halting problem" challenge. \$\endgroup\$ – user202729 May 14 '18 at 7:10
1
75 76
77
78 79
100

You must log in to answer this question.

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