471
\$\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 '19 at 7:51
  • \$\begingroup\$ @guest271314 You can use this markup to create a tag in a draft: [tag:code-golf] \$\endgroup\$ – James Aug 29 '19 at 15:19
  • \$\begingroup\$ Why no featured anymore? Can't we have it auto-added or something? \$\endgroup\$ – S.S. Anne Sep 26 '19 at 15:57
  • 3
    \$\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 '19 at 13:43

2754 Answers 2754

1
80 81
82
83 84
92
0
\$\begingroup\$

Let's Play Countdown!

(The Numbers round this time)

Countdown is a British TV game show composed of three different styles of rounds; the letters round, the conundrum, and the numbers round.

The conundrum could be solved with the same program you'd make for the Letters round, so let's tackle the third option that hasn't been done yet!

Challenge

Take in a set of numbers. One of which is the "Target" number, and the rest are the building numbers.

The Countdown Number Round asks you to take the building numbers and to construct the Target number only using the four elementary operators. Every step must result in another strictly-positive integer (so non-perfect division is disallowed). Output the method to which you can construct the target number. If that's impossible, get as close as possible (above or below are scored the same). Numbers do not need to be used, but may NOT be reused.

Note - You will perform at most N-1 operations, where N is the number of building numbers. Every elementary operator takes in two inputs and provides one, so you "lose" one from your ranking every operation. That should give you an idea of the size of your output.

I/O is in any reasonable format, but target vs building numbers must be obviously distinct (either by the target being the first or the last number, or outside an array, or a different type, etc).

Output needs to explain exactly what operations are being performed on what numbers, and what the output for each operation would be, but can be done in whichever way seems reasonable.

Example I/O

In these examples, the first element is the target.

[888 100 2 75 3 1 10]
75-1=74
10+2=12
74x12=888

[766 22 10 8 3 1]
22+10=32
32x8=256
256-1=255
255x3=765 #You cannot get this one exactly, but one-off is close.

Sandbox Questions

I'm... like 85% sure this isn't anywhere here yet. I did a chunk of searching and couldn't find anything that fit the bill, so I think this is clear?

Any other neat examples you guys got?

||||||
\$\endgroup\$
  • 1
    \$\begingroup\$ As you say, I don't think we have exactly this challenge, but there are many similar ones. I doubt you will get anything besides brute forcing all possible arrangements then sorting them by nearness to the target. Separately, if there are multiple tying solutions you don't require that e.g. the shortest be output, correct? It is probably worth mentioning that. \$\endgroup\$ – FryAmTheEggman Feb 21 at 21:24
0
\$\begingroup\$

Iterative Quadratics

Recently, in my algebra class, we proved that the following process always stops at some point, so I thought it would be a cool challenge!

Input: Two reals a,b.

Output Non-negative integer

Challenge:

Given two reals a,b, initialize a count variable c to 0, consider the quadratic equation

x^2+ax+b

If this quadratic has real roots r,s (r<=s), increment the counter by 1, and replace a,b with r,s and repeat the process.

If the quadratic has complex roots, return c.

Test Cases

To be added.

||||||
\$\endgroup\$
  • \$\begingroup\$ you need to specify the precision required for stopping \$\endgroup\$ – qwr Mar 11 at 19:16
  • \$\begingroup\$ @qwr good catch. Any suggestions? \$\endgroup\$ – Don Thousand Mar 11 at 19:51
0
\$\begingroup\$

Doubly stochastic matrix

A doubly-stochastic matrix is a square matrix of non-negative real entries each of whose rows and columns sums to 1. Given a doubly-stochastic matrix, express it as a non-negative linear combination of permutation matrices, as is guaranteed to exist by the Birkhoff–von Neumann theorem.

TODO: Example, better explanation, test cases. If you want to develop and post this challenge, it's yours.

||||||
\$\endgroup\$
  • \$\begingroup\$ I liked this idea! May I work on this and give you credit? If I manage to do so before you, of course. \$\endgroup\$ – RGS Feb 24 at 19:33
  • \$\begingroup\$ @RGS You're very welcome to fully take it. \$\endgroup\$ – xnor Feb 26 at 2:01
0
\$\begingroup\$

Implement GF(2²)

Introduction to groups and fields

An additive group is a set with addition and negation defined. They must satisfy the following conditions:

  • \$0\$ is the additive identity.

  • Addition is associative.

  • For every \$x\$, the negation of \$x\$, \$-x\$ exists, and \$x + (-x) = (-x) + x = 0\$.

If addition is also commutative, the additive group is called abelian.

A field is an additive abelian group with multiplication and reciprocal defined. They must satisfy the following conditions:

  • \$1\$ is the multiplicative identity.

  • Multiplication is associative and commutative.

  • For every nonzero \$x\$, the reciprocal of \$x\$, \$x^{-1}\$ uniquely exists, and \$x\times x^{-1} = x^{-1}\times x = 1\$.

  • Multiplication distributes over addition.

Modular Arithmetic

For every positive integer \$n\$, you can define an additive abelian group as follows:

  • Define the set as integers from \$0\$ to \$n-1\$.

  • Define addition as usual addition with the result moduloed by \$n\$.

  • Define negation as usual negation with the result moduloed by \$n\$.

This group is denoted by \$ℤ_n\$. If \$n\$ is prime, multiplication can be analogously defined, making it a field. In particular, the operation tables of \$ℤ_2\$ are:

$$ \begin{array}{l|ll} + & 0 & 1 \\ \hline 0 & 0 & 1 \\ 1 & 1 & 0 \end{array} \begin{array}{l|ll} x & -x \\ \hline 0 & 0 \\ 1 & 1 \end{array} \begin{array}{l|ll} × & 0 & 1 \\ \hline 0 & 0 & 0 \\ 1 & 0 & 1 \end{array} \begin{array}{l|ll} x & x^{-1} \\ \hline 0 & \text{NaN} \\ 1 & 1 \end{array} $$

Galois Field GF(2²)

A Galois field \$\text{GF}(p^k)\$ emerges when one takes the set as polynomials over \$ℤ_p\$, and defines addition and multiplication as the usual operation with polynomial modulo, where the modding polynomial is irreducible and has degree of \$k\$. Since \$x^2+x+1\$ is an (in fact, the only) irreducible polynomial over \$ℤ_2\$ that has degree \$2\$, this results in \$\text{GF}(2^2)\$. Its operation tables are:

$$ \begin{array}{l|ll} + & 0 & 1 & x & x+1 \\ \hline 0 & 0 & 1 & x & x+1 \\ 1 & 1 & 0 & x+1 & x \\ x & x & x+1 & 0 & 1 \\ x+1 & x+1 & x & 1 & 0 \end{array} \begin{array}{l|ll} f(x) & -f(x) \\ \hline 0 & 0 \\ 1 & 1 \\ x & x \\ x+1 & x+1 \end{array} \\ \begin{array}{l|ll} × & 0 & 1 & x & x+1 \\ \hline 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 1 & x & x+1 \\ x & 0 & x & x+1 & 1 \\ x+1 & 0 & x+1 & 1 & x \end{array} \begin{array}{l|ll} f(x) & f(x)^{-1} \\ \hline 0 & \text{NaN} \\ 1 & 1 \\ x & x+1 \\ x+1 & x \end{array} $$

Your task is to implement the set and the operations. As a conseuqence, you must have:

  • The members of the set defined as constants (2-bit bitstring, an ASCII digit, or whatever). This won't contribute to the score.

  • Four codes that defines each operations, whose input(s) is/are as defined above.

Rules

  • Though defined as polynomials, the type and format of the inputs doesn't matter. You must have the same type for every input.

  • The type and format of the outputs doesn't matter either, but it must be the same as the input(s).

  • The reciprocal of \$0\$ must result in an "error" condition. This includes returning an errornous value, throwing an error, or terminating the program. It must halt.

  • Other invalid inputs fall in don't care situation.

  • Since there are multiple codes, the score for code golf is alloted by the sum of their lengths in bytes.

||||||
\$\endgroup\$
  • 1
    \$\begingroup\$ Related: GF(2^8) and GF(3^2), though neither asks for negation or multiplicative inverse. Also, A code that defines the set as a type can be problematic in many languages where the concept of "type" is not well-defined. I'd suggest to exclude it from the code size and just ask the answerer to provide the four values corresponding to \$0, 1, x, x+1\$ respectively. \$\endgroup\$ – Bubbler Feb 24 at 0:02
  • \$\begingroup\$ @DonThousand Requiring the uniqueness of a negation resolves the issue. Also, it would take too long to explain the "actual" definition of \$\mathbb{Z}_p\$. So I defined it with usual modulo. \$\endgroup\$ – Dannyu NDos Feb 24 at 1:25
  • \$\begingroup\$ @DonThousand \$(-a) + a = 0\$ implies \$(-(-a)) + (-a) = 0\$. So both \$a\$ and \$-(-a)\$ are additive inverses of \$-a\$. By uniqueness of additive inverse, it follows \$-(-a) = a\$. \$\endgroup\$ – Dannyu NDos Feb 24 at 1:57
  • \$\begingroup\$ @DannyuNDos Incorrect, you assume commutativity again. $a$ is a right inverse, and $-(-a)$ is a left inverse of $-a$ \$\endgroup\$ – Don Thousand Feb 24 at 2:03
  • \$\begingroup\$ @DonThousand The definition of group states that a left inverse must be the right inverse, and a right inverse must be the left inverse. Such inverse always uniquely exists. \$\endgroup\$ – Dannyu NDos Feb 24 at 3:21
  • \$\begingroup\$ @DannyuNDos That's my point. Your definition doesn't say that the right inverse = left inverse. \$\endgroup\$ – Don Thousand Feb 24 at 3:30
  • \$\begingroup\$ @DonThousand Oh my! So there was the flaw. I only remembered the definition, but not memorized it. Thanks anyways. \$\endgroup\$ – Dannyu NDos Feb 24 at 3:32
  • \$\begingroup\$ @DannyuNDos Yea, lol. Sheesh, that was a journey. \$\endgroup\$ – Don Thousand Feb 24 at 3:36
  • \$\begingroup\$ @DonThousand You only need a right zero and right inverses, then we get left zero and left inverses, and they are unique (we also don't have to demand that). Proof that right inverses are left inverses: \$(-a)+a=(-a)+a+0=(-a)+a+(((-a)+a)+(-((-a)+a)))=(-a)+(a+(-a))+a+(-((-a)+a))=((-a)+0)+a+(-((-a)+a))=((-a)+a)+(-((-a)+a))=0\$. Using this gives left zero: \$0+a=(a+(-a))+a=a+((-a)+a)=a+0=a\$. \$\endgroup\$ – Christian Sievers Feb 24 at 15:07
0
\$\begingroup\$

Shared Letters in consecutive numbers

Inspired by this puzzling question.

It turns out that, in English, every pair of consecutive integers (e.g. 0,1, 1,2, etc.) shares at least one letter when spelled out (e.g. zErO, OnE (or NOught, ONe); One, twO, etc).

Input

Any two non-negative integers (all natural numbers including 0) up to and including one googol. These can be input as any type you choose, but string representations must only use the characters 0123456789.,' (i.e. the numbers must not already be spelled out on input, but rather input as a numeral).

You can assume that the two numbers will be consecutive.

Some examples of valid inputs:

{1,2}
{"1","2"}
{1},{2}
{{"1"},{2}}
"123,245", "123,246"
"123.456", "123'457"

some examples of invalid inputs

{1,3}
{-1,0}
{1.1,1.2}
{"one","two"}

The Challenge

Given the two inputs, output all shared characters when spelled (both numbers spelled in either lower or upper-case, the same case for both numbers).

A sample implementation for spelling numbers can be found here: https://stackoverflow.com/a/3911982/318414; but I'm sure other options exist; and there are certainly efficiencies to be found given that there are large amounts of shared strings, once you get into the higher numbers. See also https://simple.wikipedia.org/wiki/Names_for_large_numbers for the names of large numbers.

, usual exclusions apply

Output The shared letters, in any reasonable format. Any of the three numbering systems on the Wikipedia page are valid.

Examples

I will be assuming British English (long form) in my examples.

{6,7} -> "s" or "S" (six, seven)

{999,1000} -> {"n","e"," ","t","h","u","a","d"} (nine hundred and ninety nine, one thousand)

{88955,88956} -> `` (eighty eight thousand nine hundred and fifty five, eighty eight thousand nine hundred and fifty six)

1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000,1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001 -> "ONE THUSADQICL" (ONE THOUSAND QUINDECILLION, ONE THOUSAND QUINDECILLION AND ONE)

9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999, 10000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 -> el no (nine hundred and ninety nine thousand sexdecillion **nine hundred and ninety nine thousand quindecillion nine hundred and ninety nine thousand quatturodecillion nine hundred and ninety nine thousand tredecillion nine hundred and ninety nine thousand duodecillion nine hundred and ninety nine thousand undecillion nine hundred and ninety nine thousand decillion nine hundred and ninety nine thousand nonillion nine hundred and ninety nine thousand octillion nine hundred and ninety nine thousand septillion nine hundred and ninety nine thousand sextillion nine hundred and ninety nine thousand quintillion nine hundred and ninety nine thousand quadrillion nine hundred and ninety nine thousand trillion nine hundred and ninety nine thousand billion nine hundred and ninety nine thousand million nine hundred and ninety nine thousand nine hundred and ninety nine; one googol)

||||||
\$\endgroup\$
  • \$\begingroup\$ "Any two positive integers (all natural numbers including 0)" You should reword this because 0 is not a positive integer. \$\endgroup\$ – 79037662 Feb 22 at 4:34
  • \$\begingroup\$ Possibly a chameleon challenge because answerers are required to convert an integer to its English form first, which could take much more effort than finding the shared letters. \$\endgroup\$ – Shieru Asakoto Feb 29 at 3:33
  • \$\begingroup\$ @ShieruAsakoto I'm envisaging that the intermediate step won't necessarily need to be performed in code - perhaps there's a way to just look at the numbers? If not, does a challenge exist for converting numbers to words yet? \$\endgroup\$ – simonalexander2005 Mar 2 at 8:17
0
\$\begingroup\$

Find spies in a multilingual csv

Introduction

You are an NSA undercover agent in a Middle-Eastern HR company, you just received a list of people with their jobs in many different languages. Some are spies and you need to know who. Your mission, if you accept it, is to get what are people working in, and relate it to a list of job categories. Most dangerous elements are those working in Law enforcement and security. However as your code will be part of a bigger file it needs to be as short in lines as possible for stealthness. This comes from expectations I encountered in the administration to keep some mystery behind code, if ever it were to be stolen.

  • This challenges your way to handle loops, map, reduce and filter, destructuring or unpacking an array/csv/df. Last but not least it allows you to get into the fascinating world of cross-language nlp.

I provide an example in python (64 lines of code)

Challenge

The challenge is to get, in the shortest amount of bytes (libraries not included) the most similar element in an array of string with another string, and this for each line of a csv taken as input.

  • Inputs:

    1. X.csv a csv/dataframe of actual jobs that look like this one:
,new_professionactuelle
0,Entrepreneur
1,طالبة
2,ETUDIANT
3,ETUDIANT 
4,موظف
5,موجه تربوي 
6,Réalisateur film cartoon
7,إإطار مالي
8,موضف إطار
9,مهندس بمكتب دراسات
10,باحثة  _ كاتبة _ 
11,طالب
12,Chef de projet
13,ASSUREUR
14,FONCTIONNAIRE D'ÉTAT
15,Professeur Universitaire
16,cadre supérieur
17,fonctionnaire
19,professeur
20,Chef de projet
21,مدير  شركة
22,Avocat
23,cadre à Maroc Telecom
24,Employé 
25,Consultant en Immobilier
26,fonctionnaire
27,اجير أو عامل
  1. df.csv job categories that must include all the following categories:

    ['Agriculture, farming and environment',
       'Accountancy, banking and finance',
       'Teacher training and education', 'Leisure, sport and tourism',
       'Transport and logistics', 'Information technology',
       'Hospitality and events management',
       'Business, consulting and management', 'Creative arts and design',
       'Trade', 'Law enforcement and security',
       'Property and construction', 'Law',
       'Engineering and manufacturing', 'Social care',
       'Charity and voluntary work', 'Sales',
       'Public services and administration', 'Other. Please specify:',
       'Healthcare', 'Energy and utilities',
       'Marketing, advertising and PR', 'Media and internet',
       'Recruitment and HR', 'Science and pharmaceuticals']
    
    • Output would be the column in X.csv plus a new column, the most similar job. The most accurate results are:
,new_professionactuelle,category
0,Entrepreneur,Public services and administration
1,طالبة,Teacher training and education
2,ETUDIANT,Teacher training and education
3,ETUDIANT ,Teacher training and education
4,موظف,Recruitment and HR
5,موجه تربوي ,Teacher training and education
6,Réalisateur film cartoon,Creative arts and design
7,إإطار مالي,"Accountancy, banking and finance"
8,موضف إطار,Trade
9,مهندس بمكتب دراسات,Engineering and manufacturing
10,باحثة  _ كاتبة _ ,Recruitment and HR
11,طالب,Teacher training and education
12,Chef de projet,Creative arts and design
13,ASSUREUR,Business, consulting and management
14,FONCTIONNAIRE D'ÉTAT,Public services and administration
15,Professeur Universitaire,Teacher training and education
16,cadre supérieur,Business, consulting and management
17,fonctionnaire,Public services and administration
18,CDB Retraite,Recruitment and HR
19,professeur,Teacher training and education
20,Chef de projet,Public services and administration
21,مدير  شركة,Recruitment and HR
22,Avocat,Law
23,cadre à Maroc Telecom,Media and internet
24,Employé ,Sales
25,Consultant en Immobilier,Property and construction
26,fonctionnaire,Public services and administration
27,اجير أو عامل,Recruitment and HR
  • Inputs should be tested against all categories.

The winner of the challenge will be the one with the most accurate results. If on the test set. If several are as accurate, the shortest amount of bytes will be the winner. You can use any methods to get the most similar item. The state of the art method seems to be according to Google Multilingual Universal Sentence encoder. I provide an attempt with the code below but you will see it is not quite acccurate.

Example in Python

Double agent: A spy who works for two countries, and sometimes even three, in which case he is definitely a trouble. - Mots et Grumots (2003), Marc Escayrol

#@title Setup common imports and functions
import numpy as np
import os
import pandas as pd
import tensorflow.compat.v2 as tf
import tensorflow_hub as hub
from tensorflow_text import SentencepieceTokenizer
import sklearn.metrics.pairwise

from simpleneighbors import SimpleNeighbors
from tqdm import tqdm
from tqdm import trange

import json

def most_similar(embeddings_1, embeddings_2, labels_1, labels_2):

  assert (len(embeddings_1) == len(labels_1) and len(embeddings_2) == len(labels_2))

  # arccos based text similarity (Yang et al. 2019; Cer et al. 2019)
  sim = 1 - np.arccos(sklearn.metrics.pairwise.cosine_similarity(embeddings_1, embeddings_2))/np.pi

  embeddings_1_col, embeddings_2_col, sim_col = [], [], []
  for i in range(len(embeddings_1)):
    for j in range(len(embeddings_2)):
      embeddings_1_col.append(labels_1[i])
      embeddings_2_col.append(labels_2[j])
      sim_col.append(sim[i][j])
  df = pd.DataFrame(zip(embeddings_1_col, embeddings_2_col, sim_col),
                    columns=['embeddings_1', 'embeddings_2', 'sim'])

  # return the higest similarity one
  category = df['embeddings_1'].iloc[df['sim'].argmax()]
  return category

def main():

    X = pd.read_csv('X.csv')
    y = pd.read_csv('y.csv')
    df_rni = pd.read_csv('df.csv')

    # The 16-language multilingual module is the default but feel free
    # to pick others from the list and compare the results.
    module_url = 'https://tfhub.dev/google/universal-sentence-encoder-multilingual/3' #@param ['https://tfhub.dev/google/universal-sentence-encoder-multilingual/3', 'https://tfhub.dev/google/universal-sentence-encoder-multilingual-large/3']

    model = hub.load(module_url)

    def embed_text(input):
        return model(input)

    def compute_similarity(references, target):
        # I want to create as many rows as there are references and fill them with the results
        # arccos based text similarity (Yang et al. 2019; Cer et al. 2019)
        for row in target.iterrows():
            for reference in references:
                sim = 1 - np.arccos(
                result = sklearn.metrics.pairwise.cosine_similarity(row,
                                                                    reference))/np.pi

            # place the result in the column "reference"

    # get unique job categories and job of people
    job_categories = X.S02Q11_Professional_field.unique()
    # turn them to list
    job_categories = job_categories.tolist()
    # emebedding job categories 
    references_result = embed_text(job_categories[1:])

    for _, row in df_rni.iterrows():
        actual_job = row['new_professionactuelle']
        # check for nan that can't be embedded
        if str(actual_job) != 'nan':
            # embedding actual job
            target_result = embed_text(actual_job)
            # visualize similarity
            category = most_similar(references_result, target_result, job_categories[1:], [actual_job])
        else: category = None

if __name__ == "__main__":
    main()
||||||
\$\endgroup\$
  • \$\begingroup\$ @Arnauld Indeed, fixed, thanks! \$\endgroup\$ – Revolucion for Monica Feb 24 at 15:19
  • \$\begingroup\$ It looks like your reference code fetches output from an external source, which is forbidden by default. Please detail within the question how one would implement the Google Universal Sentence Encoder. (If the challenge actually requires querying tfhub.dev/google/universal-sentence-encoder-multilingual/3, I don't think that's gonna be appropriate for CGCC). \$\endgroup\$ – Grimmy Feb 24 at 15:55
  • \$\begingroup\$ @Grimmy Google Universal Encoder: that's not compulsory, but I find it very handy and a good tip to start. External source: yes, that's the way I provided example data like the inputs above. Should I hard code the sources? \$\endgroup\$ – Revolucion for Monica Feb 24 at 16:05
  • \$\begingroup\$ Wait, Google Universal Encoder isn't compulsory? That seems to contradict the most similar element in an array of string with another string according to Google Multilingual Universal Sentence encoder. If GMUSE isn't required, this sentence should be replaced by a proper definition of "most similar element", and GMUSE should only be mentioned in the footnotes. \$\endgroup\$ – Grimmy Feb 24 at 16:10
  • \$\begingroup\$ External source: yes, that's the way I provided example data like the inputs above. I'm confused. Do you use tfhub.dev/google/universal-sentence-encoder-multilingual/3 only to get example data? It sure doesn't look like that in your code. \$\endgroup\$ – Grimmy Feb 24 at 16:11
  • \$\begingroup\$ @Grimmy Porbably I misunderstood "It looks like your reference code fetches output from an external source" then, my apologizes. \$\endgroup\$ – Revolucion for Monica Feb 24 at 16:19
  • \$\begingroup\$ This needs an explanation of how "accuracy" is computed. (And you still need to define "most similar"). \$\endgroup\$ – Grimmy Feb 24 at 18:45
0
\$\begingroup\$

Auto Tic Tac Toe

Okay, so after thinking about the comment I think I thought of a way to make it more interesting.


Challenge

Given no input, write a program or function which outputs an entire game of Tic-Tac-Toe where X always wins, or the game ends in a tie.

Requirements

  • X goes first
  • O must make moves at random
  • X must make smart moves such that it always wins the game, or the game ends in a tie

Example

Here's what I would expect a game to look like:

X--
---
---

XO-
---
---

XO-
-X-
---

XOO
-X-
---

XOO
-X-
--X

Notes:

  • X does not need to win in the fewest moves, it is enough to just make it always block O from winning
  • You can output the game in whatever form you like, as long as it is easily conveys every turn of the game. For example you could output a string like above, or a list of lists of ints like below, where 0 is an empty space and 1, 2 are X, O respectively:
[
  [1,0,0, 0,0,0, 0,0,0], 
  [1,2,0, 0,0,0, 0,0,0], 
  [1,2,0, 0,1,0, 0,0,0],
  [1,2,2, 0,1,0, 0,0,0], 
  [1,2,2, 0,1,0, 0,0,1]
]

This is code golf, answer in the fewest bytes wins. Standard rules apply.


Is this a better challenge? I'd love to know what people think


Working example of ungolfed code: Try it online!

||||||
\$\endgroup\$
  • 1
    \$\begingroup\$ I suspect this hasn't been asked because the huge majority of the work is spent on IO and not on an interesting problem. If you want to ask a tic-tac-toe challenge, you might be better served asking something like "can the next move win" which might still be a lot of parsing, but prevents excessive output at least. That said, you did do a good job of alleviating these problems in your notes, so you may be fine - most of what I've written here is my opinion, not precise advice. \$\endgroup\$ – FryAmTheEggman Jan 26 at 19:31
  • \$\begingroup\$ @FryAmTheEggman Made a pretty big edit, do you think this would be less boring? \$\endgroup\$ – Quinn Feb 1 at 1:15
  • \$\begingroup\$ I think the problem I have with this version is that it is probably more work to make a tic-tac-toe AI than it is to encode all the possible games and just pick one at random to output. It is possible that that isn't true, I haven't tried yet, but it still feels a bit tedious. But this might be the right direction - perhaps instead just ask for one random valid final tic-tac-toe board? Then it will likely be an encoding problem, but perhaps one with interesting strategies. Again, all opinion here, the challenge is written well, etc. \$\endgroup\$ – FryAmTheEggman Feb 1 at 5:13
  • \$\begingroup\$ Do you mean "uniformly distributed" when you write "random"? \$\endgroup\$ – Jonathan Frech Feb 4 at 9:54
  • \$\begingroup\$ Is the challenge in its current form not a kolmogorov-complexity challenge with choice? \$\endgroup\$ – Jonathan Frech Feb 25 at 1:25
  • \$\begingroup\$ @FryAmTheEggman I don't think making the AI is actually that hard for tic-tac-toe, though if im underestimating it, i could make a change that X always go first, which I think would make the ai pretty trivial \$\endgroup\$ – Quinn Feb 25 at 14:14
  • \$\begingroup\$ @JonathanFrech You tell me i have no clue, is that meaning the amount of code to output all possible tictactoe outcomes? \$\endgroup\$ – Quinn Feb 25 at 14:15
  • \$\begingroup\$ I am just saying that if you take no input and require a (semi-)static output, a part of the challenge is to find out which tic-tac-toe game requires the least bytes to represent and the rest is a kolmogorov-complexity task, which in my opinion is s slightly over-used challenge format. \$\endgroup\$ – Jonathan Frech Feb 25 at 15:59
  • \$\begingroup\$ kolmogorov-complexity challenges are code golf challenges with no input and a static output. \$\endgroup\$ – Jonathan Frech Feb 25 at 15:59
  • \$\begingroup\$ @JonathanFrech Is that a bad thing then? Do you think this challenge wouldn't be fun? \$\endgroup\$ – Quinn Feb 25 at 20:18
  • \$\begingroup\$ @FryAmTheEggman okay fixed my example, hopefully that illustrates how simple the ai could be \$\endgroup\$ – Quinn Feb 25 at 20:32
  • 1
    \$\begingroup\$ I feel as though your example does more to demonstrate that nobody would approach this by writing an AI - they would just encode each possible game as Jonathan is suggesting. That doesn't mean it isn't a good challenge, the problem I am trying to get at is that the phrasing of the challenge implies that writing a "player" is required - which I think is a bad requirement. If the challenge was just "output a random, valid, tic-tac-toe board" you could still maybe get an AI solution, if it happened to be shorter, but wouldn't come with a lot of needless baggage. Sorry if this sounds a bit rambly. \$\endgroup\$ – FryAmTheEggman Feb 25 at 20:39
  • \$\begingroup\$ @FryAmTheEggman well my example has tons of unnecessary baggage and is not doing anything in an efficient way in terms of golfing, i just wanted the general algorithm to be shown, id imagine it could easily be shortened to a couple hundred bytes in most languages. That said if they can find a way to output winning board states so long as they show each turn that was played than that would be valid, I don't intend to require anyone to write an AI, just achieve the desired output. Not sure how to rephrase the question to make sure its clear that that is a valid answer. \$\endgroup\$ – Quinn Feb 25 at 21:15
  • \$\begingroup\$ @Quinn However, finding such a game would not be done in the submission but to be able to write the submission, leaving the actual challenge itself to be a bit of a boilerplate. \$\endgroup\$ – Jonathan Frech Feb 25 at 21:19
0
\$\begingroup\$

Shift the letters, soldier !

Context

We're at war! You need to transfer an important message to your general to inform him from an imminent assault. The thing is, your enemy knows a lot about cryptography : you will need to be more creative in order to encode your message...

Task

Create a program that accepts an ascii message as input, and outputs the encoded message. The message should be encoded this way : each character should get its ascii value shifted by its position in the message.

For example, let's encode the message "Hello, world!"

H   e   l   l   o   ,       w   o   r   l   d   !     Original message
72  101 108 108 111 44  32  119 111 114 108 100 33    ASCII value
0   1   2   3   4   5   6   7   8   9   10  11  12    Place in the message
72  102 110 111 115 49  38  126 119 123 118 111 45    Encoded ascii (line 1 + line 2)
H   f   n   o   s   1   &   ~   w   {   v   o   -     Encoded message

The message Hello, world! should be encoded as Hfnos1&~w{vo-.

Rules

  • The message should be encoded as described before.
  • The ascii values should be set between 32 and 126.
  • If the new ascii value goes beyond the limit, it should loop back to 32.
  • Every character should be encoded. This includes punctuation, spaces etc.
  • No standard loopholes allowed.
  • This is codegolf, so the shortest code wins.
  • If you are able to decode a message, multiply your score by 0.7 Won't be part of the challenge anymore.

Meta

  • Is the challenge clear enouth ?
  • Should i only allow printable ascii values, or can i allow values between 1 and 256 ?
||||||
\$\endgroup\$
  • \$\begingroup\$ Thank you for sandboxing this. I usually recommend doing so for at least a week, and periodically ask for review in TNB. \$\endgroup\$ – Adám Feb 28 at 9:09
  • \$\begingroup\$ I think people would be forced to do the bonus in this case because of the -30% margin. I got a 42 without bonus but a 57*0.7=39.9 with bonus in JS. \$\endgroup\$ – Shieru Asakoto Feb 29 at 3:16
  • \$\begingroup\$ Bonuses are discouraged for a variety of reasons. I would strongly recommend either making it mandatory or completely leaving it out. \$\endgroup\$ – FryAmTheEggman Mar 1 at 18:58
  • \$\begingroup\$ The main challenge is add by position, the bonus challenge is minus by position. So it's a good idea to completely leave the bonus out. \$\endgroup\$ – petStorm Mar 2 at 0:29
  • \$\begingroup\$ Thanks for the comments, I'll remove the bonus as it will never be balanced enouth to be interesting. I'll add some example as soon as I can. \$\endgroup\$ – The random guy Mar 3 at 20:02
  • \$\begingroup\$ I would say that allowing the usage of the ascii range 1 to 255 or a language's code page could allow for some interesting golfs :) \$\endgroup\$ – RGS Mar 3 at 20:39
  • \$\begingroup\$ Use asciii values from 0 to 255 was my original plan, but I'm afraid some interestings languages would be disadvantaged. Also, wouldn't the usage of language's code page be too permissive ? \$\endgroup\$ – The random guy Mar 4 at 15:51
  • \$\begingroup\$ @Therandomguy it depends on what you mean by "too permissive". Sometimes it is done, as it may allow some languages to do some funny things. As to the range being from 0 to 255, I don't see it hurting any language at all, but of course I may be missing something :) \$\endgroup\$ – RGS Mar 4 at 21:36
  • \$\begingroup\$ Are you interested in re-posting it? \$\endgroup\$ – petStorm Mar 6 at 7:38
  • \$\begingroup\$ This weekend I'll post it, I just need some time creating the examples \$\endgroup\$ – The random guy Mar 6 at 8:25
  • \$\begingroup\$ I'd be glad to see it posted in Main! \$\endgroup\$ – petStorm Mar 25 at 12:19
0
\$\begingroup\$

Compute the Pareto frontier

Given a set of triplets, output its Pareto frontier.

Definitions

A triplet is a list of 3 positive integers, for example [120, 15, 21] (order matters).

A triplet [A, B, C] is objectively worse than [a, b, c] when A >= a, B >= b, and C >= c (lower is better).

A triplet is on the Pareto frontier when it's not objectively worse than any other triplet in the input.

I/O rules

Input and output are both a set of triplets. Each triplet must be represented as either a list of integers ([1, 2, 3]) or a /-delimited string ("1/2/3"). The format of the outer sets is flexible (built-in set type, list, or delimited string are all okay).

Test cases

[[1, 1, 1], [2, 2, 2]] => [[1, 1, 1]]
[[3, 3, 1], [3, 1, 3], [1, 3, 3], [2, 2, 2]] => [[3, 3, 1], [3, 1, 3], [1, 3, 3], [2, 2, 2]]
... (more to come) ...
||||||
\$\endgroup\$
  • \$\begingroup\$ I had sandboxed a similar challenge, but it didn't seem to be going anywhere and I wasn't going to post it. Maybe the discussion on it about filtering is somewhat relevant to this. \$\endgroup\$ – xnor Mar 8 at 18:42
  • \$\begingroup\$ The IO rule for the triplets seems odd, why not any kind of ordered list? \$\endgroup\$ – FryAmTheEggman Mar 8 at 19:35
0
\$\begingroup\$

A similar challenge was posted here but that's outdated and I have a few twists.

Challenge

Write a program, expression or subroutine which, given an arithmetical expression in infix notation, like 1 + 2, outputs the same expression in postfix notation except the numbers are now float representative in the string, i.e. 1.0 2.0 +.

The input can include parentheses (()), exponents (^), division (/) and multiplication (*), addition (+) and subtraction (-) (in that order of operation), such as

4 ^ (2 / 3) * 9 * 3 - - 4 * 6

output the same expression in prefix notation.

4.0 2.0 3.0 / ^ 9.0 * 3.0 * -4.0 6.0 * -

Spaces are optional in the input as well as the output.

Twists

  • Must support using floats too, instead of just integers. so 4 ^ (2.0/3.0) * 9.0 * 3.0 - - 4 *6 output's is the same as the ones above.
  • Must return a string with all numbers as its float representative instead of as its original form, so 9 -> 9.0 and if it was 9.0 it stays 9.0.
  • Must support negation (see example above "3.0 - - 4" ends up with "-4.0", negative sign stays in place).
  • Cannot use exec() or eval() functions.

Assumptions

  • You can assume that there will not be any special numbers such as those in scientific notation or those with hanging zeroes, e.g. 000004 or 0005.000000.
  • You should also not assume the commutative or associative properties. This means that, while the operators will move around, the numbers will always remain in the same order.
  • You can always assume a valid infix input.

Clarifications

  • You should not evaluate any expression.
  • The output should not contain any unneeded parentheses. ((2+1))-1 should reduce to 2+1-1.

Game Winning Criteria

Fewest amount of characters wins. Bytes are not of a matter here.

||||||
\$\endgroup\$
  • 2
    \$\begingroup\$ To reiterate my comment on the original question: 1. Using the word "twist" is not recommended. 2. Don't ban exec/eval just because you don't like it. The task isn't about evaluating the value, so it is unnecessary and pretty much arbitrary. 3. You say "prefix notation", but 4.0 2.0 3.0 / ^ 9.0 * 3.0 * -4.0 6.0 * - is in postfix, not prefix. You should fix either the description or the example result. \$\endgroup\$ – Bubbler Mar 12 at 1:27
  • 1
    \$\begingroup\$ And you didn't explain why you want to handle unary negation in a different way (which is essentially changing the underlying expression, which seems against "You should not evaluate any expression"). By using a different symbol for unary minus (say ~), it is possible to translate the example to postfix as 4.0 2.0 3.0 / ^ 9.0 * 3.0 * 4.0 ~ 6.0 * -. \$\endgroup\$ – Bubbler Mar 12 at 1:34
  • 2
    \$\begingroup\$ For code-golf scoring, scoring by bytes is preferred over characters. (I believe there must be a more persuasive argument somewhere...) \$\endgroup\$ – Bubbler Mar 12 at 1:47
  • 1
    \$\begingroup\$ The second line in "clarifications" is unnecessary because "postfix notation" implies no parentheses. For the floating-point output, do you have a reason to demand adding .0 to integer values? A floating-point number 4 can be printed as 4, 4., or 4.0, and all of them represent the same value anyway. \$\endgroup\$ – Bubbler Mar 12 at 2:13
  • \$\begingroup\$ The linked challenge explicitly assumes left-associativity for all operators ^ * / + - (that is, 1 - 2 + 3 = (1 - 2) + 3, 4 / 5 * 6 = (4 / 5) * 6, and 7 ^ 8 ^ 9 = (7 ^ 8) ^ 9), but ^ is mathematically right-associative (7 ^ 8 ^ 9 = 7 ^ (8 ^ 9) != (7 ^ 8) ^ 9). Which one should we use? \$\endgroup\$ – Bubbler Mar 12 at 2:17
  • \$\begingroup\$ Can negation be stacked? i.e. is 1 - - - 1 a valid input? Doesn't negation in the output kinda negate (heh) the point of it being postfix, because it it prefix? \$\endgroup\$ – Jo King Mar 12 at 2:33
0
\$\begingroup\$

Lucky Numbers in a Matrix

Given a m * n matrix of distinct numbers, return all lucky numbers in the matrix in any order.

A lucky number is an element of the matrix such that it is the minimum element in its row and maximum in its column.

Test cases

Case 1:

Input: matrix = [[3,7,8],[9,11,13],[15,16,17]]
Output: [15]
Explanation: 15 is the only lucky number since it is the minimum in its row 
and the maximum in its column

Case 2:

Input: matrix = [[1,10,4,2],[9,3,8,7],[15,16,17,12]]
Output: [12]
Explanation: 12 is the only lucky number since it is the minimum in its row 
and the maximum in its column.
||||||
\$\endgroup\$
  • \$\begingroup\$ What will be the smallest size of the matrix? Also, I suggest formatting the matrices 2-dimensionally in the test cases so that it is easier to see the corresponding output tio.run/##SyzI0U2pTMzJT/8PBI/… \$\endgroup\$ – user41805 Mar 15 at 8:11
0
\$\begingroup\$

Balance a Binary Search Tree

Given a binary search tree, return a balanced binary search tree with the same node values.

A binary search tree is balanced if and only if the depth of the two subtrees of every node never differ by more than 1.

If there is more than one answer, return any of them.

Test Case:

enter image description here

enter image description here

Input: root = [1,null,2,null,3,null,4,null,null]
Output: [2,1,3,null,null,null,4]
Explanation: This is not the only correct answer, [3,1,4,null,2,null,null] is also correct.
||||||
\$\endgroup\$
  • 1
    \$\begingroup\$ Perhaps, you can include an explanation of this input format in the challenge body. What counts as valid input formats for the binary tree? \$\endgroup\$ – user41805 Mar 15 at 8:18
0
\$\begingroup\$

Determine the maximum value in the final array.

Description

Start with an array initialized to zeros with indices starting at 1 and a series of operations to perform on segments of the list. Each operation will consist of a starting and ending index within the array, and a number to add to each element within that range.

Determine the maximum value in the final array.

For example, start with an array of 5 elements: list = [0, 0, 0, 0, 0]. The variables a and b represent the starting and ending indices, inclusive. Another variable, k, is the addend. The first element is at index 1.


    a    b    k             list

                   [  0,  0,  0,  0,  0]

    1    2   10    [ 10, 10,  0,  0,  0]

    2    4    5    [ 10, 15,  5,  5,  0]

    3    5   12    [ 10, 15, 17, 17, 12]

The maximum value in the resultant array is 17. That is the value to be determined.

Function description

The function must return a long integer that denotes the largest value in the array after all operations have been performed.

listMax has the following parameters:

n: an integer, the size of the initial array.
operations: a 2D integer array where each element contains an operation.

Test Cases

Sample Input

5

3

3

1 2 100

2 5 100

3 4 100

Sample Output

200
Return the maximum value in the final list, 200, as the answer.

Explanation

Perform the following sequence of o = 3 operations on list = [0, 0, 0, 0, 0]:

  1. Add k = 100 to every element in the inclusive range [1, 2], resulting in list = [100, 100, 0, 0, 0].

  2. Add k = 100 to every element in the inclusive range [2, 5], resulting in list = [100, 200, 100, 100, 100].

  3. Add k = 100 to every element in the inclusive range [3, 4], resulting in list = [100, 200, 200, 200, 100].

This is code-golf so shortest submission in bytes wins! If you liked this challenge, consider upvoting it... And happy golfing!

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

Golf yourself a real calculator [draft]

We will only cover the characters(0123456789+-*/=%ñ) in our tutorial.

The = operations

Unlike most desktop calculators, our household calculator is a tacit language. Therefore it is able to do a lot more than other infix calculators.

Take a simple calculation as an example. The non-scientific calculator does not have the exponentiation operator. What do you do to calculate 2^5?

2*2====

However, there's a shortcut for doing that. Since 2 is already in the expression buffer, you can simply do

2*====

The calculator automatically fills in the current expression during the inputting.

Here is a demonstration of how this works:

(A template for easy copy&paste.

Pressed Key      : 
Expression buffer: 
Output buffer    : 
)

Pressed Key      : 2
Expression buffer: 2
Output buffer    : 2

Pressed Key      : *
Expression buffer: 2 *
Output buffer    : 2

Pressed Key      : =
Expression buffer: * 2
Output buffer    : 4

Pressed Key      : =
Expression buffer: * 2
Output buffer    : 8

Pressed Key      : =
Expression buffer: * 2
Output buffer    : 16

Pressed Key      : =
Expression buffer: * 2
Output buffer    : 32

Implicit 0 before calculation

Suppose you enterede the following expression:

*1

Now, don't get me wrong, the household calculator of course doesn't have pointers. So, why doesn't it raise a syntax error though? (The output is 0 by the way.) Here's why.

The calculator initially has the expression starting at 0, therefore it prepends a 0 to the expression. Therefore the full form of our expression is:

0*1

What we've learned so far

  • The output buffer is a part of the calculator storing the latest-evaluated integer. All entered numbers get appended to the output buffer as well as the expression buffer.
  • The expression buffer is a part of the calculator storing the latest instruction. After a = operator, it stores the latest applied expression for later application.
  • The = operator tries to evaluate the instruction buffer. If that's a syntax error, it tries to evaluate that concatenated the output buffer. If that still fails, it tries to evaluate the output buffer concatenated with the instruction buffer. After that operation, the expression starting from the newest-entered dyadic operator is saved in the expression buffer.
||||||
\$\endgroup\$
0
\$\begingroup\$

Represent n as a expression containing all the digits

Related Challenge: Single Digit Representations of Natural Numbers

Task

Write a program/function that when given a non-negative integer \$n\$ that is less than or equal to \$1000\$ outputs a expression which uses all the digits from \$0\$ to \$9\$ exactly once and evaluates to \$n\$

The expression outputted by your program may only use the operations listed below:

  • addition
  • subtraction and unary minus (both must have the same symbol)
  • multiplication
  • division
  • exponentiation
  • concatenation (must be explicit)
  • parentheses

The precedence of the operators is up to you but must be consistent for all outputs produced by you program. You may also use custom symbols for representing the digits and operators but the symbols must be distinct and must be consistent for all outputs produced by you program

Scoring

This is so shortest bytes wins

Testcases

0 -> 0 * (1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9)
42 -> 4 || (2 + 0 * (1 + 3 + 5 + 6 + 7 + 8 + 9))
100 -> 123 + 4 − 5 + 6 || 7 − 8 || 9 + 0
100 -> 9 || 8 − 7 || 6 + 5 || 4 + 3 + 2 || 1 + 0
100 -> 1 || 0 || ((9 - 7 - 2) * (3 + 4 + 5 + 6 + 8))
1000 -> 1 || (9 - 7 - 2) || ((8 - 5 - 3) * (4 + 6)) || 0

Note: In the testcases || represents concatenation


A proof by exhaustion that shows that all number less than a \$1000\$ have a expression that uses all the digits.


For Sandbox

  • Any tags I should add
  • I really don't want concatenation as an operation so if someone could find a proof or show by exhaustion that all numbers below \$1000\$ have expression that uses all the digits and doesn't use concatenation I would be grateful
||||||
\$\endgroup\$
0
\$\begingroup\$

Dilapidated art gallery problem

In a typical art gallery problem, the objective is to place as few guards as necessary inside an arbitrary polygon so that all of it is visible by some guard. This time, we'll make some changes to simplify the task:

  • The gallery can only afford to pay one guard. No more. This means that it won't be possible to keep everything in sight, so the objective becomes to maximize the amount of art visible.
  • Not even a dilapidated art gallery is barbaric enough to put art on the floor, and they don't have enough money to afford pedestals, so we only care about how much wall area is visible.
  • Since the art gallery doesn't even have a roof, the whole floor is visible anyways. If you are wondering how the guard manages to hover high above the gallery - he doesn't. He has a telescopic camera tied to a weather balloon. There. Problem solved. Therefore, what counts for visibility isn't occlusion. The only thing that matters is that the walls are facing the right way.
  • You can assume the floor plan is a (not necessarily connected) union of rectangles. I was thinking about including diagonal walls, but this version fits better with the theme. Any internal walls have a definite thickness. If they didn't, you could just ignore them, and that's no good.
  • The guard doesn't have to be inside the gallery. They can sit outside, or even lean against the walls. You, however, cannot place the guard with infinite precision. If you try to align the guard with one of the walls, they will be displaced infinitesimally in one direction chosen with uniform probability. But yes, you can try.

The input will consists of the following characters:

  • The space character represents 1m x 1m of empty space. It's up to you to decide if it's inside the gallery, or outside. You may assume that the input encodes a rectangular area that includes all of the gallery floor and that all of the walls are depicted.
  • - and | represent 1m x 1m squares with walls (east-west and north-south respectively) passing through their centers. Each wall will be adjoined by either the same type of wall or a corner in its lengthwise direction, and empty space in its transverse direction.
  • + Represents a corner. Each corner will be adjoined by an east-west wall either on its east side or on its west side, but not both, and by a north-south wall either on its north side or its south side, but not both, and by empty space on the remaining two sides, and in all four diagonally neighboring tiles.

Your objective is to determine and mark all guard locations - tile centers - that maximize the number of wall segments viewed from the correct side - empty space should be marked with . and wall tiles should be marked with #.
In the event that none of the optimal spots align with tile centers, do not mark any tile as optimal. It is the user's responsibility to provide a more detailed floor plan. You may optionally display an error message in that case. If you choose so, the error message must be: displayed in every situation in which no optimal tile would have been marked; same for every input that causes it to be shown; includes at one character not allowed in any valid output.

Example cases:

+----+    +----+
|    |    |....|
|    | => |....|
|    |    |....|
+----+    +----+

The guard can be anywhere inside the gallery, but they can't lean against the wall because they might suddenly find themself on the other side of that wall unexpectedly.

+---+        +---+    
|   |        |   |  . 
+---+ +-+    +---+ +-+
      | | =>       | |
      | |          | |
      | |          | |
      +-+          +-+

In this case, the gallery consists of two separate buildings, and the guard's best spot lies outside either of them.

+---+
|   |
|   +-+ => error
+-+   |
  |   |
  +---+

In this case, there is a 1m x 2m area in which the guard can see all of the walls, but there's no way to depict that in the output. You may pass the input unmodified, or you may output an error message.

+-----+    +-----+
|     |    |.   .|
| +-+ |    | +-+ |
| | | | => | | | |
| +-+ |    | +-+ |
|     |    |.   .|
+-----+    +-----+

This art gallery has a courtyard. Two inner walls must be left unprotected, but it doesn't matter which ones.

  +-+          +-+    
  | |         .#.#... 
  +-+ +-+     .###.##+
      | |     .....#.|
+-+   +-+ => +##...##+
| |          |.#..... 
+-+ +-+      +##.###. 
    | |       ...#.#. 
    +-+          +-+  

For every wall but four, there is another wall such that exactly one of the two can be seen at any given time. As long as the other four walls are guarded, the number of walls guarded is maximized. This is also one of the rare cases where the guard can lean against a wall - if they fall through, they'll wind up guarding another wall instead.

+-------------+

This is not an art gallery. It's a fence with no inside or outside. Invalid input.

+---+-+---+   +
|   | |   |   |
|   | |   |   +
+---+-+---+

You might think this depicts two rooms with an internal wall, or three rooms with two internal walls - either way, internal walls are banned. Also, fences are banned. Invalid input.

+---+ +--+ +-+
|   | |  ++| |
|   +-+   |+-+
+---------+

This building has a clear interior and exterior, but the southern corridor is too narrow, the dent in the north-east corner is too jagged to leave enough room for art, and the nearby closet is too close to the main building. Each of these reasons suffices to make this an invalid input.

|---------+
| +-+     |
|    *a k |
| ei 32A  |
+-+++-+--++

There's a gap in the northwest corner, debris all over the floor, and the southern wall has exposed scaffolding. All wrong.

||||||
\$\endgroup\$
  • \$\begingroup\$ I'm not sure if I'm misreading, but I feel as though there is a lot of excess information provided, while certain more basic concepts are left unexplained. For example, the rule about guard displacement being uniformly random and the size of the tiles being 1m2 seem unnecessary for computing the output, whereas the rule for what the guard sees was difficult for me to interpret. My understanding is that the guard sees infinitely far in every direction, but not through walls? \$\endgroup\$ – FryAmTheEggman Mar 20 at 16:00
  • \$\begingroup\$ @FryAmTheEggman from the third point: "Therefore, what counts for visibility isn't occlusion. The only thing that matters is that the walls are facing the right way". Are you suggesting I should reformulate that? \$\endgroup\$ – John Dvorak Mar 20 at 16:09
  • \$\begingroup\$ Yes, that part wasn't totally clear to me, and it feels like a very important detail that is somewhat buried amongst much less relevant information. \$\endgroup\$ – FryAmTheEggman Mar 20 at 16:24
0
\$\begingroup\$

For How Long am I Alone?

Task

You are a factory worker, whose shift is from time X to time Y. It's a very boring job, and you want to know if any other workers are working during your shift. Given a list of start and end times for the other workers and your own shift time, output the longest amount of time that you are the only one working in the factory.

Input

List of start and end times. Any reasonable format is allowed, such as a list of tuples representing (startHour, startMinutes, endHour, endMinutes) or a list of date objects.

A pair of times, which represent your own start and end times. These may be received as a tuple/list or as separate arguments. Again, the times can be passed as a tuple, date objects, or two object array representing (hour, minutes), or you can pass the hours and minutes as separate arguments.

Each person starts working precisely at their start time and gets off work right when the end time starts. For example, if someone is working from 8:00 to 17:00, at 17:00 they are not considered to be at work anymore.

Each person does his shift 7 days a week.

If you choose to use date objects, the "Year" field of the date objects must always be the same across all inputs.

Note that the end time of your shift can look like it's earlier than your start time, e.g. 21:30 - 5:30. This means that your shift starts at 21:30 at the first day and ends at 5:30 on the next day.

Output

The longest interval in minutes in which you are the only one working in the factory.

Test Cases

In the form of [(hh:mm,hh:mm)...], hh:mm, hh:mm

[(3:30, 12:00), (13:00, 21:40)], (8:30), (16:30) -> 60
[(1:01, 1:03), (1:04, 1:06), (1:07, 1:10)], (1:00), (1:10) -> 1
[(21:00, 5:00), (22:30, 7:00)], (0:00), (4:00) -> 0

Questions

Should I keep the part about the shift being able to stretch across midnight?

Is the input specification clear enough?

Any suggestions welcome.

||||||
\$\endgroup\$
  • \$\begingroup\$ Say my shift is overnight and someone has a shift that isn't overnight. How do I know what day said shift belongs to? e.g. if I'm working from 21:30 to 5:30 and I get another input as 1:00 to 4:00 how do I know if I haven't even started? \$\endgroup\$ – RGS Mar 20 at 13:26
  • \$\begingroup\$ @RGS Good question. Added a part about the shifts being 7 days a week, so there is no confusion. I feel like the part about having a overnight shift might make this challenge unnecessarily complicated; What do you think? \$\endgroup\$ – Embodiment of Ignorance Mar 20 at 18:13
  • \$\begingroup\$ I am not a sandbox veteran, but from my POV this challenge will have us handling intervals and do arithmetics with the interval endpoints and that is probably the main core of the challenge. But adding the overnight shifts means we are trying to intersect segments of a circumference, instead of regular intervals, which is also interesting, I think! (do you understand what I mean with this?) So maybe either remove overnight shifts or rephrase the challenge as intersecting segments of a circumference? So that it becomes more clear that it isn't just an edge case, but the core challenge itself \$\endgroup\$ – RGS Mar 20 at 19:00
  • \$\begingroup\$ As for the title, I would have "For how long am I alone" because "How long am I alone" looks like you are asking for your length when you are alone, instead of the amount of time during which you will be alone. \$\endgroup\$ – RGS Mar 20 at 19:01
  • \$\begingroup\$ Instead of "must always be the same across all inputs", I suggest "will always be the same across all inputs". This makes it more clear that you don't have to deal with the year. \$\endgroup\$ – S.S. Anne Mar 20 at 23:56
0
\$\begingroup\$

Numbers by index

Challenge

Print the numbers:

0
1
22
333
4444
55555
666666
7777777
88888888
999999999

In that order.

I/O

Takes no input. The numbers can have any delimiters desired (or none). Example outputs:

0122333444455555666666777777788888888999999999

[0,1,22,333,4444,55555,666666,7777777,88888888,999999999]

etc....

Code Example

This is an un-golfed example that may perhaps act as algorithm guide (or maybe not):

Turing Machine Code, 553 bytes

0 * 0 r K
K * _ r 1
1 * 1 r L
L * _ r 2
2 * 2 r a
a * 2 r M
M * _ r 3
3 * 3 r b
b * 3 r c
c * 3 r N
N * _ r 4
4 * 4 r d
d * 4 r e
e * 4 r f
f * 4 r O
O * _ r 5
5 * 5 r g
g * 5 r h
h * 5 r i 
i * 5 r j
j * 5 r P
P * _ r 6
6 * 6 r k
k * 6 r l
l * 6 r m
m * 6 r n
n * 6 r o
o * 6 r Q
Q * _ r 7
7 * 7 r p
p * 7 r q
q * 7 r r
r * 7 r s
s * 7 r t
t * 7 r u
u * 7 r R
R * _ r 8
8 * 8 r v
v * 8 r w
w * 8 r x
x * 8 r y
y * 8 r z
z * 8 r A
A * 8 r B
B * 8 r S
S * _ r 9
9 * 9 r C
C * 9 r D
D * 9 r E
E * 9 r F
F * 9 r G
G * 9 r H
H * 9 r I
I * 9 r J
J * 9 r halt

Try it online!

This prints out the numbers with a space delimiter:

0 1 22 333 4444 55555 666666 7777777 88888888 999999999

Challenge Type

, so shortest answer in bytes (by language) wins.

Edit: Link to the related challenge. Curiously, there is one answer on there where if it was by index, and the zero was included, it would be shorter.

||||||
\$\endgroup\$
  • \$\begingroup\$ Nice challenge! Are preceding & trailing whitespace (during string output) permitted? \$\endgroup\$ – petStorm Mar 11 at 3:22
  • \$\begingroup\$ I think it should also be kolgomorov-complexity. \$\endgroup\$ – PkmnQ Mar 11 at 5:19
  • 6
    \$\begingroup\$ I don't like how the zero breaks the pattern of having the digit N appear N times -- it seems like an exceptional edge case. I think it would be better for 0 not to appear, so the numbers would just start from 1. \$\endgroup\$ – xnor Mar 11 at 7:06
  • 1
    \$\begingroup\$ @xnor, I knew you wouldn't like it (and probably a few other won't as well) That's on purpose. It just seems a little too easy otherwise. \$\endgroup\$ – ouflak Mar 11 at 7:28
  • \$\begingroup\$ @a'_', Yes. @ PkmnQ, Noted. \$\endgroup\$ – ouflak Mar 11 at 7:29
  • \$\begingroup\$ I don't really see how adding a fixed zero to the beginning makes the challenge harder in almost any language. In some, the empty string will actually convert to zero, which makes it more natural but still fairly trivial. I feel like you probably either want to go with omitting the zero, or finding a different way to make the challenge more complicated. \$\endgroup\$ – FryAmTheEggman Mar 11 at 14:53
  • \$\begingroup\$ @FryAmTheEggman, How can you have a challenge about indexes and not have zero? That just seems wrong. \$\endgroup\$ – ouflak Mar 11 at 15:31
  • \$\begingroup\$ Most people start counting from one - only people who use computers a lot default to starting at zero. And separately, I think finding another way to incorporate it is better than leaving it out (I just also think both are better than having an unexplained outlier). \$\endgroup\$ – FryAmTheEggman Mar 11 at 15:40
  • \$\begingroup\$ @FryAmTheEggman, But it's not really unexplained is it? It's the index of the first number. \$\endgroup\$ – ouflak Mar 11 at 15:46
  • 1
    \$\begingroup\$ As per what xnor said, it doesn't match the pattern of the others. That behaviour is not explained. Comments aren't really for a discussion like this; if you disagree that is fine. I've just given feedback on how I think you could improve the challenge. \$\endgroup\$ – FryAmTheEggman Mar 11 at 16:15
  • \$\begingroup\$ I do want to make sure that everyone knows that I am VERY grateful for the feedback! I also appreciate having a Sandbox where we can have this discussion here instead of on the main site. \$\endgroup\$ – ouflak Mar 11 at 16:18
  • \$\begingroup\$ @FryAmTheEggman, It's not that I disagree. I kind of agree. I like that leading zero in there to represent the index location of the initial value. I considered this when I thought of the question, before posting it here. It breaks up a trivial loop sequence answer a bit, or maybe even inspires a clever solution that nobody considered. I'd like to keep it because it stands out like that, not despite that. \$\endgroup\$ – ouflak Mar 11 at 16:21
  • \$\begingroup\$ I posted an example implementation above. The zero wasn't a big deal. \$\endgroup\$ – ouflak Mar 11 at 16:31
  • 1
    \$\begingroup\$ My guess is that you're excited about the arithmetic expression 10**n/9*n or similar. But I don't think that's much more interesting than the obvious loops that removing the zero would allow unmodified. \$\endgroup\$ – xnor Mar 11 at 21:59
  • 1
    \$\begingroup\$ @ouflak I contrast, I am very excited about arithmetic expressions :) \$\endgroup\$ – xnor Mar 12 at 21:16
0
\$\begingroup\$

In need of title.

Note: In the final challenge \$N\$ will be a concrete number (I am thinking about 100), but while this is in the sandbox it is subject to change so I have left it as \$N\$.


This challenge is based off of a list of \$N\$ Castilian (also called Spanish) words and the words they originate from.

You are to write a program or function which takes the origin word as input and outputs as close as possible the Castilian derivative. Your program should be no longer than \$N\$ bytes.

Scoring

To calculate your score run your program on every origin word and calculate the distance between your output and the correct answer. Your score is the sum of all these distances.

The distance here is a modified version of Levenshtein distance. It is the same as Levenshtein distance except replacement steps that add or remove a diacritic cost only 1/2 of a step as opposed to their normal 1.

You can use this code to calculate the distance between two strings.

The goal is to have as low a score as possible.


About the list

All of the origin words spare 1 are Latin words (Late or Classical depending on the word). The one exception is ezkerra (the origin for izquierda) which is of Basque origin. It has been added as an extra curve-ball in case you can get all the others with a little space to spare.

Verbs are always in the infinitive form and nouns in the nominative singular.

The words are not chosen randomly but rather I have focused on choosing words that follow a number of simple rules. The list is also organized so that words that undergo similar transformations are grouped together. This is for your ease of use, nothing more.


The list

profundus, profundo
fundus, hondo
fabulare, hablar
furnus, horno
ferrum, hierro
filus, hijo
folia, hoja
fovea, hoyo
factum, hecho
octo, ocho
noctu, noche
lacte, leche
capere, caber
sapere, saber
lupus, lobo
pater, padre
mater, madre
liber, libro
thema, tema
theatrum, teatro
thesaurus, tesoro
thorax, tórax
aether, éter
anthropologia, antropología
orthographia, ortografía
philosophia, filosofía
materia, materia
resistentia, resistencia
aurum, oro
taurus, toro
autumnus, otoño
annus, año
scribere, escribir
scutum, escudo
scutella, escudilla
scriptor, escritor
ezkerra, izquierda
||||||
\$\endgroup\$
  • \$\begingroup\$ I think it's interesting in that it should be near impossible to get a perfect score without built-ins. As a suggestion I'd remove the non-ASCII words, or at least normalise them, and perhaps not let \$N\$ be too high. Also, I wonder what the default cat program would be. \$\endgroup\$ – Jo King Mar 3 at 12:31
  • \$\begingroup\$ @JoKing I am looking to somewhat twart perfect scores, I feel there should always be some room for improvement, It just is a little hard to balance this with golfing-languages ability for expressiveness. I am interested to hear what ranges for \$N\$ you think are too high. I started out by avoiding any non-ASCII characters, but it was really hard to build up a representative corpus of words. Plus the accents and eñe really are a feature of the language. I may adjust the scoring so that i and í for example are only half away from each other so that the penalty is small. \$\endgroup\$ – Ad Hoc Garf Hunter Mar 3 at 13:05
0
\$\begingroup\$

Ordinal to Cardinal

Given a positive integer represented as the English spelling of an ordinal number, return the equivalent cardinal number.

Rules

  • Where an integer requires multiple words to spell, only the last word changes.

  • The following integers are strongly irregular:

    • "one" becomes "first"
    • "two" becomes "second"
    • "three" becomes "third"
  • Other integers take a suffix of "th", however there are a few integers that are weakly irregular:

    • "five" becomes "fif(th)"
    • "eight" becomes "eigh(th)"
    • "nine" becomes "nin(th)"
    • "twelve" becomes "twelf(th)"
    • "twenty" to "ninety" become "twentie(th)" to "ninetie(th)".
  • The input can be assumed to be the English spelling of an ordinal number that follows the above rules to transform it into the equivalent cardinal number.

Examples

  • "one hundred and nineteen" becomes "one hundred and nineteenth"
  • "one hundred and twenty" becomes "one hundred and twentieth"
  • "one hundred and twenty one" becomes "one hundred and twenty first"

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

||||||
\$\endgroup\$
  • \$\begingroup\$ There are a lot of loosely related challenges, with this one being the closest. I don't think this is a dupe at all, though, since the amount to change is much more significant. Is there an upper limit on the input? If not, you definitely need to specify how the larger numbers might appear i.e. do we need to handle "milliard" as well as "million"? \$\endgroup\$ – FryAmTheEggman Mar 26 at 15:47
  • \$\begingroup\$ @FryAmTheEggman That and the other challenge takes the numbers as digits rather than words, which IMHO is a significant difference already. As for large numbers, you can assume for the purposes of the question that any number I forgot about takes a "th" suffix. \$\endgroup\$ – Neil Mar 26 at 22:30
  • \$\begingroup\$ Which integers do we need to handle? I'd suggest limiting it to, say, numbers from 1 to 99. Or if you do want all positive integers, could you please clarify how these are written out? \$\endgroup\$ – xnor Mar 27 at 20:57
  • \$\begingroup\$ @xnor a) this challenge is about words, not numbers b) the rules are there, I don't understand what you're missing \$\endgroup\$ – Neil Mar 27 at 21:51
  • \$\begingroup\$ @Neil Like, is "one billion, two hundred and thirty four million, five hundred and sixty seven thousand, eight hundred and ninety" a possible input, for which the output would be "one billion, two hundred and thirty four million, five hundred and sixty seven thousand, eight hundred and ninetieth"? If so, what is the exact format for such numbers? I understand that really only the last word matters for the conversion in the challenge, but it might make a difference for, say, a regex that does a replacement that might falsely trigger on something like "Duotrigintillion". \$\endgroup\$ – xnor Mar 27 at 22:01
  • \$\begingroup\$ @xnor Why would it falsely trigger on duotrigintillion? Is there no duotrigintillionth? \$\endgroup\$ – Neil Mar 27 at 22:39
  • \$\begingroup\$ @Neil I mean if it's part of a longer number and the regex does a replacement that doesn't check for the end of the string, but simply replaces certain sequences of characters. Duotrigintillion is an arbitrary example; I don't expect it specifically to actually "collide" with anything useful. \$\endgroup\$ – xnor Mar 27 at 22:42
  • \$\begingroup\$ @xnor Well, surely if it collides as the last word, then it will collide as an earlier word, which would be an error, according to the first rule? \$\endgroup\$ – Neil Mar 27 at 23:41
  • \$\begingroup\$ @Neil Oh, you're right, that would catch it. Maybe a more useful example is "one hundred and one" wrongly being made into 'first hundred and first". In any case, I think it would be useful to either add large-valued test cases or put an upper bound. \$\endgroup\$ – xnor Mar 28 at 0:54
  • \$\begingroup\$ @xnor I still don't see that it needs an upper bound. You can just assume that the rules I've given apply, even if they don't in real life for some reason. \$\endgroup\$ – Neil Mar 28 at 1:07
0
\$\begingroup\$

\$\Theta(N\cdot\sqrt N)\$ sort

The challenge is to write a program that sorts an array of distinct positive integers in ascending order. You may input the array and output the result using the default IO methods.

However, the worst-case time complexity of the algorithm used must be \$\Theta(N \cdot \sqrt N)\$, where \$N\$ is the length of the input array.

You may not assume your built-in sorting functions to have any time complexity in particular. While you can implement a fast (e.g. \$O(N \log N)\$) sort and then perform pointless operations to increase the complexity, direct algorithms exist.

This question is tagged , so the shortest code wins!

Sandbox stuff

I have noticed that a possible solution is, for example, to create a sorted multiset from the array and read it back. I would probably like to disallow that. Is there a way to achieve that without making the validity criteria subjective?

||||||
\$\endgroup\$
  • \$\begingroup\$ I feel like this will be answered by implementing sorting efficiently, then doing something pointless for the required number of steps. \$\endgroup\$ – xnor Apr 1 at 8:55
  • \$\begingroup\$ @xnor That would involve implementing a O(n log n) sort or radix sort, which can be more complicated than a O(n*sqrt(n)) algorithm. There's, for example, a gap sequence that results in O(n * sqrt(n)) complexity for Shellsort. \$\endgroup\$ – my pronoun is monicareinstate Apr 1 at 9:04
0
\$\begingroup\$

Modify The Stack

Let's say you have a stack, which at the start contains a b c in this order (a is on the top). You are given the required output stack, in any reasonable format (a list, a string, etc.), e.g. [a, c, b] (here a is on the top, below it c and below it b).

Your task is to output the shortest sequence of operations to achieve that stack formation, and you may assume that there is such sequence:

  • s - swap the top two elements of the stack, a b c -> b a c

  • d - duplicate the top element of the stack, a b c -> a a b c

  • t - swap (or rotate) the top three elements of the stack, a b c -> b c a

You may call the input/operations whatever you want, as long as it's consistent.

Examples

These might not be the shortest, please tell me if you find a shorter sequence

['a', 'c', 'b'] -> tts
([a b c] [b c a] [c a b] [a c b])
['a','a','b','c'] -> d
['a','b','a','b','c'] -> sdtsdt
([a b c] [b a c] [b b a c] [b a b c] [a b b c] [a a b b c] [a b a b c])

Score

This is a codegolf, so the shortest answer wins. good luck!

||||||
\$\endgroup\$
  • \$\begingroup\$ Specifying that the first element is the top of the stack could help understanding the challenge a lot. Can we use some other values instead of the stack elements a, b, c and/or the commands s, d, t? Also, the operation a b c -> b c a is often called rotate or roll. \$\endgroup\$ – Bubbler Mar 30 at 2:38
  • \$\begingroup\$ For test cases: a c b is tts. a b a b c can be done with dtdtt or dtdts. \$\endgroup\$ – Bubbler Mar 30 at 2:41
  • \$\begingroup\$ thanks, but dtdtt and dtdts doesn't work. \$\endgroup\$ – Command Master Mar 30 at 5:29
  • \$\begingroup\$ Sorry, I had the t operation mistaken, but your tdtsdt doesn't work either. The first operation should be s. \$\endgroup\$ – Bubbler Mar 30 at 5:39
  • \$\begingroup\$ right, I fixed that \$\endgroup\$ – Command Master Mar 30 at 5:46
  • \$\begingroup\$ I don't think the test cases are very helpful here until they are actually proven optimal... Do you really want to require input validation? If so, it is probably a very bad idea to post this without writing a reference implementation to make sure it's possible and not too annoying. (besides: I silently downvoted before because I simply dislike the idea, and not because of some specification issues, so I had nothing to comment) \$\endgroup\$ – my pronoun is monicareinstate Apr 5 at 16:05
  • \$\begingroup\$ @mypronounismonicareinstate Sandbox is all about feedback. Silent downvotes don't help the challenge writer and the community. If you don't like the whole idea, you could say so in the comments in the first place (preferably with why you think that way), and then the challenge writer could consider to rewrite it or abandon it and try out something different. \$\endgroup\$ – Bubbler Apr 5 at 23:25
0
\$\begingroup\$

How many Temtem can I breed?

Temtem is a monster-catching MMORPG. Within the game you have the ability to breed two Temtem to create an egg which then hatches into the baby of its mother. The ability to do this depends on several properties of the parent Temtem:

  • A Temtem has a gender, which is either male or female. To breed, you need one Temtem of each gender.
  • A Temtem has one or two types. A pair of Temtem can only breed if they have a type in common.
  • A Temtem has a fertility which ranges from 0 to 8. Temtem with a fertitilty of 0 can no longer breed in captivity. The fertility of each parent decreases by 1 when they breed.

The resulting Temtem inherits some of its properties from its parents.

  • The baby Temtem's gender is random. For the purposes of this question, this means that you can choose the gender, but you cannot change it later.
  • The baby Temtem inherits its mother's type. (This is not strictly true but it is always possible to evolve the baby to give the mother's type if necessary.)
  • The baby Temtem inherits the lesser of its parents' fertility.

Simple example:

  • One female Temtem with fertility 3 and one male Temtem with fertility 2 of the same type.
  • Breeding reduces their fertility to 2 and 1 and we choose the baby, which also has 1 fertility, to be male.
  • The female can breed again with both males, at which point all the Temtem now have 0 fertility.
  • This gives you a total of five Temtem.

You challenge is to write a program or function which accepts a list of Temtem and outputs the maximum number of Temtem it is possible to breed, assuming luck is on your side.

You can use any convenient input method for the Temtem, as long as it breaks no standard loopholes. For instance, you could use a string of three or four characters encoding the gender, fertility and type(s). (Your input method must be able to support 12 different types and 132 different pairs of types.)

You can output either the total number or the number of new Temtem, or you can also output the resulting list of Temtem in the order they were born.

This is , so the shortest program or function wins!

||||||
\$\endgroup\$
  • \$\begingroup\$ Without the types this makes an interesting "limited Fibonacci-like" growth - I'd be curious to see if it had already been studied. I think adding in the types makes it more likely that brute forcing will be the best approach. I haven't done much work on this yet, so of course I could be wrong. Separately, this definitely needs a test case where inter-type breeding gives a larger result than handling each separately, though I'm pretty sure you knew that. \$\endgroup\$ – FryAmTheEggman Apr 6 at 16:47
0
\$\begingroup\$

Word Grid Puzzle Iterator

I commonly see an advert for a word-based game, where, by removing a word from a grid of letters, the remaining letters "collapse", horizontally and vertically, leading to further words being findable.

The challenge is to take in a grid of characters and a word as an input, and output the collapsed grid after that word has been removed.

Words in the grid could be oriented in any direction.

This is code-golf, usual exclusions apply.

Example

The following set of examples follow on from each other - so the output from the first example is the input to the second.

AIR

In:

N   F   A   D   S   T
I   O   I   E   N   T
A   G   R   W   O   H
R   L   I   A   H   A
S   L   E   E   W   W

Out: If the word "AIR" is removed, none of the rows or columns are empty and so the rest of the grid remains as-is:

N   F       D   S   T
I   O       E   N   T
A   G       W   O   H
R   L   I   A   H   A
S   L   E   E   W   W

HAIL

If the word "HAIL" is removed, the letters in the 2nd-5th columns drop down one, making the word "SNOW" accessible:

N                   T
I   F       D   S   T
A   O       E   N   H
R   G       W   O   A
S   L   E   E   W   W

SNOW

If SNOW is removed, the columns collapse horizontally:

N               T   
I   F       D   T   
A   O       E   H   
R   G       W   A   
S   L   E   E   W   

THAW

If THAW is removed, the T drops down so that SLEET is now accessible:

N                       
I   F       D       
A   O       E       
R   G       W       
S   L   E   E   T   

SLEET

Removing SLEET clears a row and a column, and so the grid collapses in both directions:


N                   
I   F   D           
A   O   E           
R   G   W           

RAIN, DEW, FOG

The remaining three vertical words (RAIN, DEW, FOG) can then be removed individually:



F   D               
O   E               
G   W               


F                   
O                   
G                   





Notes

In the above examples, I have not resized the arrays as the outside rows/columns are made empty; instead just leaving them blank (i.e. the final array is 6x5, as is the starting array). Your program may also do this, or it may resize the array to remove empty rows and columns if you prefer.

For example, assuming the input is a 1x5 array:

H A T C E removing HAT could become _ _ _ C E or CE, both are valid. (underscores represent spaces for formatting purposes)

Inputs and Outputs:

Any reasonable format is acceptable - arrays, strings, etc. But:

  • you cannot assume that the orientation of the word to remove is the same as that in the input. e.g you won't get the input "LIAH" because the word HAIL is written right-to-left on the grid.
  • the output must be the same format as the input (i.e. the program must accept the output from the previous iteration as the grid input to the next)
  • You can assume the word will be in the grid, horizontally or vertically (not diagonally)
  • Words will never contain spaces, only the letters A-Z; and if the word is found but with a space in it, then that doesn't count as matching the word
    • You can assume the case of the word will match the grid, in whatever case suits your language (UPPER, lower, camelCase, whatever)
  • You can assume that the Input word will only appear once on the grid

Sandbox Questions

  • Does this feel too much like multiple challenges (find the word, collapse the array)?
||||||
\$\endgroup\$
  • \$\begingroup\$ I think the idea stands on its own logically, though perhaps there is a dupe out there somewhere. Separately, I think you should explain the situation where a word appears more than once. Your resizing comment also seems a bit odd: I would expect that if instead of HAIL the input was AGWOH the word wouldn't be able to be removed. \$\endgroup\$ – FryAmTheEggman Apr 3 at 20:20
  • \$\begingroup\$ Thanks for your comments as always. I have tried to clarify. I'm not sure what you mean about the resizing comment - only empty rows and columns can be removed; and words will always be A-Z (or whatever case you prefer) and must match exactly the input, in any orientation. \$\endgroup\$ – simonalexander2005 Apr 6 at 7:43
  • \$\begingroup\$ I see, that is what I expected, but when I read the challenge I was unsure. I think your edit makes it much clearer. (What I was trying to get at was that I expected gaps in unempty rows/columns to be "unmatchable", which I think before was made somewhat ambiguous by the wording of the purely aesthetic output) \$\endgroup\$ – FryAmTheEggman Apr 6 at 16:30
0
\$\begingroup\$

chaining couples with parity

Rules

Take the $n$ first integers (with $0$ included or not) with $n$ an even number except 0.

The goal is to produce a (not so) random chain of couples with these numbers, for example with input 6 : (5, 4), (1, 6), (3, 2)

But you have to respect a bit of parity and randomness :

  1. Each second number in a couple must have the same parity than the first number of the next couple. No rule for the first number of the first couple and the second number of the last couple. So the example above is not a correct answer.

(5, 4), (6, 1), (3, 2) is a correct answer for an input 6.

So this is a sort of parity chain.

  1. Your output should not always answer the same chain for the same input. It has to be random.

Input

An even number greater or equal than 2.

Valid output examples

  • Input: 2 Outputs (1, 2) and (2, 1) are valid. (0, 1) and (1,0) are also.

  • Input: 4 Output: (0, 1), (3, 2) (if start with 0) because 1 and 3 are odd

  • Input: 4 Output: (1, 4), (2, 3) (if start with 0)

  • Input: 6 Output: (0, 5), (1, 3), (4, 2)

  • Input: 8 Output: (0, 7), (1, 6), (2, 5), (3, 4)

Invalid output examples

  • Input: 4 Output:(1, 2), (3, 4) because 2 is even and 3 is odd.

  • Input: 6 Output:(5, 4), (1, 6), (3, 2) because 4 is even and 1 is odd and also because 6 is even and 3 is odd.

What if $n$ is odd?

No rule for $n$ if it's odd. All outputs accepted!

What about output's format?

No special formatting is expected. You just have to separate the couples such that one can correctly see them.

Sandbox Questions

Duplicate?

||||||
\$\endgroup\$
  • \$\begingroup\$ Use \$ instead of $ to use MathJax. Also, what do you exactly want by "random"? Is it acceptable to pick from two answers (e.g. pick between (1 2)(4 3)(5 6) and (5 6)(4 3)(1 2))? Check this and this. \$\endgroup\$ – Bubbler yesterday
0
\$\begingroup\$

The assignment logic may be used in a planning KoTH, in which a student bot chooses a full permutation from the classes and is awarded points from what preference they get.

Assign classes fairly and satisfyingly

Background

In a school, students are signing up for after-school classes. However, the capacity of each class is limited. In order to facilitate class assignment, each student is required to fill in a questionnaire to show his/her preference to the classes by listing all classes in decreasing order of his/her interests.

You are assigned to help assigning classes to them. You want to maximally satisfy their preferences while being fair with the assignment. A student can be assigned with multiple classes.

Challenge

Write a program or function that receives the following input:

  • a list of classes with the corresponding capacities; and
  • a list of students with their corresponding preference lists,

and output or return either:

  • a list of class with the list of students being assigned to that class; or
  • a list of students with their assigned classes.

You may use any reasonable alternative format for both input and output, for example, apart from receiving two arrays, you may choose to receive two strings, and especially for the second input (which requires a 2-D array), you may even have an input like this (first level delimiter \n, second level delimiter space):

1 2 3 4
4 2 3 1
1 3 2 4
2 3 4 1
3 4 1 2
4 1 2 3

To simplify the challenge, you may assume both classes and students are 0-indexed or 1-indexed. For the use of illustrating the requirements and samples, 1-indexing is used. You may also assume that each preference list is a full permutation of all classes.

The assignment requirements are as follows:

  • Fairness: All students must have roughly the same amount of classes assigned to them, that is, for every \$1\le i\le\text{[Number of students]}\$, $$\left|{\text{[Number of classes assigned]}_i-\frac{\sum\text{[Class capacities]}}{\text{[Number of students]}}}\right|<1.$$
  • Satisfaction: You should fulfill the preferences as well as possible. Specifically, you should fulfill as much first preferences as possible, then as much second preferences as possible, and so on. In case of having the same preference order, the classes should be assigned on first-come-first-served basis.

The fairness rule should be taken first if it conflicts with the satisfaction rule. Test case 3 is an example of handling such conflicts.

Test cases

Test case 1

Input:

classes = [2, 2, 2, 2],
students = [
 [1, 2, 4, 3],
 [2, 4, 1, 3],
 [3, 4, 2, 1],
 [4, 3, 2, 1]
]

Output:

classes = [
 [1, 3],
 [2, 1],
 [3, 4],
 [4, 2]
],
students = [
 [1, 2],
 [2, 4],
 [3, 1],
 [4, 3]
]

Explanation:

  1. It is clear that all 1st priorities can be fulfilled because all of them are different. So each student gets his 1st priority.
  2. Student 1 wants Class 2 as his 2nd priority, and Class 2 still has place for him. So he gets Class 2.
  3. Student 2 wants Class 4 as his 2nd priority, and Class 4 still has place for him. So he gets Class 4.
  4. Student 3 wants Class 4 as his 2nd priority, but Class 4 is already full. No place for him.
  5. Student 4 wants Class 3 as his 2nd priority, and Class 3 still has place for him. So he gets Class 3.
  6. Now each of the students except Student 3 has 2 classes already, so by the rule of fairness they are not considered in the subsequent assignments.
  7. Only Class 1 has place for Student 3, so he gets his 4th priority.

Test case 2

Input:

classes = [2, 2, 2],
students = [
 [3, 1, 2],
 [2, 3, 1],
 [2, 3, 1],
 [3, 2, 1]
]

Output:

classes = [
 [1, 2],
 [2, 3],
 [1, 4]
],
students = [
 [3, 1],
 [2, 1],
 [2],
 [3]
]

Explanation:

  1. It is clear that all 1st priorities can be fulfilled because none of the classes was chosen by 3 or more students as their 1st priorities.
  2. Student 1 wants Class 1 as his 2nd priority, and Class 1 still has place for him. So he gets Class 1.
  3. Student 2 wants Class 3 as his 2nd priority, but Class 3 is already full. No place for him.
  4. Student 3 wants Class 3 as his 2nd priority, but Class 3 is already full. No place for him.
  5. Student 4 wants Class 2 as his 2nd priority, but Class 2 is already full. No place for him.
  6. Now Student 1 has 2 classes already, so by the rule of fairness he is not considered in the subsequent assignments.
  7. Student 2 wants Class 1 as his 3rd priority, and Class 1 still has place for him. So he gets Class 1.
  8. All classes are already full, so no more seats can be assigned. Students 3 and 4 will only get 1 class each.

Test case 3

Input:

classes = [1, 1, 1, 2],
students = [
 [1, 2, 4, 3],
 [3, 4, 2, 1],
 [2, 4, 3, 1],
 [2, 4, 1, 3]
]

Output:

classes = [
 [1],
 [3],
 [2],
 [4, 2]
],
students = [
 [1],
 [3, 4],
 [2],
 [4]
]

Explanation:

  1. It is clear that all 1st priorities except for Student 4 can be fulfilled.
  2. If we ignore Student 4 and proceed to the second round, Student 2 and 3 will occupy the remaining seats and Student 4 will not get a place (which is disallowed by the fairness rule), so the 2nd priority of Student 4 will be considered first. Since Class 4 still has place for him, he gets Class 4.
  3. Student 1 wants Class 2 as his 2nd priority, but Class 2 is already full. No place for him.
  4. Student 2 wants Class 4 as his 2rd priority, and Class 4 still has place for him. So he gets Class 4.
  5. All classes are already full, so no more seats can be assigned. All students get 1 class each, except Student 2, who gets 2 classes.

Winning Condition

This is a code-golf challenge, so the shortest submission for each language wins. Standard loopholes are forbidden.

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

Chase the Easter Bunny around the garden, and grab as many eggs as you can.

In this instance, the garden is a 2-dimensional grid with 49 rows and 49 columns.

The Easter Bunny™️ is in the center of the garden, minding his own business, holding on to 100 Easter eggs. He'll hop away from where the most people are.

When the Easter Bunny™️ hops, we all know he'll leave behind an Easter egg.

Grab an Easter egg for 1 point. Grab the Easter Bunny for 10 points.

The game starts with 4 hunters, one in each corner of the garden.

The hunters can take 1 step each turn, in one of the 4 cardinal directions (North, South, East or West). When they've each taken a step (or decided not to), the bunny will take a move.

The bunny can hop to any position up to 4 spaces away in both the x and y axes. It will decide where it will hop to by the position of the hunters.

It will hop north if there are more hunters to the south than to the north (ignoring the same row). If there are 3 to the south, and 1 to the north, it will hop north by 2 spaces. This same dynamic will be used to decide where it will hop to on the X axis.

The game ends when:

  • The Easter Bunny™️ leaves the garden.
  • The Easter Bunny™️ drops his last egg.
  • The hunters catch the bunny.

How to hunt the bunny?

Your code will take the form of an array of 4 JS functions, which will each control a hunter starting in these positions (in this order):

  • North West (0, 0)
  • North East (0, 48)
  • South East (48, 48)
  • South West (48, 0)

The functions should each have this fingerprint:

function(api, my_storage, shared_storage) {
}
  • api is your function's interface to the game (see below)
  • my_storage is an object available to this function each time it's called.
  • shared_storage is an object available to all hunters each time they're called.

The API

The api object presents these four movement functions:

  • api.north()
  • api.east()
  • api.south()
  • api.west()

If any of these are called during your function, the hunter will take one step in that direction (or the last called of these four directions). If none of thess are called during your function, the hunter will stand still.

It also provides information about the state of the game with these methods:

  • api.turn - Returns a number of turns taken in this game so far.
  • api.bunny - Returns an object of bunny-related info

    { x: 25, y: 25, eggs_left: 100 }

  • api.hunters - always 4 results

    [ {x: 0, y: 0, me: true}. ... ]

  • api.eggs

    [ x: 25, y: 25 ]

Template

Teams.concat(
  [
    function(api, my_storage, shared_storage) {
      // NW hunter
    },
    function(api, my_storage, shared_storage) {
      // NE hunter
    },
    function(api, my_storage, shared_storage) {
      // SE hunter
    },
    function(api, my_storage, shared_storage) {
      // SW hunter
    }
  ]
)

How to participate (speculative)

  • git clone git@github.com:someone/bunny_hunt.git
  • cd bunny_hunt
  • cp template_entry.js entries/my_entry.js
  • (Write your hunter code)
  • node one_match.js entries/my_entry.js to see the result
  • node all_matches.js to see all results (if you import more entries)

Deadline

This will run until the 19th of April, one week after Easter Sunday (in the traditions which celebrate Easter Sunday on the 12th of April this year).

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

Reverse Internal Truth Machine

Ok, the previous one was too easy, because stack languages.

0              # Push input
 Truth machine # Do stuff

However, what if instead of putting it at the start, you put it at the end? Of course, this is still trivial for ><>, but what about for other languages?

Bonus

How about a -20% bonus?

A suggestion was made in my original question where it should do something else if something else was put there, or nothing was put there at all!

So the bonus is, if there is nothing at the end, it should print 'Truth Machine'.

||||||
\$\endgroup\$
  • 1
    \$\begingroup\$ Idea: put the input in the exact middle of the program. Otherwise it's still too trivial for prefix languages. E.g. Pyth and Husk. \$\endgroup\$ – petStorm 15 hours ago
  • \$\begingroup\$ That's just the same as this. 05AB1E: ReverseInternalTruthMachine0qsomestuffhere \$\endgroup\$ – PkmnQ 15 hours ago
  • \$\begingroup\$ I can't understand absolutely anything in this proposal. \$\endgroup\$ – my pronoun is monicareinstate 13 hours ago
0
\$\begingroup\$

How Many Ways To Empty The Glove Box?

Inspired by this 538 Riddler Express Puzzle.

Task

You are given an positive integer n, and a list A = [a_1, a_2, ..., a_k] of k distinct positive integers.

A restricted composition of n is an ordered list P = [p_1, p_2, ..., p_m] where each p_i is a (not necessarily distinct) member of A, and p_1 + p_2 + ... + p_m = n.

So, if n=10, and A = [2,3,4] then an example of a restricted composition would be P = [3,4,3]. Another example would be P = [2,3,3,2]. A third example would be P = [3,3,4]. But there's no restricted composition that starts [3,3,3,...], because 10-(3+3+3) = 1, which is not in A.

We want the total number of different restricted compositions given the inputs, as an integer.

Inputs

A positive integer n and a list A of positive integers. All reasonable input formats allowed.

Output

The number of distinct restricted compositions.

This is ; we seek the shortest solution in bytes. The usual restrictions are in play; no loopholes allowed.

Test Cases

(5, [2, 3, 4]) => 2
(10, [2, 3, 4]) => 17
(15, [3, 5, 7]) => 8

Tags

||||||
\$\endgroup\$
-1
\$\begingroup\$

Program calculating its own length

Task

Your task is simple: write a program that produces its own length, without using any literals or built-in constants other than 0 (or its equivalents in your language).

Rules

  1. Your code must print its own length in bytes when run, followed by a single newline.
  2. Your code cannot use any literals other than 0 (or whatever equivalents your language might have). This includes string and character literals.
  3. Your code cannot use any built-in constants of your language, unless these are guaranteed to always have the value 0.
  4. Any functions and operators provided by your language can be used.
  5. You're not allowed to use any external libraries or external resources in your program.

Scoring

The score of a valid program is its length in bytes. The score of an invalid program is ∞.
As this is code golf, lowest score wins.

||||||
\$\endgroup\$
  • \$\begingroup\$ Does "any literals" include the more involved ones like function, array and object literals? Apart from this restriction, I'm pretty sure this has been asked before. \$\endgroup\$ – Martin Ender Aug 3 '14 at 17:54
  • 3
    \$\begingroup\$ @MartinBüttner Probably a dupe: codegolf.stackexchange.com/q/27079/16402 \$\endgroup\$ – user16402 Aug 3 '14 at 17:58
  • 1
    \$\begingroup\$ Would this Python entry be valid (not golfed)? It uses only globals. text = open(__file__, 'rb').read(); length = len(text); print(length) \$\endgroup\$ – Isiah Meadows Aug 12 '14 at 5:41
  • \$\begingroup\$ May we use built-in lists that are guaranteed to be []? \$\endgroup\$ – Adám Feb 8 '19 at 8:28
  • \$\begingroup\$ In Jelly (and likely much more esolangs), a empty program outputs 0, producing an answer that is very hard to beat; Try it online! \$\endgroup\$ – my pronoun is monicareinstate May 24 '19 at 8:44
1
80 81
82
83 84
92

You must log in to answer this question.

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