Sandbox for Proposed Challenges

Question

This "sandbox" is a place where Code Golf users can get feedback on prospective challenges they wish to post to main. This is useful because writing a clear and fully specified challenge on your first try can be difficult, and there is a much better chance of your challenge being well received if you post it in the sandbox first.

Sandbox FAQ

Posting

To post to the sandbox, scroll to the bottom of this page 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, though you can optionally add a title at the top. You may also add some notes about specific things you would like to clarify before posting it. Other users will help you improve your challenge by rating and discussing it.

When you think your challenge is ready for the public, go ahead and post it, and replace the post here with a link to the challenge and delete the sandbox post.

Discussion

The purpose of the sandbox is to give and receive feedback on posts. If you want to, feel free to give feedback to any posts you see here. Important things to comment about can include:

• Parts of the challenge you found unclear
• Comments addressing specific points mentioned in the proposal
• Problems that could make the challenge uninteresting or unfit for the site

You don't need any qualifications to review sandbox posts. The target audience of most of these challenges is code golfers like you, so anything you find unclear will probably be unclear to others.

If you think one of your posts requires more feedback, but it's been ignored, you can ask for feedback in The Nineteenth Byte. It's not only allowed, but highly recommended! Be patient and try not to nag people though, you might have to ask multiple times.

It is recommended to leave your posts in the sandbox for at least several days, and until it receives upvotes and any feedback has been addressed.

Other

Search the sandbox / Browse your pending proposals

The sandbox works best if you sort posts by active.

To add an inline tag to a proposal, use shortcut link syntax with a prefix: [tag:king-of-the-hill]. To search for posts with a certain tag, include the name in quotes: "king-of-the-hill".

Answer 1

Compress even permutations

Factorial number system

Every nonnegative integer can be encoded by factorial number system. Factorial number system doesn't have a fixed radix, but uses the factorial of nonnegative integers as radices. The place of \$0!\$ can have \$0\$ as the digit, the place of \$1!\$ can have \$0\$ or \$1\$ as the digit, the place of \$2!\$ can have \$0\$, \$1\$, or \$2\$ as the digit, and so on. Subscript exclamation mark denotes that the integer is encoded in factorial number system. For example:

$$ 41010_! = 4 \times 4! + 1 \times 3! + 0 \times 2! + 1 \times 1! + 0 \times 0!= 103_{10} $$

Permutations

Numbers encoded by factorial number system has one-to-one correspondence to permutations:

$$ 41010_! \cong \begin{pmatrix} 0 \\ 0 \end{pmatrix} \begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix} \begin{pmatrix} 2 & 1 & 0 \\ 2 & 1 & 0 \end{pmatrix} \begin{pmatrix} 3 & 2 & 1 & 0 \\ 0 & 3 & 2 & 1 \end{pmatrix} \begin{pmatrix} 4 & 3 & 2 & 1 & 0 \\ 3 & 2 & 1 & 0 & 4 \end{pmatrix} = \begin{pmatrix} 4 & 3 & 2 & 1 & 0 \\ 1 & 3 & 2 & 0 & 4 \end{pmatrix} $$

That is, each the place of \$n!\$ represents a right-direction rotation of \$n\$ through \$0\$, and its digit represents what \$0\$ becomes after the rotation.

It follows that the parity of the permutation is same as the parity of the sum of digits at the places of factorials of odd numbers. For \$41010_!\$, the permutation is even because \$1 + 1 = 2\$ is even.

Objective

An even permutation of 5 elements, or any equivalent object will be the input. That leaves \$5! \div 2 = 60\$ distinct permutations. Compress it to \$\lceil \log_2{60}\rceil=6\$ bits.

Rules

• Input type and format doesn't matter. Possible choices of input format include (in C++):

  • std::map<int,int> scrambling the numbers from \$4\$ to \$0\$

  • int[5] containing the digits of the factorial number system

  • int[4] containing the digits of the factorial number system, except the place of \$0!\$ (it doesn't contribute to the permutation)

  • int encoded by the factorial number system

• Output type and format doesn't matter either. It may be:

  • bool[6]

  • int8_t

  • a bit field

  • std::string containing ASCII digit 0s and 1s

• Invalid inputs fall in don't care situation.

Answer 2

Simplify a directed graph

code-golf graph-theory math

Input

A connected directed graph, in any convenient format. A valid format (and probably the most convenient) would be a list of edges.

Simplification

These two reductions are performed as often as possible. It does not suffice to apply one reduction first, then the other, as each of them can cause more of the other one.

Let \$E\$ be the set of all edges of the graph in the following explanations. For example \$E = \{(0, 1), (1, 2), (2, 0)\}\$ represents the following graph:

0 ----> 1
^       |
'-- 2 <-'

Let \$E_a\$, where \$a\$ is a vertex, indicate the set of edges involving \$a\$:

$$E_a := \{(u, v) \in E : u = a \vee v = a\}$$

Two graphs are isomorphic iff all vertices from one graph can be relabeled to make it equal to the other graph.

Deduplication

If there are disjoint sets of vertices \$M\$ and \$N\$ (\$M \cap N = \emptyset\$) not directly connected (\$((M, N) \cup (N, M)) \cap E = \emptyset\$) and the graphs with edges \$E \setminus E_M\$ and \$E \setminus E_N\$ are isomorphic, then the vertices \$M\$ (or \$N\$, but not both, are removed).

This means that of any two non-overlapping, non-directly-connected subgraphs that leave isomorphic graphs behind when removed, one is removed.

Simple example:

b --> 1
      ^  ==>  b --> 1
      |
      a

Relay removal

If there are vertices \$a\$ and \$b\$ and a non-empty set of vertices \$N\$, such that \$b \notin N\$ and \$E_b = \{(a, b)\} \cup (b, N)\$, then \$b\$ is removed from the graph and edges \$(a, N)\$ are added if they do not alreay exist.

This means that a vertex with exactly one edge ending there, at least one edge starting there and no self-loop can be removed, moving the starting edges to the start of the ending edge.

Simple example:

            1             1
            ^             ^
            |             |
O --> a --> b  ==>  O --> a ----.
      ^     |             ^     |
      |     v             |     v
      '---- 2             '---- 2

Output

The output is the result of the reductions, in any convenient format. If identifiers are used for edges or vertices, as in a list of edges, these identifiers are not required to correspond to identifiers in the input.

A different format may be used for input and output.

Scoring

This is code-golf: Lowest bytecount in each language wins. No answer will be accepted, as there is no overall winner.

Other rules

• Standard loopholes apply
• Functions or programs
• Any input and output methods (STDIN, arguments, prompt(), ...)

Test cases

not yet

Meta:

• Everything clear?
• Better explanations?
• Better title?
• I'm not sure whether output might depend on the order in which reductions are performed.

Answer 3

Let's Play Countdown!

(The Numbers round this time)

code-golf math

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?

Answer 4

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.

Answer 5

Doubly stochastic matrix code-golf

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.

Answer 6

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.

Answer 7

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.

code-golf, 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)

Answer 8

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,اجير أو عامل

2. 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()

Answer 9

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!

Answer 10

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

Answer 11

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.

Answer 12

Dilapidated art gallery problem

code-golf ascii-art

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.

Answer 13

For How Long am I Alone? code-golf

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.

Answer 14

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 code-golf, so the shortest program or function that breaks no standard loopholes wins!

Answer 15

Mom-rounding the time code-golf time arithmetic integer

Context

Growing up with my mother, whenever she looked at a clock to check the time, she would always say "shoot, it's already X!" and then I would look at the clock and realize she was just rounding the time in a really weird way.

Task

Given a time with hours and minutes, round it like my mom would. Rounding always occurs upwards. Say it is currently H hours and M minutes.

• if M is 0, no rounding occurs; my mom isn't that crazy;
• if M is 9 or less, my mom rounds to H:15;
• if M is 19 or less, my mom rounds to H:30;
• if M is 34 or less, my mom rounds to H:45;
• for any other value of M, my mom rounds to H+1:00.

Input

You will take a time that needs rounding, in any sensible format. ISO strings for date/time, two integers representing hours/numbers, a string with two integers and a separator; these are all fair game.

Output

The string "shoot, it's already X" with X replaced with the mom rounding time.

Scoring

This is code-golf so shortest answer wins. However, if your source code contains the substring shoot, it's already then you may subtract 19 from your score.

Test cases

Here is the program I use to generate the test cases.

11:00 -> shoot, it's already 11:00!
 3:08 -> shoot, it's already 03:15!
 1:09 -> shoot, it's already 01:15!
13:13 -> shoot, it's already 13:30!
 2:35 -> shoot, it's already 03:00!

Answer 16

Answer 17

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 code-golf, so the shortest program or function wins!

Answer 18

Word Grid Puzzle Iterator

code-golf

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)?

Answer 19

chaining couples with parity code-golf math integers array

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 \$n=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 \$n=6\$.

So this is a sort of parity chain.

2. First number (of the first couple) has to be chosen randomly (uniform) in the \$n\$ first integers.

Input

An even number \$n\$ greater or equal than 2.

Valid output examples

• Input: \$n=2\$ Outputs (1, 2) and (2, 1) are valid. (0, 1) and (1,0) are also.

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

• Input: \$n=4\$ Output: (1, 4), (2, 3) (if start with 0)

• Input: \$n=6\$ Output: (0, 5), (1, 3), (4, 2)

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

Invalid output examples

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

• Input: \$n=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?

Answer 20

Rot1Rot3 code-golfstring

Write a program or function such that given a string \$ S \$, encode it with Rot1Rot3. To encode it, do the following:

1. Take \$ S\$ and partition it into blocks with \$ 3 \$ characters each. If it does not partition equally (i.e. \$ |S| \bmod 3 \neq 0 \$), take away some characters from the end of the string until it does, and form a smaller partition from the 'taken-away' characters.

2. For each individual partition, rotate it to the right by \$ 1 \$ step.

3. Finally, rotate all of the partitions together to the right by \$ 3 \$ steps, as if each partition were one character.

Example

Input: Hello, code golf!

1. Partition it like so: |Hel|lo,| co|de |gol|f!| (pipes to show separation). Notice that f! does not form a full partition, and is therefore left as a partition with \$ 2 \$ characters instead.

2. Rotate each individual partition to the right by \$ 1 \$ step: |lHe|,lo|o c| de|lgo|!f|.

3. Rotate the partitions as a whole to the right by \$ 3 \$ steps: | de|lgo|!f|lHe|,lo|o c|.

Final Output: delgo!flHe,loo c

Additional Info

• You can expect any sequence of any characters, as long as they are printable.
• This is code-golf, so the shortest code in bytes wins.

Test Cases

Input

Hello, code golf!
flog yhcrana
Rot1Rot3
abababa
import this
1
21
All animals are equal, but some animals are more equal than others.

Output

 delgo!flHe,loo c
yg rhcaanofl
tRoo1R3t
aabbbaa
torh tsipim
1
12
hotser.lAln aaim lsearq eluab,  utmsoae mnisalr ame eorq eluah t an

Answer 21

Check my Knight's Tour

Given as input an n-by-n matrix of integers, check that all integers from 1 to n² are present, and that all pairs of consecutive integers are exactly a Knight's move apart. (For instance, a 4-by-4 board with the values

1 2 1 2
2 1 2 1
1 2 1 2
2 1 2 1

would meet the condition that all 1s would have a 2 that was exactly a Knight's move away, but this would of course not constitute a Knight's Tour.) The integers 1 and n² do NOT need to be a Knight's move apart. You must be able to support at least 7 different values for n including 10.

A Knight's move is possible between any two squares that are a Euclidean distance of √5 apart.

Output follows normal decision-problem rules.

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

Answer 22

How could these rep and scores have happened?

code-golf arithmetic integer

Challenge: Given a reputation score, a count of questions with accepted answers, and a list of net votes on questions, calculate a sequence of actions that could have produced them. To keep this simple, here's a few simplifications from how Stack Exchange actually works:

• The only things that change reputation are upvotes on questions (+10), downvotes on questions (-2), and accepting an answer to a question (+2).
• The daily cap of 200 never comes into play.
• Votes are never retracted and accepts are never rescinded.

The minimum possible reputation of 1 still applies. If there are multiple sequences of actions that can produce the given state, then your program/function should return the shortest possible sequence (or one of the shortest, if there's multiple that are tied for the shortest). If there are no sequences of actions that can produce the given state, consider that Undefined Behavior, so it doesn't matter what your program does.

Examples/test cases:

• A user has 1 reputation, hasn't accepted any answers, and has no questions. The shortest possible sequence is "".
• A user has 33 reputation, has accepted 1 answer, and has questions with scores 2 and 1. A shortest possible sequence is "upvote, upvote, upvote, accept".
• A user has 3 reputation, hasn't accepted any answers, and has a question with score -5. The shortest possible sequence is "downvote, downvote, upvote, downvote, downvote, downvote, downvote".

The standard restrictions against loopholes apply. I/O may be in any convenient format. Examples: For input, [101,0,4,3,2,1] or (101,0,[4,3,2,1]) could mean a user with 101 reputation, 0 questions with accepted answers, and questions with scores 4, 3, 2, and 1. For output, the string UDA could mean "upvote, downvote, accept".

This is code golf, so the shortest program/function wins.

Answer 23

Draw a Bracket

A bracket is a way of organizing a tournament as a tree structure. It follows several rounds of matches with half of the competitors being eliminated each round, until one competitor remains.

In this challenge you will be given as input a list of one digit \$(0-9)\$ integers as input representing competitors and you should output an ASCII representation of a bracket. The exact specifications are in the Output section of this challenge.

For example if the input is 1 2 3 4 5 6 7 8 then the output would be:

1
 1
2
  1
3
 3
4
   1
5
 5
6
  5
7
 7
8

In this challenge the lower number is always the winner in a matchup.

Input

The input will always be of length \$2^n\$ for some positive integer \$n\$, and will consist entirely of one digit numbers. You may take the integers as their representative characters instead if this pleases you.

Output

I will explain precisely how the output is created momentarily, it is a bit hard.

Scoring

This is code-golf the shortest answer in bytes wins.

Answer 24

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 code-golfarray-manipulation

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.

The program should terminate in finite time for all practical sizes of inputs.

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.

Test case 4

Input:

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

Output:

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

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. However both Classes 1 and 3 are full, he can only get Class 4.
3. The remaining place for Class 4 goes to Student 2, and we have 3 1st priorities, 1 2nd priority and 1 4th priority fulfilled.
4. But this is not the best. By breaking the first-come-first-served rule for 1st priority, we can get the best - 3 1st priorities and 2 2nd priorities fulfilled.

Winning Condition

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

Answer 25

Euler's Geometry Puzzle

posted

Answer 26

posted

Answer 27

Convert CSV to GeoJSON

Given an input in this CSV format:

Latitude,Longitude,Name,Value
-37,145,Melbourne,4500000
-34,150,Sydney,5000000

produce this output (GeoJSON):

{
    "type": "FeatureCollection",
    "features": [
        {
            "type": "Feature",
            "properties": {
                "Name": "Melbourne",
                "Value: "4500000"
            },
            "geometry": {
                "type": "Point",
                "coordinates": [-37, 145]
            }
        }
    ],
...
}

You may assume that:

• The input will always be a well formed CSV file in this format. (No meta rows/front matter, no quoted strings, no spaces between fields, no problematic characters.)
• The input will contain one "Longitude" and one "Latitude" column, capitalised that way.
• The Latitude and Longitude columns may not be in that order, nor necessarily the first two columns.
• The number of other columns may be zero or many. They must all be converted.
• There will always be one header row. There may not be any data rows.

Notes regarding the output:

• must be valid GeoJSON (test with geojsonlint.com if you're not sure). Note: There must be a properties object, even if it is {}.
• is correct if it is semantically equivalent. (The order of keys does not matter).
• Whitespace does not matter.
• Treat all properties as strings.

Input and output in any of the standard ways for text input/output. Note the output must be text, not an object. (Ie, in JavaScript, use JSON.stringify())

Answer 28

Finitly inverese in base N code-golf math

Your task is when given a base N (you can assume it's \$ \geq2 \$) you need to output all natural numbers for which the decimal expansion of \$ \frac{1}{x} \$ in base N is finite.

Input

You can take the base N in any reasonable format, and you also may take an additional number N, depending on what output format you chose.

Output

You have 3 options for the output format:

• Take a number n and output the n-th number in the sequence
• Take a number n and output first n numbers in the sequence
• Take no additional input and output the list indefinitely

Test Cases

10 -> [1, 2, 4, 5, 8, 10, 16, 20, 25, 32, 40, 50, 64, 80, 100, 125, 128, 160, 200, 250, 256, 320, 400, 500, 512, 625, 640, 800, 1000, 1024, 1250, 1280, 1600, 2000, 2048, 2500, 2560, 3125, 3200, 4000, 4096, 5000, 5120, 6250, 6400, 8000, 8192, 10000, ...]
2 -> [1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, ...]

Answer 29

This Question Has _____ Views code-golf stack-exchange-api

posted

Answer 30

Making a programable computing chip

Make a programable chip with 8000 commands ROM and 48 16-bit unsigned words RAM initalized with zero.

---

These commands should be supported:

a = b + c  # mod 65536
a = b - c
a = b * c
a = b / c  # undefined behavior if c==0
a = b % c
a = b > c  # return 0 or 1
a = b >= c
a = b == c
a = b != c
if a goto b 
if !a goto b
call a, b  # store ip of next command to b and goto a, then can return
input a
output a
a = [b] # You can decide constant k and l, such that [kn+l] is rn. 
[a] = b # Using undefined [n] is UB

where a, b, c can be r0-r47 or a constant of a 16-bit integer or the ip of a command. Writing to a constant is a nop, so input 42 discards an input. Mixing ip and integer, running out of commands are undefined behavior.

For example,

L1: input r1
    r0 = r0 + r1
    output r0
    if !0 goto L1
    r2 = r1 + L1

takes input, and output sum of all inputs modulo 65536. r2 = r1 + L1 is undefined behavior, but since it's never executed it's not a problem.

---

The circuit consists of controlled gates (x,y,c,t), meaning that wire x and wire y are connected if wire c was active(t=1) or inactive(t=0), and programable wire (x,y,0,0), meaning that wire x and wire y can be programmed to be connected.

At the beginning, none of the wires, except IO wires(discuss later), is active. In each step, any wire connected to wire 0, whether directly or indirectly, is active.

IO is used to connect multiple such component. It contains 18 wires, where 16 of them store an integer to be passed, and two A and B meaning if there's data on the wire. When sender send, sender negate A; when reciever recieve, B negated. Therefore, there's data on the wire iff A!=B.

We write A on input, B on input, A on output, and B on output of the chip, as 4, 8, 5, 9, respectively, and the 16-bit input on 16-31, output on 32-47. You can active wires where you are expected to read from, but your chip should handle with another such chip (so if you write to input, you should handle cases when output is inputted).

For example, {(0,5,4,1),(0,8,9,1)} output zero whenever recieving an input.

---

You should submit a circuit (a set of 4-elem tuples) and a compiler. Smallest circuit win.