457
\$\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\$
  • \$\begingroup\$ How are tags added to questions? \$\endgroup\$ – guest271314 Jan 9 at 7:51
  • \$\begingroup\$ @guest271314 You can use this markup to create a tag in a draft: [tag:code-golf] \$\endgroup\$ – DJMcMayhem Aug 29 at 15:19
  • \$\begingroup\$ Why no featured anymore? Can't we have it auto-added or something? \$\endgroup\$ – JL2210 Sep 26 at 15:57
  • 1
    \$\begingroup\$ @JL2210 We now have a permanent info box that links to the Sandbox, so the featured tag isn't necessary \$\endgroup\$ – caird coinheringaahing Sep 29 at 13:43
  • \$\begingroup\$ I think the sentence 'replace the post here with a link to the challenge and delete it' may specify that the deletion should be done immediately . \$\endgroup\$ – AZTECCO Oct 5 at 19:39

2559 Answers 2559

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

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

The challenge

  • Write a Discord bot with a single command, !oldest, that gives the oldest user in the server that the command that was run in.

  • Gracefully failing in DM channels is not required.

  • Assume the bot's token is this invalid token: MjM4NDk0NzU2NTIxMzc3Nzky.CunGFQ.wUILz7z6HoJzVeq6pyHPmVgQgV4.
    If the token is compressed in the program, provide instructions on how to change it so I can test it.

Sample discord.py implementation

import discord
client = discord.Client()
@client.event
async def on_message(M):
 if(M.content=="!oldest"):
  N=sorted([x.id for x in M.server.members])[1]
  await client.send_message(M.channel, str(M.server.get_member(N)))
client.run("MjM4NDk0NzU2NTIxMzc3Nzky.CunGFQ.wUILz7z6HoJzVeq6pyHPmVgQgV4")
  1. Get a list of every user in the server
  2. Sort their snowflake IDs
  3. Print the username and discriminator of the member with the smallest ID.

No API for your language? Have fun.

Standard loopholes forbidden, etc, etc.

Shortest code in bytes wins.


Sandbox

I originally posted this question on the main site, but I deleted it, as it turns out I'm bad at writing these. Please forgive me.

\$\endgroup\$
  • 1
    \$\begingroup\$ I'm sure I've seen this already, but with comments saying that it needed a lot more information to be self-contained. It still needs a lot more information to be self-contained. \$\endgroup\$ – Peter Taylor May 5 '18 at 11:11
  • \$\begingroup\$ Yep. I've edited the question to clarify. \$\endgroup\$ – SIGSTACKFAULT May 5 '18 at 12:35
  • 2
    \$\begingroup\$ Are you talking about discord servers? Other than form the example this is not clear at all. What is a DM channel? What is a token in this context? \$\endgroup\$ – flawr May 5 '18 at 13:02
  • \$\begingroup\$ A: Clarify that you're talking about Discord B: When you make a challenge that requires a library does that mean I can use a library that conveniently has the command you're asking of? \$\endgroup\$ – IQuick 143 May 6 '18 at 2:12
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
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\$

You must log in to answer this question.

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