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\$

2995 Answers 2995

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

Source in n bytes

Write a program A and an integer K that, when given a number n>=K, your program generates a program(in same language) of length n that generates the source program A and don't if some characters are removed.

Smallest K for each language win.

| |
\$\endgroup\$
  • \$\begingroup\$ What do you mean by "and don't if some characters are removed"? Any example? \$\endgroup\$ – tsh May 14 '18 at 5:13
  • \$\begingroup\$ @tsh generates the source program A and don't generates the source program A if some character(s) of your generated source are removed, so you don't just fill the code with unnecessary space/etc \$\endgroup\$ – l4m2 May 14 '18 at 5:48
  • \$\begingroup\$ So it's similar to a pristine program? \$\endgroup\$ – user202729 May 14 '18 at 6:58
  • \$\begingroup\$ What do you mean by "don't generate program A if some characters removed"? Do you mean "for any sub character sequence S of source A, program S have different behavior to program A"? \$\endgroup\$ – tsh May 14 '18 at 7:13
  • \$\begingroup\$ @tsh your program generates a program(in same language) of length n called P that outputs A, for any sub character sequence S of source P, program S have different behavior to program P(so don't output A) \$\endgroup\$ – l4m2 May 14 '18 at 10:00
  • \$\begingroup\$ This looks to me like a generalised quine. If a simple quine diagonalises f(Y):print Y, this diagonalises f(Y):if len("....")>X:print Y. There are some subtleties around the length of X, but I'm not sure how much this adds to existing quine questions. \$\endgroup\$ – Peter Taylor May 14 '18 at 10:01
  • \$\begingroup\$ @PeterTaylor For example, we have function () { source = ...; if (length(source)=10000) return source; else "9900 bytes padding"; } then its sub sequence function () { source = ...; if (length(source)=1000) return source; else "900 bytes padding"; } should just work. \$\endgroup\$ – tsh May 15 '18 at 2:44
  • \$\begingroup\$ @tsh, I have no idea what you mean. I'm not even sure whether your example is meant to support my point or contradict it. \$\endgroup\$ – Peter Taylor May 16 '18 at 8:57
  • \$\begingroup\$ @PeterTaylor I think tsh can support or contradict your idea, depending on your meaning \$\endgroup\$ – l4m2 May 16 '18 at 11:00
0
\$\begingroup\$

Posted

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

RTanque Tournament!

I'd love to do a PCG challenge based on RTanque by awilliams.

https://github.com/awilliams/RTanque

(only Ruby, sorry)

It's a game which is played by writing code to control a tank, sharing a game space with some other tanks. The aim of the game is to be the last tank standing. Part of the beauty of it is that, after writing the code, no further user input is needed during the game.

I've seen this work really well at meetups, it goes like this:

  • Individuals or teams install the library, run a game with the example tank classes.
  • Create a new tank class, with a unique name.
  • Modify behaviour, both movement rules and aiming/firing rules.
  • At the end tanks are all sent to the organiser (usually via GitHub gists)
  • On a projector, the tanks are pitted against each other. Everyone can watch how their tank fares.

How it'd work on SO:

  • There'd be a set period of time, perhaps 1 or 2 weeks.
  • Answers would be a tank class.
  • There'd be an "event" to close the challenge.
  • The fights are screen-capped, dropped onto YouTube and embedded in the question.

Phase 1:

All answers are randomly placed into large groups (maybe 10 per game), the first half to lose are knocked out of the tournament.

Phase 2:

The rest are randomly dealt into a bracket tournament, and are eliminated in successive matches.


Any thoughts? Ideas? Offers of practical help?

| |
\$\endgroup\$
  • \$\begingroup\$ Bracket tournaments are typically a terrible way to choose a winner. Any sort of randomness can have a huge effect on the outcome. If randomness is involved at all, you'll need to run thousands of games to get a reliable winner. These types of challenges are called king-of-the-hill, and we do enjoy them around here. \$\endgroup\$ – Nathan Merrill May 14 '18 at 16:35
0
\$\begingroup\$

Calculator tape

There is an infinite amount of calculators in a row (supporting the four basic operations, +, -, *, and /), all initially displaying "0". They have a peculiar property that any calculator which has a result lower than either the one to its left or right stop accepting any button presses except "=".

Besides the calculators is an operator who follows certain instructions and presses their buttons accordingly.

Unfortunately, the operator is a bit lazy and has asked you to write a program which would simulate all of this for him and then output a list of all nonzero calculator results.

Calculators and operations

Every calculator has three registers, one which stores the input, one which stores the last result, and one which stores the currently selected operation (+, -, *, /).
In the beginning, the input and result registers are unset, acting as 0 if adding/subtracting or 1 if multiplying/dividing. The operation starts as +.

The operations available are the following:

  • 0..9 - Append the digit to the input of the selected calculator, without changing its result.
  • # (±) - Change the sign of the input. Note that this might be executed even when the input is 0.
  • +, -, *, / - Evaluate the current operation, then set the operation accordingly and reset the input. As it changes the result, it might change the disabled statuses of calculators.
  • = - Evaluate the current operation and reset the input. Don't reset the operation.
    Unlike the other operations, this operation works even when the calculator has a lower result than its adjacent calculators.
  • <, > - Select the previous or the next calculator, similar to BF.

Input and output

Input is going to be a string or list of operations to be done. The characters used to represent the individual operations need not be the same as outlined above, but must be distinct.

Output should be a list (in any format) composed of nonzero calculator results and their indices. The indices might start from any number, as long as it is identical between runs.

Examples:

Input  ->  Output # comment
1  ->  # The calculator's result is 0
1=  -> 0: 1 # The = operation evaluates result + input = 0 + 1 = 1
1#=  -> 0: -1
#1=  -> 0: -1 # Note that this results in input being -0 for a moment
1=>2=  ->  0: 1 # The second calculator does not work while the first is larger
1#=>2=  ->  0: -1, 1: 2 # Results start at 0, so negative results don't disable
1>2=<=  ->  0: 1, 1: 2 # = Works on otherwise-disabled calculators
4*4>1+2=<=  ->  0: 16 # * changes the result to 4, thus disabling others

Meta

  • As it currently stands, there are too few complicated examples, mainly because it is too easy to disable a calculator. Would be nice to have some which have multiple adjacent calculators with the same result.
  • There is too little inter-calculator interaction past the disabling mechanic. Maybe some way to read a result as input?
  • The third point might be yours! Comment to claim it ;)
| |
\$\endgroup\$
  • \$\begingroup\$ What character encoding is ± in? Can we assume Windows-1252 where ± is 0xB1? (I suggest using an ASCII-only substitution, like #) \$\endgroup\$ – user202729 May 15 '18 at 6:38
  • \$\begingroup\$ > "The characters used to represent the individual operations need not be the same as outlined above, but must be distinct." -- the idea was that golfers might pick a different character, for example $ or #. Anyway, I will replace ± with # so it would be less confusing. \$\endgroup\$ – Bojidar Marinov May 15 '18 at 11:51
0
\$\begingroup\$

Tired Sumo Fighters

This is a simple KOTH challenge in which you program a bot to push other bots out of a ring. Each round consists of two bots, and every bot will compete against each other bot at least 10 times. The reason that this KOTH is different from other similar KOTHs is that the bot only is very tired, so it only has a little bit of energy, and it cannot waste it.

Moving

Your bot can move around the ring (An 11x11 square) using one of 10 commands:

moveForward() //Moves forward
moveLeft() //Moves left
moveBackward() //Moves backward
moveRight() //Moves right
moveToward() //Moves toward enemy
moveAway() //Moves away from enemy
approachCenter() //Moves toward center of ring
approachEdge() //Moves away from center of ring
moveCounterClockwise() //Moves counter-clockwise around ring
moveClockwise() //Moves clockwise around ring

However, each movement takes energy. As a parameter, set the energy consumption (Defaults 1). If one bot stays still and the other runs into it, the moving bot pushes the still bot. If the bots run into each other, the bot who allotted more energy pushes. If there is a tie, the bots do not move.

Pushing

Say that bot 1 and bot 2 are fighting. If bot 1 is at position (-4,5) and bot 2 is at (-2,5), there is one space between them. If each bot moves toward the opponent, the one who spent more energy moves forward. If there is a tie, the bots do not move. If a bot has any coordinate with an absolute value greater than 5, it loses. If any bot has energy under 0, it loses. It is possible to live with 0 energy, but you will be quickly pushed out of the ring. Every bot starts with 200 energy

Detection

To find your opponent or yourself, use these commands:

locateSelf() //Returns as array [x,y]
locateOpponent() //Returns as array
energyLevel() //Returns your energy level
opponentEnergy() //Returns opponent's energy

Example

function sumoChamp() {
    if (energyLevel() > opponentEnergy()) {
        moveToward(5);
    } else {
        moveCounterClockwise(2);
    }
}

As you can see, a basic sumo bot takes just a few lines. However, a smart sumo bot would be able to overpower it, and a genius bot could even figure out its pattern and destroy it. You cannot build systems designed to target specific bots that have already been designed. To save information for later, store it in your bot's function, like this:

sumoChamp.opponentResearch.avgEnergy = 4

Rules

Standard loopholes not allowed

Entries can be in any language that supports functions and arrays, but all entries will be converted to JavaScript before the game starts.

| |
\$\endgroup\$
  • \$\begingroup\$ There should be more specification. What's the exact distance the bot will be pushed? \$\endgroup\$ – user202729 May 19 '18 at 16:46
  • \$\begingroup\$ @user202729 1 space \$\endgroup\$ – Redwolf Programs May 21 '18 at 2:26
  • \$\begingroup\$ Perhaps my understanding is not complete, however would there be an optimum solution that would either guarantee a win or tie? i.e. move to the centre of the ring and then subequently push the opponent toward the outside of the ring with half of the remaining energy that you have each step. If the opponent uses less energy they are pushed, otherwise they will have wasted more energy than the first bot and eventually run out of energy prior to the first bot, thus get push out \$\endgroup\$ – Moogie Jul 20 '18 at 4:09
0
\$\begingroup\$

Bananagrams


Bananagrams is a tile-based word game where you race to make crosswords and use all your letters before everyone else does. In the original game, finishing your crossword allows you to say "peel", causing everyone to draw another letter tile. Whoever finishes their crossword when there are no more letter tiles to draw is the winner.

Challenge

You will be given a list of letter tiles and your task is to arrange them into a crossword using this list of alphabetic words as your dictionary. In the spirit of the board game, you need to do this as quickly as possible.

Input and Output

Input to your solution will be a list of letters and you should output a grid of letters. You will need to read in the list of words.

As an example: given abcdeiloopswy, your program/function might produce

cowboy
  a l
  side
  p

Test cases for timing

  • aabcdeeefghiijklmnoopqrssttuuvwxy

more TBA

Rules

  • No abusing standard loopholes
  • Input and output may be in any convenient format.
  • You must load the linked word list exactly, not a stripped down version.
  • You may assume that you will be given only lowercase letters
  • You may assume that there is at least one possible crossword from your given set of letters.
  • This is a challenge, so the answer with the shortest execution time in each language wins.
    • Be sure to post execution time and CPU as part of your solution.
| |
\$\endgroup\$
  • 1
    \$\begingroup\$ Why do solutions need to be written in Python? What if a solution calls out from Python to another language? \$\endgroup\$ – isaacg May 7 '18 at 21:23
  • \$\begingroup\$ @isaacg: one way or another, there needs to be a way to compare solutions on performance. The other option would be to make a test driver for several languages, but I don't want to write 10 test drivers. \$\endgroup\$ – Beefster May 8 '18 at 2:15
  • \$\begingroup\$ I don't see why you need a test driver like that. Just require submissions to read from a file and write their outputs to a file, and have your test script read their file to evaluate their solutions. \$\endgroup\$ – isaacg May 8 '18 at 5:12
  • \$\begingroup\$ @isaacg: how would I be able to score on execution time? I guess I could ditch that as a scoring requirement in favor of a time limit. \$\endgroup\$ – Beefster May 8 '18 at 18:17
  • 1
    \$\begingroup\$ Time the execution of the submission, with something like the time command. Or require submissions to time themselves. I'm not suggesting you change your rules at all, just use different timing. \$\endgroup\$ – isaacg May 8 '18 at 18:29
  • \$\begingroup\$ @Beefster (time command is a Linux utility, which can be used to measure the execution time of any process, which is also what TIO used to measure the time, however do note that TIO is not acceptable for measuring time) \$\endgroup\$ – user202729 May 9 '18 at 13:36
  • \$\begingroup\$ @isaacg: How would I adjust for differences in language speeds? Solutions in C would have a massive advantage over solutions in pretty much any other language. \$\endgroup\$ – Beefster May 9 '18 at 19:28
  • \$\begingroup\$ @user202729: See above comment \$\endgroup\$ – Beefster May 9 '18 at 19:29
  • \$\begingroup\$ @Beefster A lot of the time, algorithmic speed is more important than complilation quality, so it'll matter what language the program is easiest to write fast code in, which is not always C. Take a look at past fastest-code contests. C++, Rust, and Nim are popular. \$\endgroup\$ – isaacg May 9 '18 at 19:39
  • 1
    \$\begingroup\$ @isaacg: After looking around, you have me convinced. I thought language advantages were a bigger deal than they really were. \$\endgroup\$ – Beefster May 9 '18 at 20:13
  • \$\begingroup\$ I'm not a fastest-code expert (ask Dennis for more details?), but I'm afraid that using a "sample benchmark program" doesn't solve the "on which machine" issue, because on some machines some operations can be done faster than other machines. \$\endgroup\$ – user202729 May 11 '18 at 1:05
0
\$\begingroup\$

Construct any Sporadic Simple Group

There are 26 sporadic simple groups. Your task is to write a program which defines an operation isomorphic any of these groups.

Input: Two symbols that represent elements of the group. You can choose how these symbols will be represented (characters, numbers etc.).

Output: The result of the operation on the input.

Taken as a whole, the operator defined must be isomorphic to one of the 26 sporadic groups.

I don't actually know anything about group theory; I haven't even taken a course in it yet, just read some Wikipedia and thought this could be interesting. If it isn't trivially solvable, maybe someone could post it?

| |
\$\endgroup\$
  • \$\begingroup\$ I think this has potential but needs a bit of work. 1. As it stands, it's almost 26 questions in one. Intuitively I would expect the smallest group to be the most golfable, but to really be sure I'd have to make a semi-serious effort with all 26. I suggest picking one group or at most one family of groups. 2. "Symbols" is a bit vague. I'm not sure whether I'd be allowed to use an array which must be a permutation of the numbers 0 to N for suitable N (which is the obvious way of doing some if not all of the groups). 3. You haven't specified a winning condition. I assume code-golf. \$\endgroup\$ – Peter Taylor May 20 '18 at 21:59
  • \$\begingroup\$ 4. (Hadn't thought of this when I wrote 2). Since every finite group is a permutation group, with a suitable input format this can be reduced to codegolf.stackexchange.com/q/1490/194 . So if you want to tackle it as group action, you need to constrain the input representation and running time quite harshly. However, it reminds me of codegolf.stackexchange.com/a/26423/194 where golfing a representation of a simpler perm group was an interesting subtask. The solution might be to ask to generate all elements of the group in a non-trivial representation (as perms or reduced words). \$\endgroup\$ – Peter Taylor May 20 '18 at 22:07
0
\$\begingroup\$

K-th largest element

Find the k-th largest element of n elements in at worst O(n)

It shouldn't be affected by

  • element arranging
  • element range
  • RNG (if you use)

| |
\$\endgroup\$
  • \$\begingroup\$ This can be done with a heapify algorithm in O(n). Not that complicated. \$\endgroup\$ – Beefster May 19 '18 at 20:33
  • \$\begingroup\$ @Beefster But (1) it's not trivial (at least for golfing languages, C++ has built-in nth_element) and (2) your algorithm is wrong (it takes O(n+k log n), which is about O(n log n) for k in O(n)) \$\endgroup\$ – user202729 May 20 '18 at 2:36
  • \$\begingroup\$ "O(n)" implies "at worst O(n)". Big-O notation only upper-bound the complexity, it doesn't lower-bound. (so an algorithm that is O(n) is also O(n²), O(n!), ...) \$\endgroup\$ – user202729 May 20 '18 at 2:37
  • 5
    \$\begingroup\$ Also, please "Write your challenge just as you would when actually posting it." -- people find it hard to understand your posts, so it would have a lower change of them not understanding your challenge. \$\endgroup\$ – user202729 May 20 '18 at 2:38
  • 1
    \$\begingroup\$ To the two people who have upvoted this answer: @user202729's point is relevant to you too. Do you seriously think this is ready to post with just a title and tags? \$\endgroup\$ – Peter Taylor May 20 '18 at 22:14
  • \$\begingroup\$ @PeterTaylor No because of the character limit xd (I thought it was a 0 vote, didn't know it's a +2/-2) \$\endgroup\$ – l4m2 May 21 '18 at 1:20
  • \$\begingroup\$ @user202729 nth_element is average O(n), worst O(n^2) iirc? \$\endgroup\$ – l4m2 May 21 '18 at 1:21
  • \$\begingroup\$ ... I think so. cppreference says "O(n) on average", and doesn't specify the worst case behavior. You may want to add "the algorithm must have deterministic runtime". \$\endgroup\$ – user202729 May 21 '18 at 1:23
0
\$\begingroup\$

Meta

Polyomino detection itself is a duplicate. And there was also a very similar question concerning simple connectedness of a tiling pattern. So I won't submit.

Holey polyomino

A polyomino is a plane polygon consisting of equally-sized squares connected at edges. A polyomino might have a hole if it contains a region with a square on all four sides.

The challenge

Determine if a collection of squares is a polyomino with a hole.

Input

The input will be a matrix of 0s and 1s, where a 1 indicates a square in that position. For example, the top left nonomino in the picture above could be:

Output

A truthy or falsey value for whether the input represents a polynomino with a hole.

Test cases

Arrays of rows:

[[1, 1, 1], [1, 0, 1], [1, 1, 1], [0, 1, 0]] => TRUE

[[1, 1, 1, 0], [1, 0, 1, 0], [1, 1, 1, 0], [0, 1, 0, 1]] => FALSE
| |
\$\endgroup\$
  • \$\begingroup\$ Are holes of size greater than 1 considered? For example (as a list of rows since formatting is limited in comments) [[1111] [1001] [1111]] \$\endgroup\$ – Kamil Drakari May 22 '18 at 20:21
  • 1
    \$\begingroup\$ @Kamil Drakari yes, that counts. I'll add a test case. And there's no need for the input to be square, so I'll change that too. \$\endgroup\$ – ngm May 22 '18 at 20:24
  • \$\begingroup\$ Proposed test case [[0, 1, 1, 1], [1, 1, 0, 1], [1, 0, 0, 0], [1, 1, 1, 1]] => FALSE to cover the situation where there's an empty square with non-empty squares in all four directions but which still has a path to the exterior. \$\endgroup\$ – Peter Taylor May 23 '18 at 7:42
  • \$\begingroup\$ I don't think this challenge is likely to get much traction. I've just proposed a simpler "Is this a polyomino?" question which I think should go first, and might open up possibilities for other challenges. \$\endgroup\$ – ngm May 23 '18 at 14:37
  • \$\begingroup\$ The simpler one is, as I wrote in a comment there a duplicate. This one is not a duplicate AFAIK, so you should stick with this one (if any). \$\endgroup\$ – Stewie Griffin May 23 '18 at 18:54
  • \$\begingroup\$ Can there be two (or more) holes? \$\endgroup\$ – Stewie Griffin May 23 '18 at 18:58
  • \$\begingroup\$ @StewieGriffin I've deleted the other one. And this one is very close to codegolf.stackexchange.com/questions/69030/… so I don't think I would proceed. \$\endgroup\$ – ngm May 23 '18 at 18:58
  • \$\begingroup\$ @StewieGriffin the two-or-more hole thing could work, but I would be inclined to make it a question about topology rather than polyominoes. As in "calculate the genus of this surface" where the surface is represented by the binary array as in my examples. \$\endgroup\$ – ngm May 23 '18 at 19:07
0
\$\begingroup\$

Go shopping!

You're shopping for four specific items. Your town contains fifteen shopping malls. Unfortunately you can't always find the item you want at the nearest mall. You want see whether you can purchase the four items on a single shopping trip.

For each item, there is a list of malls (given as coordinates) where the item can be purchased. Some malls however will only sell you a given item if you visit that mall first. Furthermore, the entrances and exits to the malls are badly placed and you can only visit malls in increasing order of coordinates.

Examples:

  1. Item 1 can be purchased at mall (7, 2) but only if you visit that mall first. It can also be purchased at mall (3, 1).
  2. Item 2 can be purchased at mall (7, 1).
  3. Item 3 can be purchased at mall (3, 2), (4, 2), (5, 2) or (6, 2).
  4. Item 4 can be purchased at mall (7, 2).

With this scenario, it's not possible to purchase both items 2 and 3 in one trip.

  1. Item 1 can be purchased at mall (3, 3), (4, 3), (5, 3), (6, 3).
  2. Item 2 can be purchased at mall (3, 2), (4, 2), (3, 3) or (4, 3).
  3. Item 3 can be purchased at mall (6, 1), (7, 1), (6, 2) or (7, 2).
  4. Item 4 can be purchased at mall (4, 1), (5, 1), (6, 1) or (7, 1), but only if you visit that mall first.

In this secnario, you would visit mall (4, 1), (4, 2), (6, 2), and then (6, 3), and successfully purchase all four items on a single trip.

This is , so the shortest program or function that breaks no standard loopholes wins.

| |
\$\endgroup\$
  • \$\begingroup\$ 1. "(given as coordinates)": always 2D and in integers? 2. "Some malls however will only sell you a given item if you visit that mall first." How is this indicated in the input? 3. "in increasing order of coordinates." What's the order in dimensions higher than 1D? Lexicographic? \$\endgroup\$ – Peter Taylor May 24 '18 at 13:49
  • \$\begingroup\$ I think your two examples need more separation. It was difficult to tell whether the middle "With this scenario..." line connects to the first, second, or both lists. I would add "Example 1:..." and "Example 2:..." to show the distinction. \$\endgroup\$ – Kamil Drakari May 24 '18 at 15:03
  • \$\begingroup\$ @PeterTaylor 1. Yes. 2. I don't mind how that special case is indicated in the input; you could have two separate lists, or a boolean with the coordinates. 3. You can choose which coordinate(s) to increase. \$\endgroup\$ – Neil May 24 '18 at 19:04
  • \$\begingroup\$ How come in the first scenario I can't go (3,1) (3,2) (7,1) (7,2) and purchase all four items? Do items need to be bought in order? If so, that should be explicitly stated. \$\endgroup\$ – AdmBorkBork May 25 '18 at 14:03
  • \$\begingroup\$ @AdmBorkBork You can't go from (3, 2) to (7, 1) because 1 < 2. (And you can't go from (2, 3), to (1, 7) either, for the same reason.) \$\endgroup\$ – Neil May 25 '18 at 15:40
  • \$\begingroup\$ Ah, both coordinates need to be non-decreasing. That could probably be made a little more clear. \$\endgroup\$ – AdmBorkBork May 25 '18 at 15:58
  • \$\begingroup\$ This should be reflavored as an IKEA trip. :P \$\endgroup\$ – Beefster May 29 '18 at 19:01
0
\$\begingroup\$

Softcode

Softcoding is an anti-pattern defined by “the practice of removing ‘things that should be in source code’ from source code and placing them in some external resource”, which usually are config files, database entries, or both. “At the extreme end, soft-coded programs develop their own poorly designed and implemented scripting languages”, as can be seen by one of the most egregious examples of the practice, the Enterprise Rules Engine.

Thus, programmers who fall to the habit of softcoding, after tons of work, find themselves at the very point they were starting from: they have developed “some sort of COmmon Business-Oriented Language that’s generic enough to code any rule”. But unfortunately for them, there already is such a thing. “It’s called C++. And Java. And C#. And Basic. And, dare I say, COBOL.

For the sources of the above quotations are more information of the practise, see: Soft Coding on The Daily WTF, Softcoding on Wikipedia and The Enterprise Rules Engine on The Daily WTF.

The Challenge

Softcode! Make an actual, Turing-complete language that will reside in config files!

More specifically, you should write a compiler / interpreter / anything in between that will define a Turing-complete programming language, whose every valid source code will also be a valid JSON file. (The reason why JSON has been chosen is the simplicity of syntax and wide avalability of JSON parsers, so that you won't have to write a parser yourself.)

Input/output format is up to you.

The catch

Not your interpreter code should be golfed. Your JSON code should be golfed. Or, more specifically, golfable. That is: you will have to present a JSON file that, if fed to your program, will solve a given golfing challenge and will have smallest size out of all JSON files presented here. This will determine the winner; the size of the interpreter code is not relevant.

Technical details

Unfortunately, given how this challenge is defined, if I would define any particular problem your JSON-program should solve, one could get away with a simple trick of defining one particular command in one's JSON programming-language that solves this particular problem. To instead encourage creating a language that is as concise as possible, this challenge will be split into two phases. Phase 1 will last a month since posting this challenge; you will then write your compilers or interpretes. Then I will, on random, choose one challenge from this site that has at least 5 upvotes. (If this challenge proves unsuitable for this problem, I'll roll the dice again.) Afterwards, Phase 2 will begin, when you will present a JSON-program that solves this challenge.

Be creative.

Example interpreter

For reference, below is a simple JS interpreter of a Turing-complete JSON programming language. Of course, it does not strive to define a language suitable for golfing. (I hope there are no bugs in this interpreter, but I don't feel like testing it now.)

importPackage(java.io);
importPackage(java.lang);

// This interpreter implements GOTO-programs, which are Turing-complete.

var stdin = new BufferedReader( new InputStreamReader(System['in']) );
var progsrc = stdin.readLine();
var prog = JSON.parse(progsrc).prog;

var vars = {};
vars.in = Number(stdin.readLine());

for(var i = 0; i < prog.length; i++) {
    switch(prog[i].command) {
        case 'ADD':
            vars[prog[i].varname] = vars[prog[i].varname] || 0;
            vars[prog[i].varname] += prog[i].constant;
            break;
        case 'SUBSTRACT':
            vars[prog[i].varname] = vars[prog[i].varname] || 0;
            vars[prog[i].varname] -= prog[i].constant;
            break;
        case 'GOTO':
            i = prog[i].index-1;
            break;
        case 'IF':
            vars[prog[i].varname] = vars[prog[i].varname] || 0;
            if(vars[prog[i].varname] == prog[i].constant) {
                i = prog[i].index-1;
            }
            break;
        case 'HALT':
            i = prog.length;
            break;
    }

    vars.out = vars.out || 0;
    print(vars.out);
}
| |
\$\endgroup\$
  • \$\begingroup\$ What's the winning criterion? \$\endgroup\$ – feersum May 26 '18 at 23:29
  • 1
    \$\begingroup\$ @feersum Size of the JSON program. But nevermind. I realized how hard did I screw. Trivially, the correct solution is to pass the sole property name to an already-existant golfing language interpreter. I'll post a take 2 in a while... \$\endgroup\$ – gaazkam May 27 '18 at 8:12
0
\$\begingroup\$

You have been given the following tree structure make from dictionaries and lists

{'snapshot': {'outer': {'inner': {'dir1': {'blob': 
          [{'file': '8ke45'}, {file1: '72d4kl'}]}, 
          'dir2': {'blob': [{'file1': 'fa65e'}]}}, 
           'something': {'blob': [{'thing1': '8447v'}]}}}

The dictionary contains all the directories and blobs(arbitrary file) in a given directory, in this case 'snapshot,' which contains the directory outer and no blobs. 'Outer' has all of its corresponding directories and blobs and so on until the end of the branch. Blobs objects are a dictionary with the key 'blob' and the value of a list of dictionaries containing the filename and content hash.

the tree looks like:

snapshot
    |_outer 
        |__ inner 
        |     |__dir1
        |     |   |__file
        |     |   |__file1
        |     |__dir2
        |     |   |__somefile
        |     |__another_file
        |__ something
            |__thing1

the objective to create trees files, wherein each directory is the hash of the hash of the underlying directories or blobs.

e.g the 'inner' file:

    name: 7j3429ds 
    contents: tree 8340dnwh28a          --di1
              tree sh2991ka86n          --dir2
              blob 12046bshs63          --anotherfile

You may hash the file using any known checksum ie. sha1, md5 ect. This is an example for the hash of the contents of a file:

def hash_(name):
    hash_object = hashlib.sha1(bytes(str(name), encoding='utf-8'))
    hex_dig = hash_object.hexdigest()
    return(hex_dig)

An Example of the final output given the dictionary:

{'snapshot': {'inner': {'dir1':{'blob': [{'file': '8ke4528dgsk'}},  
                        'dir2': {'blob': [{'file1': 'fa65ek97n37'}]}}} 

should look as such:


45334423112
    |_ds498kdh72b 
        |__ ak37ka729sm
        |     |__193bal7q8gl
        |__ o8pdn279ax8
              |__9y728s7ndsn

note the names of the files are just random hashes in the example when actually computing the hashes, the hash should consist of the hashes or all trees and blobs contained within that tree

45334423112 contents:

tree ds498kdh72b

ds498kdh72b contents:

tree ak37ka729sm
tree o8pdn279ax8

ak37ka729sm contents:

blob 8ke4528dgsk
blob fa65ek97n37

note that the blobs are the value of the filname key in the lowest level directory of the tree ie.

'dir1':{'blob': [{'file': '8ke4528dgsk'}]}

The winning criterion is the shortest solution.

If the question is seemingly vague, please comment on what you're unfamiliar with. Good luck ;)

| |
\$\endgroup\$
  • 1
    \$\begingroup\$ would any which way mean returning the first character of the file name is fine? :P \$\endgroup\$ – ASCII-only May 27 '18 at 11:08
  • 1
    \$\begingroup\$ "any way you want" is too open to abuse. x => 0 is a valid hash function, just have a lot of collisions. \$\endgroup\$ – user202729 May 27 '18 at 11:10
  • \$\begingroup\$ Cool thanks, very valid feedback :) \$\endgroup\$ – Charl Kruger May 27 '18 at 11:20
  • \$\begingroup\$ Your example has a mismatching [. (besides -- actually, the sandbox is relatively inactive, it's hard to get feedback) \$\endgroup\$ – user202729 May 27 '18 at 13:41
0
\$\begingroup\$

Given some lists of strings containing only lowercase letters, slice the first few (1 to length) characters for each string in each list, so that when each list is joined without separating symbol, it can't be any other list's possible expression.

For example, for {[ab,cd],[abcd]}, {ac,a} is valid, but {abc,a} is not because abc can also mean [abcd].

You can assume the result exist. If more than one solution, either output all of them or one of them. Shortest code win.

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

Link the pairs of points

Given some pairs of points on a plane, connect each pair with a simple polygonal chain such that any two different chains don't have any common points. The points won't necessarily be integral. Any two points in the input won't overlap.

Samples:

[{(0,1.2),(1,2)}] -> [{(0,1.2),(2.6,1),(1,2)}] # Output doesn't need to be optimized
[{(0,0),(1,1)},{(1,0),(0,1)}] -> [{(0,0),(1,1)},{(1,0),(9999,0),(0,999),(0,1)}]

Reasonable I/O method allowed. Code-golf, shortest code win.

| |
\$\endgroup\$
  • \$\begingroup\$ I think you want to describe a simple polygonal chain. \$\endgroup\$ – user202729 May 28 '18 at 5:37
  • \$\begingroup\$ Is there any two points in the input that have the same coordinate? \$\endgroup\$ – user202729 May 28 '18 at 5:38
  • \$\begingroup\$ @user202729 The chain shouldn't intersect with itself and other chains \$\endgroup\$ – l4m2 May 28 '18 at 10:23
  • \$\begingroup\$ Is it a sufficient answer to sort the points by angle and join them all up in order, and if not why not? \$\endgroup\$ – Peter Taylor May 29 '18 at 14:13
  • \$\begingroup\$ @PeterTaylor You are to link each pair, not to link all of the points together \$\endgroup\$ – l4m2 May 29 '18 at 14:22
0
\$\begingroup\$

Shortest code to generate a random ethereum address with matching private key pair

Ethereum is a blockchain platform. An Ethereurem public address consist of 256 bytes based on ECDSA encryption.

It’s very simple challenge about a service available on many websites without registering (which most of the time involve going on website main page and click the generate button) : generate a random ethereum address !

What is an Ethereum address ?

An Ethereum address is a public/private key pair hence the public address is just the public part of the key pair. Here’s an example of Ethereum address with private key after :

0x7bbaf5E447B089C5e0a802d07A2bc63870e90f05 651bfdb66c839ae0aa4ed59bbada63c13876feb60a89ca6dacc63a7b04cf4b60

Every private key and public key is valid as long as the length above is the same. But you need to output a private key which match a public key (It’s possible to retrieve the public key from the private key).
Example online generators : https://vanity-eth.tk/ https://forkdelta.github.io https://etherdelta.com https://walletgenerator.net/

Example code to generate an address in bash :

#!/bin/sh

keys=$(openssl ecparam -name secp256k1 -genkey -noout | openssl ec -text -noout 2> /dev/null)

# extract private key in hex format, removing newlines, leading zeroes and semicolon
priv=$(printf "%s\n" $keys | grep priv -A 3 | tail -n +2 | tr -d '\n[:space:]:' | sed 's/^00//')

# extract public key in hex format, removing newlines, leading '04' and semicolon
pub=$(printf "%s\n" $keys | grep pub -A 5 | tail -n +2 | tr -d '\n[:space:]:' | sed 's/^04//')

# sha3 is a subset of the keccak familly function. Thus keccak is included in most sha3 tools.
addr=0x$(echo $pub | keccak-256sum -x -l | tr -d ' -' | tail -c 41)

echo 'Private key:' $priv
echo 'Address:    ' $addr

Rules

  • The resulting public address shouldn’t be fully random : the last byte should be 0. This can be achieved by generating about 256 random address and selecting the first which has a trailing null byte (the probability is 1∕256).
  • Print or return : the public key along the matching private key as a string.
  • The solidity has native functions to generate an address, so you don’t have to understand how to generate an address

 Winner

The code which uses the fewest bytes.

| |
\$\endgroup\$
  • \$\begingroup\$ Please explain what is unclear : codegolf.stackexchange.com/q/165724/50239 \$\endgroup\$ – user2284570 May 30 '18 at 8:21
  • \$\begingroup\$ Fetching the result of an online generator though an HTTP request is valid if you can get a public key with 1 or several null bytes at the end. Fetching results from an online source is usually a loophole forbidden by default. If you allow it here one could write their own generator which already handles the trailing zero requirement, put it on a website and post curl <some link shortener> as answer. \$\endgroup\$ – Laikoni May 30 '18 at 9:22
  • \$\begingroup\$ @Laikoni : yes. I’m accepting curl answers… What’s the problem. This question does it to : codegolf.stackexchange.com/q/152844/50239 \$\endgroup\$ – user2284570 May 30 '18 at 9:36
  • \$\begingroup\$ The linked question explicitly states Standard loopholes are obviously not allowed, so I don't think that would be allowed. The general problem is that code-golf is about performing a certain task in the fewest number of bytes. Outsourcing the code which solves the task on a website and submitting code to the challenge which just gets the result from this page is thus generally not allowed, as your submitted code actually performs a different task, while the actual code that solves the task is not part of the score. \$\endgroup\$ – Laikoni May 30 '18 at 9:50
  • \$\begingroup\$ @Laikoni is it fixed now ? \$\endgroup\$ – user2284570 May 30 '18 at 11:43
0
\$\begingroup\$

Create random recurrences with their solutions

(This is a work in progress and I would love any help please. First, how do I copy the wiki entry into this question without making a mess of the math as I have below? PPCG doesn't appear to support math rendering like the wiki does.)

The task is to create random recurrence relations that are solvable using the Akra-Bazzi method along with the solutions. This method solves recurrences of the form:

enter image description here

The conditions for usage are:

  • sufficient base cases are provided
  • a_i and b_i are constants for all i
  • a_i > 0 for all i
  • 0 < b_i < 1 for all i
  • |g(x)| = O(x^c), where ''c'' is a constant and ''O'' notates Big O notation
  • | h_i(x) | = O(x/(log x)^2) for all i
  • x_0 is a constant

The asymptotic behavior of T(x) is found by determining the value of p for which enter image description here and plugging that value into the equation

enter image description here

| |
\$\endgroup\$
  • 1
    \$\begingroup\$ can you dumb this down so that people like me can understand it? maybe some examples? \$\endgroup\$ – don bright Jul 7 '18 at 2:48
  • \$\begingroup\$ @donbright Yes absolutely. I need to rewrite using Mathjax too now it is supported. I will work on it next week. \$\endgroup\$ – user9207 Jul 7 '18 at 7:21
  • 1
    \$\begingroup\$ I have rewritten your post with code-golf delimited mathjax, here on pastebin: pastebin.com/TLM4D0Ri \$\endgroup\$ – don bright Jul 7 '18 at 14:54
0
\$\begingroup\$

Introduction

Often computers are used to perform consecutive jobs. Sometimes the order of doing these jobs does not matter. Other times there are dependencies between jobs that restrict the order that jobs can be performed. Additionally, jobs may require significant resources to store results, so it may be necessary to first schedule those jobs that will consume previous results before performing jobs that produce even more results. Furthermore, there may be significant costs to change from one type of job to another. The challenge then becomes finding the optimal execution order of jobs.

Challenge

Allow me to illustrate the problem with an example. Consider a list of 10 jobs, numbered 0 to 9. Each of these jobs can be dependent on zero or more other jobs. (Assume there are no circular dependencies.) For example:

Job : Dependent on
---   ------------
0   : 8
1   : 6
2   :
3   : 0 6 9
4   : 7 9
5   : 2
6   : 4 8
7   :
8   : 9
9   :

This can be illustrated graphically as follows:

Illustration

One possible solution to this particular example is to perform the 10 jobs in the order: 9 8 7 4 6 0 2 1 3 5 While this solution satisfies the dependency requirements, it is not ideal. To see why, let us perform the jobs one at a time:

Job : Results stored in memory
---   ------------------------
9   : 9
8   : 8 9
7   : 7 8 9
4   : 4 8 9
6   : 6 8 9
0   : 0 6 9
2   : 0 2 6 9
1   : 0 1 2 6 9
3   : 1 2 3
5   : 1 3 5

After performing the first job (job 9), we only have the result of job 9 in memory. After performing job 8 we need to store the results of 8 and 9, and after job 7 we have the results of jobs 7, 8 and 9. After performing job 4 we find that the results of job 7 is no longer needed and we can discard that, leaving only the results of job 4, 8 and 9. Carrying on we find that the worst case memory usage is after job 1 when we have to store the results of 5 different jobs (0, 1, 2, 6 and 9).

As it turns out there is a better solution to this example, and that is to do the jobs in the order: 7 9 4 8 6 0 3 2 5 1 The memory usage is then:

Job : Results stored in memory
---   ------------------------
7   : 7
9   : 7 9
4   : 4 9
8   : 4 8 9
6   : 6 8 9
0   : 0 6 9
3   : 3 6
2   : 2 3 6
5   : 3 5 6
1   : 1 3 5

This time we only ever needed to store the results of 3 jobs in memory, instead of the 5 in the previous solution.

Finally, consider that each job is of a certain "type", and changing from one type to another is something that should be avoided. For example, let's say we have 3 types of jobs: A, B and C, and our 10 jobs in the example have the following types: Jobs 0-3 is type A, jobs 4-7 is type B, and jobs 8 and 9 is type C.

Job : Results stored in memory : Job Type Change
---   ------------------------ : ---------------
7   : 7                          B
9   : 7 9                        C
4   : 4 9                        B
8   : 4 8 9                      C
6   : 6 8 9                      B
0   : 0 6 9                      A
3   : 3 6                        .
2   : 2 3 6                      .
5   : 3 5 6                      B
1   : 1 3 5                      A

As you can see, we had to change the job type 8 times: B C B C B A B A

When minimizing job changes, while still keeping maximum memory usage to 3, we now find that the optimal solution is: 9 8 7 4 6 0 3 1 2 5

Job : Results stored in memory : Job Type Change
---   ------------------------ : ---------------
9   : 9                          C
8   : 8 9                        .
7   : 7 8 9                      B
4   : 4 8 9                      .
6   : 6 8 9                      .
0   : 0 6 9                      A
3   : 3 6                        .
1   : 1 3                        .
2   : 1 2 3                      .
5   : 1 3 5                      B

This solution require only 4 job type changes (C B A B), while still only needing memory to store 3 results.

The solutions to this example that I presented here was found using a brute force search, ie going through every permutation of job order. From doing this I can tell you that this example has 1485 solutions that satisfy the dependency requirements. Of these 1485 solutions only 15 solutions require memory for no more than 3 results. Of these 15 solutions only 2 require only 4 job changes. The one is shown above (9 8 7 4 6 0 3 1 2 5). The other is: 9 8 7 4 6 0 3 2 1 5.

Unfortunately, brute force is not viable when the total number of jobs increase beyond 10, eg 100. The challenge is to come up with an algorithm that can find the optimal solution (or any one of them if there are more than one) using an algorithm that significantly outperforms brute force.

Example Input and Output

The input to the algorithm is a list of N jobs numbered 0 to N-1, each with a job type (A-Z) followed by a list of zero or more dependencies, eg:

0, A, 8
1, A, 6
2, A
3, A, 0 6 9
4, B, 7 9
5, B, 2
6, B, 4 8
7, B
8, C, 9
9, C

The output of the algorithm is the optimal execution order, eg:

9 8 7 4 6 0 3 1 2 5

Answers may be presented in any programming language or even pseudo code. I will translate them all to C++ and test them for correctness against the brute force algorithm using randomly generated inputs. The winner will be the algorithm that is fastest (and correct).

| |
\$\endgroup\$
  • \$\begingroup\$ So, is this fastest-algorithm or fastest-code? \$\endgroup\$ – wastl Jun 9 '18 at 18:35
  • \$\begingroup\$ What if there is a solution with memory 2, job changes 3, and one with memory 3, job changes 2? In other words, which one is given priority? \$\endgroup\$ – wastl Jun 9 '18 at 18:39
  • \$\begingroup\$ @wastl I think fastest-code would be the easiest because it might get difficult determining which is the fastest-algorithm. Least memory usage has a higher priority than least job changes. \$\endgroup\$ – Barnett Jun 12 '18 at 9:36
0
\$\begingroup\$

I want to do this, Render an ASCII maze but with ascii pipe characters.
I know this is similar, but I think the extra logic required to figure out which character to put at each position makes this sufficiently different.

here is what I am thinking of asking.

Write code that replaces non whitespace characters in a string with ascii pipe characters depending on adjacency to other non-whitespace characters.
this will create something like a maze where non-whitespace characters are the walls, and whitespace is abscence of walls here are the rules

your code should take its input from stdin and output to stdout

This table shows the correct output character for each combination of adjacent walls in directions: Left, Down, Up, and Right

 L D U R -> Output
 0 0 0 0 -> any non-whitespace character
 1 0 0 0 -> ─
 0 0 0 1 -> ─
 1 0 0 1 -> ─
 0 1 0 0 -> │
 0 0 1 0 -> │
 0 1 1 0 -> │
 1 1 0 0 -> ┐
 1 0 1 0 -> ┘
 0 1 0 1 -> ┌
 0 0 1 1 -> └
 1 1 1 0 -> ┤
 1 1 0 1 -> ┬
 1 0 1 1 -> ┴
 0 1 1 1 -> ├
 1 1 1 1 -> ┼

if characters are on the edge of a string then they should treat the outside as whitespace

This will be a code golf challenge

| |
\$\endgroup\$
  • 1
    \$\begingroup\$ codegolf.stackexchange.com/q/80634/194 ? \$\endgroup\$ – Peter Taylor Jun 6 '18 at 8:51
  • \$\begingroup\$ I didn't see that one, but I still think this is different, because this does not require specific characters as input, the input can be any string \$\endgroup\$ – JoshM Jun 6 '18 at 13:59
  • \$\begingroup\$ Can you add some test cases? \$\endgroup\$ – 3D1T0R Jun 6 '18 at 18:18
  • 1
    \$\begingroup\$ Although there are some minor differences, this was probably be closed as a duplicate. \$\endgroup\$ – wastl Jun 6 '18 at 19:23
  • \$\begingroup\$ i'll try to think of something to make this one different \$\endgroup\$ – JoshM Jun 6 '18 at 19:30
0
\$\begingroup\$

N represented with only 1s in any base from 2 to N-2?

This is mostly a less interesting special case of Repdigit Base Finding so I won't submit.

Any positive integer N can be expressed as 11 in base N-1 or as N concatenated 1s in base 1. Let's call those the trivial cases in which N can be represented using only 1s. Let's call any other "all 1s" representation non-trivial. Some examples:

  • 7 has an "all 1s" representation in base 2, so 7 has a non-trivial "all 1s" representation.
  • 16 has no non-trivial "all 1s" representation.
  • 11 itself has no non-trivial "all 1s" representation by my definition because it is "all 1s" in base 10, which is 11-1.

Challenge

Provide a program/function that produces one of two distinct, consistent values for whether or not an integer N > 3 has a non-trivial "all 1s" representation in a base between 2 and N-2.

| |
\$\endgroup\$
  • \$\begingroup\$ I was thrown off by the 11 example, because there is quite clearly a way to express that using only 1, but then I realized that it's trivial because base 10 is base n-1 in that situation. That might be a good note to add. \$\endgroup\$ – Kamil Drakari Jun 6 '18 at 15:54
  • \$\begingroup\$ This should generate the truthy numbers up to 1000 \$\endgroup\$ – Kamil Drakari Jun 6 '18 at 20:37
  • \$\begingroup\$ @KamilDrakari very nice, thanks. I wonder how many numbers have more than one such base (like 31)? That's an entirely different challenge. \$\endgroup\$ – ngm Jun 6 '18 at 20:42
  • \$\begingroup\$ I updated the code to search for duplicates, but could only find 31 and 8191. Golfed to fit the link in a comment \$\endgroup\$ – Kamil Drakari Jun 6 '18 at 21:22
  • \$\begingroup\$ Table seems wrong \$\endgroup\$ – l4m2 Jun 7 '18 at 4:20
  • \$\begingroup\$ Not an exact dupe, but closely related: codegolf.stackexchange.com/q/75623/194 . \$\endgroup\$ – Peter Taylor Jun 7 '18 at 8:01
  • \$\begingroup\$ Note that these are numbers of the form (b**x - 1) / (b-1) for integer b > 1 and integer x > 2. \$\endgroup\$ – Peter Taylor Jun 7 '18 at 8:03
  • 1
    \$\begingroup\$ Also: OEIS A053696. Either your reference implementation was broken or you didn't remove duplicates. \$\endgroup\$ – Peter Taylor Jun 7 '18 at 8:10
  • \$\begingroup\$ @PeterTaylor thank you for alerting me to the other challenge, which is close enough for me to say this one is a dupe (at least and easier and less interesting special case.) \$\endgroup\$ – ngm Jun 8 '18 at 18:24
  • \$\begingroup\$ Thanks for using the Sandbox! \$\endgroup\$ – JayCe Jun 9 '18 at 23:10
0
\$\begingroup\$

# Proposed Question #

List the amount of factors for a given number.

For Example:

If given 1936, the output should be 15 (as 1936 has 15 factors)
If given 196, the output should be 9 (as 196 has 9 factors)

Test cases:

  • 64 - Outputs 7
  • 196 - Outputs 9
  • 1936 - Outputs 15

Scoring:

Code Golf - Least number of bytes for each language wins (No answer)

I have made my own in JavaScript - 143 Bytes.
Available here: https://glot.io/snippets/f1tl0vrnmy
To use different numbers, change the console.log(f(64).length) to console.log(f(###).length) where ### is your desired number.

BTW, if JavaScript or similar, only the defining function is considered in code length. The method of outputting (eg. console.log) does not count.

| |
\$\endgroup\$
  • \$\begingroup\$ I'm not sure as I'm not a native speaker, but isn't that called "divisor" (not factor)? \$\endgroup\$ – wastl Jun 9 '18 at 16:26
  • 1
    \$\begingroup\$ I fear it would get closed as a duplicate of this one \$\endgroup\$ – JayCe Jun 9 '18 at 23:08
  • \$\begingroup\$ Exact duplicate. \$\endgroup\$ – user202729 Jun 10 '18 at 3:30
  • \$\begingroup\$ @wastl depends which country you are in (America or the rest of the world). \$\endgroup\$ – Suda Jun 11 '18 at 1:41
  • \$\begingroup\$ @JayCe i don't think so the, as that is the prime factorisation of the number, where i am asking for the factor count. But, as with user202729, it is an exact duplicate. So, Thanks guys :D \$\endgroup\$ – Suda Jun 11 '18 at 1:43
  • \$\begingroup\$ Thanks for using the Sandbox :) \$\endgroup\$ – JayCe Jun 11 '18 at 2:06
0
\$\begingroup\$

Block partite a string

Inspiration.

Consider a list l, consisting of numbers. Define a block operation at index i on the list l to be the act of moving 3 consecutive elements starting from i in l to the end.

Example:

l, i (1-indexing) -> l (after applying block operation at index i)
[1,2,3,4,5], 1 -> [4,5,1,2,3]
[1,2,3,4,5,6,7], 3 -> [1,2,6,7,3,4,5]

Given a list consisting of only 0 and 1, your challenge is to partite it so that zeros are at the front, and ones are at the back, using only block operations. Output should be the indices in the order they are applied on the list.

Because this is impossible for the list [1,0,1,0], the list length is guaranteed to be at least 5.

Also (as a bonus, to avoid handling special cases) there is at least 5 ones and 5 zeroes.

Test cases (1-indexing)

(there are other valid outputs)

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

Use this script to generate more test cases. (only input)

Winning criteria

This is , the shortest code in bytes wins.
Don't let code-golf languages discourage you from posting your solution. Try to come up with as short as possible solution for any language.

Note

  • [atomic-code-golf] variant.
  • You're free to brute force, although I expect that a non-brute-force solution would be much shorter.
| |
\$\endgroup\$
  • 1
    \$\begingroup\$ @HatWizard This is the code-golf variant, I'm sure that I didn't post it. The other one is atomic-code-golf. \$\endgroup\$ – user202729 Jun 10 '18 at 13:16
0
\$\begingroup\$

Which number nearest?

We say 2018 is near 2000, but not 2018 is near 2030, though |2030-2018|<|2000-2018|. Given some pairs of numbers (a,b) and two numbers g>0 and x, find an x+t for min((|t|c+g)*bd) for t as a real number making (x+t) mod a = 0, (a,b) as one of the pairs. You can decide c to be 1 or 2, and d to be 1 or -1, as long as it's constant.

Samples: (c=1, d=1)

In: {(1000, 1), (10, 100)}, g=1, x=2018
Out: 2000

In: {(1000, 1), (10, 1)}, g=1, x=2018
Out: 2020

In: {(1, 1), (10, 1)}, g=1, x=2018
Out: 2018

| |
\$\endgroup\$
  • 1
    \$\begingroup\$ I think this is an interesting challenge, but you really need some nicely formatted formulas here. The plain-text forms are hardly readable. \$\endgroup\$ – Adám Jun 13 '18 at 18:06
  • \$\begingroup\$ @Adám MathJax is currently not supported. \$\endgroup\$ – user202729 Jun 14 '18 at 1:42
  • 1
    \$\begingroup\$ I'm confused. Why wouldn't we say 2018 is near 2030? It seems grammatically fine to me. \$\endgroup\$ – Jo King Jun 14 '18 at 10:20
  • \$\begingroup\$ @JoKing 2030 is not that integer, and saying it near another strange number is quite meaningless \$\endgroup\$ – l4m2 Jun 14 '18 at 10:23
  • \$\begingroup\$ Sorry? I think there's a language barrier here. I'm not sure what you mean. \$\endgroup\$ – Jo King Jun 14 '18 at 10:27
  • \$\begingroup\$ I guess the intent is to find the nearest round number, with the (a,b) pairs deciding what a "round number" is. I agree that better formatting would help with readability, and more importantly some explanation text: what is c, what is d, what does g's value affect, and in general how did the min((|t|c+g)*bd) formula come about? \$\endgroup\$ – sundar - Reinstate Monica Jun 25 '18 at 7:37
0
\$\begingroup\$

Is there a dangling else?

Define a statement as follows (Backus-Naur form) (based on Java syntax):

statement ::= ";"
  | "if(true)" <statement>
  | "if(true)" <statement> "else " <statement>

Example valid statements:

;
if(true);else ;
if(true);else if(true);else ;

Example invalid statement that is valid Java syntax, but considered invalid for simplicity:

if(false);
if(true);else;
if(1>0);else ;
System.out.println("This is invalid");

Your task is, given a valid statement, determine if it contains a dangling else (that is, it can be parsed into more than one ways)

Test cases

Truthy test cases (contains a dangling else)

Presented in the format {input}¶ -> {parse 1}¶ -> {parse 2}

if(true)if(true);else ;
 -> if(true){if(true);}else ;
 -> if(true){if(true);else ;}

if(true)if(true);else if(true);else ;
 -> if(true){if(true);else if(true);}else ;
 -> if(true){if(true);}else{if(true);else ;}

if(true);else if(true);else if(true)if(true);else ;
 -> if(true);else if(true);else if(true){if(true);}else ;
 -> if(true);else if(true);else if(true){if(true);else ;}

Falsy test cases (uniquely parsed)

if(true)if(true)if(true);
if(true)if(true);else ;else ;
if(true);else if(true);else if(true);else ;
| |
\$\endgroup\$
0
\$\begingroup\$

Quine of Hanoi

Objetive

Make a program that print a rearranged version of itself

Rules

  • Your program will consist of newlines and 3 blocks : A, B and C where each block will have distinct and nonzero lengths, i.e. 0 < length(A) < length(B) < length(C).
  • The output will be based on the order of the code blocks and newlines, it will be a new arrangement that progresses toward a solved state by one move unless it is already solved, following Tower of Hanoi rules.

For example:

CA
B

Will print

C
B
A

Additional rules

  • Your program don't have to handle invalid orders, e.g. CAB
  • You have to handle at least one configuration of each group (but not necessarily all of them).
  • The order of the lines is irrelevant.

For example

CA
B

CAN print

B
C
A

Examples

#Group 0 - will output itself
CBA

#Group 1 - will output one of group 0
A\nCB
CB\nA

#Group 2 - will output one of group 1
A\nB\nC
A\nC\nB
B\nA\nC
B\nC\nA
C\nA\nB
C\nB\nA

#Group 3 - will output one of group 2
CA\nB
B\nCA

Winning

This is , so the one with the shortest code (A+B+C) wins

| |
\$\endgroup\$
  • \$\begingroup\$ To me, this seems like a "challenge rules inferred from test cases" situation. Specifically, it seems that the desired behavior is "when the code is run, it outputs a new arrangement that progresses toward a solved state by one move unless it is already solved", but you just say "follow Tower of Hanoi rules". \$\endgroup\$ – Kamil Drakari Jun 15 '18 at 14:43
  • \$\begingroup\$ @KamilDrakari indeed, can I use your description in the challenge? \$\endgroup\$ – Rod Jun 15 '18 at 14:45
  • \$\begingroup\$ I don't mind, go ahead. \$\endgroup\$ – Kamil Drakari Jun 15 '18 at 14:47
0
\$\begingroup\$

Most times a loop

Given a positive integer n. For an array of length n, each two element of which are different, repeatedly rearrange it using the same permutation till it's the same as original. How many times was the array rearranged at most?

Samples:

input output example permutation
1     1      [a1]
2     2      [a2 a1]
3     3      [a3 a1 a2]
4     4      [a4 a1 a2 a3]
5     6      [a3 a1 a2 a5 a4]
| |
\$\endgroup\$
  • \$\begingroup\$ Must the permutation be outputted, or only the number of steps? \$\endgroup\$ – user202729 Jun 14 '18 at 11:19
  • \$\begingroup\$ @user202729 only the one number \$\endgroup\$ – l4m2 Jun 14 '18 at 11:25
  • 1
    \$\begingroup\$ In short: Given a number n, what is the largest order of an element in a symmetric group on n letters? \$\endgroup\$ – user202729 Jun 14 '18 at 11:39
  • 1
    \$\begingroup\$ You might want to clarify that the input is the length of the array. Since the question starts "Given an array", I assumed the input was an array and was confused at first. (I think it needs more elaboration in general too.) \$\endgroup\$ – sundar - Reinstate Monica Jun 16 '18 at 8:21
  • \$\begingroup\$ @sundar problem edited; what if given an array where some elements may be same? (maybe turns into another problem) \$\endgroup\$ – l4m2 Jun 16 '18 at 10:57
  • \$\begingroup\$ oeis.org/A000793 \$\endgroup\$ – Peter Taylor Jun 19 '18 at 9:06
  • \$\begingroup\$ can you show the steps of doing a permutation? for dumb dumbs like me? \$\endgroup\$ – don bright Jul 7 '18 at 2:32
0
\$\begingroup\$

Rotational symmetry in which bases from 2 to 36

A number (here, a non-negative integer) is rotationally symmetric if it "looks" the same after being rotated 180 degrees. For example, 69 (heh.) Here's a related challenge.

We're going to consider bases from 2 to 36, using the symbols 0-9A-Z as the digits. We're going to be generous with what digits are rotationally similar. Each of the following pairs will qualify (order not relevant):

00, 11, 22, 55, 69, 88, B8, D0, DD, E3, I1, L7, S5, SS, Z2, XX, ZZ

The challenge

Given a non-negative integer n in base 10, write a program or function that produces a list of bases from 2 to 36 in which the n is rotationally symmetric.

Input and output

Any reasonable input format is allowed (the integer itself, its character representation, an array of digits, an array of digits as characters.)

Any output format that communicates the desired result in an unambiguous way is acceptable. For example, a 35 element array of truthy/falsey values. If it's easier to include base 1 (always truthy) that's fine too.

Rules

This is . Fewest bytes in each language. Usual rules apply.

| |
\$\endgroup\$
  • \$\begingroup\$ Why take input in base 10? I don't think it would make it too easy to take input in other bases ... \$\endgroup\$ – wastl Jun 25 '18 at 19:18
  • \$\begingroup\$ this is fun, but are there examples? im a bit slow on the uptake \$\endgroup\$ – don bright Jul 7 '18 at 2:13
0
\$\begingroup\$

Challenge

n=2πr

Given an input, n, print a circle with the circumference of n characters.

Rules

  • The characters for the circumference of the circle can be any non-whitespace character
  • Shapes don't have to be an amazing circle, kinda roundish shapes are still valid
  • The circle can have a small gap, but no overlap

Examples

Input: 1
Output:
o

Input: 2
Output:
oo

Input: 3
Output:
oo
o

Input: 7
Output:
 ooo
o   o
 oo

Input: 20
Output:
  oooooo
 o      o
o        o
o        o
 o      o    
  oooooo
| |
\$\endgroup\$
  • 4
    \$\begingroup\$ Objective valid criteria please? \$\endgroup\$ – user202729 Jun 26 '18 at 2:19
  • \$\begingroup\$ (BTW SE won't allow you to post a title with <15 chars. NBSP and some ZWSP can reduce it to 7, but no less.) \$\endgroup\$ – user202729 Jun 26 '18 at 2:20
  • 1
    \$\begingroup\$ Also, most languages will suffer from the floating inaccuracy of \$\pi\$ or trigonometric functions (\$\sin\$ or \$\cos\$), so you should say "although theorically it must work for all input, in practice your program only need to work with \$n\le1000\$ (or some other bounds) \$\endgroup\$ – user202729 Jun 26 '18 at 2:28
  • 1
    \$\begingroup\$ Thank you all for the feedback! The valid criteria is a very valid point, i'm working on making my own solution right now so I have something I can give to reproduce. I am aware of the title limit, I'm trying to come up with a better title before it is posted. And I will think about the inaccuracy of pi, because that could cause some headaches. Thank you again! :) \$\endgroup\$ – GammaGames Jun 26 '18 at 4:27
0
\$\begingroup\$

Shortest code to send an html s/mime signed message with one attachment over smtps

Simple challenge : use a valid RSA based security certificate in order to sign message according to s/mime rules and send it over smtp over TLS on port 465 (or starttls on port 25).

Rules :

  • The program parameters takes an ʜᴛᴍʟ string consisting of message body ; a message subject as string ; a sender address as string ; and list of recipients address.
    They can be obtained either as function/class parameters or program arguments or read from keyboard input.
  • The security certificate is read from an hardcoded file name of your choice or a hardcoded non empty string.
    It can be in the format of your choice.
  • The attachment is read is read from an hardcoded file name of your choice or 2 non empty hardcoded strings (1 for filepath and the other 1 for content)
  • The s/mime signing rules state that message body should be signed and other part shoudln’t be signed, this means in practice that data stating the message is in the html format and all data about attachments should be signed (subject priority, and e‑mail addresses aren’t signed).
  • When I say you have free choice, just pick up the solution using the fewest bytes.

 Winner

The code which uses the fewest bytes.

| |
\$\endgroup\$
  • \$\begingroup\$ I dont understand, what's the point in giving both the filepath and the content? Is the content enough? \$\endgroup\$ – user202729 Jun 27 '18 at 5:04
  • \$\begingroup\$ @user202729 Inside e‑mail data, a valid attachment consists of a file path and it’s data. Otherwise, does the question looks Ok ? \$\endgroup\$ – user2284570 Jun 27 '18 at 8:52
  • \$\begingroup\$ One problem with this type of "minimal code to do a task over a protocol" question is that it's not clear how much of the protocol must be implemented. E.g. should the client handle grey-listing? \$\endgroup\$ – Peter Taylor Jun 29 '18 at 8:50
0
\$\begingroup\$

Earth mover's distance

Dupe check: Do we already have a challenge about the Earth mover's distance? Some possibilities could be to compute it for a 1D array, a 2D array, or a circle.

| |
\$\endgroup\$
  • \$\begingroup\$ Not as such, but it's basically just linear programming so you'd want to avoid creating a dupe of codegolf.stackexchange.com/q/156287/194 . I don't recall any non-integer linear programming questions; the technique has been used in some KotH answers, but I think they encode the solution rather than the solver. \$\endgroup\$ – Peter Taylor Jun 29 '18 at 8:45
0
\$\begingroup\$

Fewest instructions to copy bytes in memory in WebAssembly.

Implement the functionality for copying bytes in memory in WebAssembly.

Rules

  • Use WebAssembly, written in wast (the text format).
  • Any of the WebAssembly instructions are fine.
  • In calling copy, it doesn't need to worry about overriding an existing string.
  • Doesn't need to worry about the strings being too large to fit into memory, strings will be reasonable size and wont overflow over the end. For example, the total memory is 10000 bytes, so strings might be 100 bytes and only go to 5000 in the memory. (But those aren't actual hardcodable values).
  • No calling JavaScript functions.
  • The string "Hello World" starts of at position 0 in memory. Copy this string to random places in memory and log it, as shown in the xample below.

The winning answer is the one with the fewest WebAssembly instructions. That is, feel free to have a functions in WebAssembly, just no calling or importing JavaScript functions.

Example

To get started, here is the start of the WebAssembly module:

// example.wast
(module
  (memory (export "mem") 1)
  (data (i32.const 0) "Hello World")
  ;; instructions counting starts from here:
  (func (export "copy")
    (param i32) ;; existing start index
    (param i32) ;; size in bytes
    (param i32) ;; new index to copy to
    ...))

And here is how to load it, as well as the tests:

// example.js
WebAssembly.instantiateStreaming(fetch('example.wasm'), {}).then(mod => {
  var exports = mod.instance.exports
  var i8 = new Uint8Array(exports.mem)
  var i = 200 + rand(500)
  exports.copy(0, 11, i)
  var i2 = 1000 + rand(500)
  exports.copy(i, 11, i2)
  console.log(i, getString(i, 11))
  console.log(i2, getString(i2, 11))

  function rand(size) {
    return Math.floor(Math.random() * (size + 1))
  }

  function getString(index, size) {
    var string = ''
    for (var i = index; i < index + size; i++) {
      string += String.fromCharCode(i8[i])
    }
    return string
  }
})

Resources

Potentially useful resources:

| |
\$\endgroup\$
  • \$\begingroup\$ It's been a few days, wondering if I could post this :) \$\endgroup\$ – Lance Pollard Jul 10 '18 at 3:02
  • 1
    \$\begingroup\$ Limiting this challenge to wast only will probably result in this question not going over well with the people on this stack exchange. \$\endgroup\$ – fəˈnɛtɪk Jul 10 '18 at 21:46
1
76 77
78
79 80
100

You must log in to answer this question.

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