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

See the Sandbox FAQ for more information on how to use the Sandbox.

## 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]

Posted: Stepping Through Time

# Quickly calculate $$\ n! \bmod p \$$fastest-codefactorial

The idea is extremely simple: Given two positive integers $$\ n \$$ and $$\ p \$$, calculate the result of $$\ n! \bmod p \$$, where $$\ p \$$ is a prime.

## Scoring

Your score is the highest $$\ p \$$ you can achieve within $$\ 10 \$$ seconds, by running the program $$\ 10 \$$ separate times. More specifically, each run-through will contain two inputs $$\ n \$$ and $$\ p \$$. You are to solve $$\ n! \bmod p \$$, where $$\ n \$$ is a random number in the range $$\[1, p]\$$.

You must use this program to generate the $$\ 10 \$$ test cases. So for example, if $$\ p = 13 \$$, the test case would look like this:

n, p
9, 13
3, 13
10, 13
13, 13
7, 13
13, 13
8, 13
9, 13
6, 13
4, 13


## Rules

• Make sure that each test case is run separately, meaning you are not allowed to make use of previous test cases
• Official times will be tested on my machine; make sure to include specifcations on how to run it

This is , so the highest score wins!

## Sandbox

• Any loopholes that need to be addressed?
• Is there an easy, trivial solution to this?
• To force independent calculation you should invoke the program 10 separate times. Although it remains possible to store data in files or similar, it would be pretty obvious. – user202729 May 22 at 8:58
• As far as I know the best-known time complexity is asymptotically $\widetilde O (\sqrt p)$, although the implementation is rather tedious and uninteresting. – user202729 May 22 at 9:00
• Your example test case has p=10 which isn't prime – xnor May 22 at 10:31
• @xnor Fixed, thanks. – dingledooper May 22 at 15:53

# Shorten the numbers

These numbers are taking up far too many bytes on my computer. Create a function/program to shorten any number using only Alphanumeric characters as the output.

# Scoring

Scoring is based on optimized-output. Shortest number of characters produced for the following randomly generated numbers (plus one special number with repetition) wins. Add the number of output characters output for the 5 test numbers together for total score.

• 94949267912781
• 75477115147709
• 79547324913976
• 12345678998765
• 11111122222222

The score of the non-optimized numbers = 70. (14 * 5)

# Sandbox questions

• does scoring make sense?
• should I include a sample script, output, or both?
• should I be more clear the answers should work on any number? (ie. "replacing each test number with one character is disallowed")?
• Base conversion from base 10 to base-255? – Third-party 'Chef' May 23 at 8:29
• As long as you're scoring on those five test numbers, the winning score is going to be the absolute smallest thing you haven't explicitly forbidden. Not allowing solutions to be tailored to those five is what we'd call a non-observable requirement, and considering how many different ways it could be approached I'm not sure how well a human could even really try to judge it. On the other hand, if you try to score it over the natural numbers, we just do base conversion. I feel like this can't work as an output optimization challenge. – Unrelated String May 23 at 10:07

Inspired by Wizard creating a jewelry.

Given an input list of positive integers, calculate the minimum cost of creating the list from the following operations:

1. Appending a positive integer costs the value of the integer.
2. Incrementing the entire list costs 2.
3. Exchanging two consecutive elements of the list costs 1.

Example: The list 1 4 9 16 25 could be constructed as follows:

• Append 1
• Append 8
• Append 17
• Increment
• Increment
• Increment
• Increment
• Increment
• Append 1
• Swap 22 with 1
• Swap 13 with 1
• Swap 6 with 1
• Increment
• Increment
• Increment
• Append 1
• Swap 25 with 1
• Swap 16 with 1
• Swap 9 with 1
• Swap 4 with 1

This costs 51, which is an improvement over simply appending the integers, as that is a cost of 54.

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

• Seems clear, but another test case or two might be helpful. – Dingus May 29 at 7:32

# Cheat activated

### Background

The game Grand Theft Auto: San Andreas went down to history also thanks to its wide selection of cheats. They're almost 90 and anyone who has ever touched this game, no doubt he tried them all!
One cheat is activated (on PC) typing in-game a secret keyword, and then boom, a jet pops out of thin air or perhaps all pedestrians look like Elvis Presley or some other rowdy effect...

They always come with this confirmation message:

Rockstar choosed to store them hashed, so due to collision, in addition to the intended ones there are many other strings that trigger every cheat.

Therefore I propose to solve this downside!

Write a full program that prints CHEAT ACTIVATED if and only if the last part of a string is a cheat code.

## Cheat codes

THUGSARMOURY
PROFESSIONALSKIT
NUTTERSTOYS
INEEDSOMEHELP
TURNUPTHEHEAT
TURNDOWNTHEHEAT
PLEASANTLYWARM
TOODAMNHOT
DULLDULLDAY
STAYINANDWATCHTV
CANTSEEWHEREIMGOING
TIMEJUSTFLIESBY
SPEEDITUP
SLOWITDOWN
ROUGHNEIGHBOURHOOD
STOPPICKINGONME
SURROUNDEDBYNUTTERS
TIMETOKICKASS
OLDSPEEDDEMON
DOUGHNUTHANDICAP
JUSTTRYANDSTOPME
WHERESTHEFUNERAL
CELEBRITYSTATUS
TRUEGRIME
ALLCARSGOBOOM
STICKLIKEGLUE
GOODBYECRUELWORLD
DONTTRYANDSTOPME
ALLDRIVERSARECRIMINALS
PINKISTHENEWCOOL
SOLONGASITSBLACK
FLYINGFISH
WHOATEALLTHEPIES
BUFFMEUP
LEANANDMEAN
BLUESUEDESHOES
ATTACKOFTHEVILLAGEPEOPLE
LIFESABEACH
ONLYHOMIESALLOWED
BETTERSTAYINDOORS
NINJATOWN
LOVECONQUERSALL
EVERYONEISPOOR
EVERYONEISRICH
CHITTYCHITTYBANGBANG
CJPHONEHOME
JUMPJET
IWANTTOHOVER
TOUCHMYCARYOUDIE
SPEEDFREAK
BUBBLECARS
NIGHTPROWLER
DONTBRINGONTHENIGHT
SCOTTISHSUMMER
SANDINMYEARS
KANGAROO
NOONECANHURTME
MANFROMATLANTIS
LETSGOBASEJUMPING
ROCKETMAN
BRINGITON
STINGLIKEABEE
IAMNEVERHUNGRY
STATEOFEMERGENCY
CRAZYTOWN
TAKEACHILLPILL
FULLCLIP
GHOSTTOWN
HICKSVILLE
WANNABEINMYGANG
NOONECANSTOPUS
ROCKETMAYHEM
WORSHIPME
ICANGOALLNIGHT
PROFESSIONALKILLER
NATURALTALENT
OHDUDE
FOURWHEELFUN
ITSALLBULL
FLYINGTOSTUNT
MONSTERMASH


## Input

• A string $$\s\$$ over the alphabet:
[A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z]

# Output

• Print CHEAT ACTIVATED if there exist a cheat code $$\c\$$ such that $$\c\$$ is a suffix of $$\s\$$
• Nothing otherwise

This is , so the shortest code wins.

• Do we have to output the specific Cheat activated string, or just a truthy/falsy value indicating whether or not a valid cheat code exists? (I also don't think $i$ is a good name for a string; is that intentional?) – my pronoun is monicareinstate May 21 at 4:27
• @my pronoun is monicareinstate Yes, that specific string, it's a little simulation. And yes, you're right $s$ is the canonical name, I choose "i" for input, but never mind – Domenico Modica May 21 at 4:39
• I think that restricting the output to Cheat activated is unnecessary since it doesn't really add anything to the challenge. Consider allowing just a truthy or falsey value as output. – math junkie May 21 at 19:01
• @math junkie I'm aware that in terms of logic it's useless. But that comes if only the "recognition part" is considered being the intended challenge. From my idea, generating Cheat activated it's also a part of it... I worded it badly in the task part – Domenico Modica May 21 at 20:08
• 18HOLES is in the cheat codes list, yet the input states that there will be no number. Is this intended? – dingledooper May 22 at 21:20
• @dingledooper No, my mistake, I thought I had removed it in the last edit – Domenico Modica May 22 at 23:07

# Convert an integer to Chinese numerals

Your task is to convert an integer from 1 to $$\10^{52}-1\$$ (inclusive).

The characters from 1 to 10 with their Unicode code points are:

一 1 U+4E00



Number greater that that are composed like this:

十一 11

...

...

...

...

...

...



This is where it gets interesting, because numbers bigger than 10,000 are groups in groups of four, expressed with 十, 百 and 千. These are the powers we're going to use in this challenge:

十 10 U+5341



Let's go through an example with 123456789123456789 as the input (other algorithms are possible)

• identify groups of four digits, starting from the right: 12,3456,7891,2345,6789
• convert each group: 十二 三千四百五十六 七千八百九十一 二千三百四十五 六千七百八十九
• insert the appropriate multipliers: 十二京三千四百五十六兆七千八百九十一億二千三百四十五万六千七百八十九

## Notes

• A leading ー MAY be dropped before 千 and 百 and MUST be dropped before 十.

## IO format

The input can be an integer in any reasonable format. You can use a string/sequence of characters or a number type, if your language supports it. 128-bit numbers are not large enough, by the way.

## Testcases

input output
1 一
2 二
3 三
4 四
5 五
6 六
7 七
8 八
9 九
10 十
15 十五
20 二十
31 三十一
100 百
123　百二十一
1000 千
8346 八千三百四十六
10000 一万
50010 五万十
100000 十万
123456789123456789　十二京三千四百五十六兆七千八百九十一億二千三百四十五万六千七百八十九
1234567891234567891234567891234567891234567891234567 一千二百三十四極五千六百七十八載九千百二十三正四千五百六十七澗八千九百十二溝三千四百五十六穣七千八百九十一禾予二千三百四十五垓六千七百八十九京一千二百三十四兆五千六百七十八億九千百二十三万四千五百六十七


Standard code-golf rules apply. The shortest code in bytes wins.

## References

• I assume this is meant to be code-golf? While the tag is technically enough, I think it is better to have a brief inclusion of that in the body of the challenge. – FryAmTheEggman May 29 at 18:44
• @FryAmTheEggman yes it should be codegolf. – corvus_192 May 29 at 19:41
• It'd be helpful if you include the code points for the Unicode characters. – Surculose Sputum May 29 at 21:13
• As someone who is actively learning Japanese, they're called Chinese numerals because they were taken from China's numeral system. Japanese numerals are a whole different, extremely complicated thing. – Ethan Slota May 29 at 21:51
• "A leading ー MAY be dropped before 千 and 百". They MUST be dropped in Sino-Korean numerals, tho. – Dannyu NDos Jun 1 at 4:07
• What about 恒河沙, 阿僧祇, 那由他, 不可思議, and 無量大數? – Dannyu NDos Jun 1 at 4:12
• Mathematica has IntererName[#, "Words", Language -> "Chinese"]&, but, unfortunately, it can't handle numbers this large :(. – my pronoun is monicareinstate Jun 2 at 11:55
• Can we take input in base 10000? (Usually done when doing big integer multiplication with int32 so seems somehow reasonable) – l4m2 Jun 19 at 4:26

# The smallest positive integer that cannot be printed in fewer than %NUMBER% bytes of %LANGUAGE% code-challenge

All numbers mentioned below are positive integers. All programs mentioned below output exactly 1 number (including functions that return it).

For every number, there must be at least one program in your language that outputs it. Besides, the problem of determining what number the program outputs must be undecidable without making the assumption that the program halts.

The challenge itself is to choose a number $$\N\$$ and find the smallest number $$\M\$$ that cannot be output by a program shorter than $$\N\$$ ordinary units of measurement used for your language (usually bytes). You have to prove your solution correct. A strong mathematical proof is not necessary, but it should be reasonably convincing for somebody knowledgeable in your programming language.

The answer with the largest $$\M\$$ wins.

# Sandbox stuff

• In this challenge, non-golfing languages seem to have a serious advantage. I think scoring by $$\M\$$ instead of $$\N\$$ is better at reducing the advantage of Lenguage-like languages to manageable levels and preventing ties; is that correct?
• Is the tag appropriate?
• Title suggestions?
• I feel like I misunderstand. Let's say print M (where M is a normal base 10 integer) is the only valid way to output integers in my language. I take $N=7$, then $M=1$. What's to stop me repeatedly increasing $N$ by 1 and adding a zero on to $M$ each time? – Dingus May 28 at 2:23
• @Dingus I used to have a complicated rule to prevent exactly this; I'll try to think of a simpler one. – my pronoun is monicareinstate May 28 at 2:35
• I'm worried that the proof will just be an exhaustive search for most language, as $M$ has to be the smallest number. Alternatively, we could make $M$ a lower bound of the smallest value, and score a solution based on both $M$ and $N$. Another way is to flip this challenge to find the largest printable number in $N$ bytes, but that has already been done here and here. – Surculose Sputum May 29 at 15:18
• @Dingus I think you will have to stop when you can't prove whether whatever precedes print M halts or doesn't halt. I still think this is too cheap a way to get a high-scoring answer, but I am not sure how to formalize things better. – my pronoun is monicareinstate Jun 2 at 16:01
• @mypronounismonicareinstate I think my question is probably not relevant. I overlooked a critical condition - 'the problem of determining what number the program outputs must be undecidable without making the assumption that the program halts'. – Dingus Jun 4 at 0:18
• I'm worried that some ridiculously large numbers will show up here. Also, as $N$ gets too large, maybe we will encounter problems like $M$ cannot be calculated assuming axioms of ZFC, what will happen then? – Trebor Jun 18 at 7:29
• @Trebor As far as I understand, each program either does output a number within finite time or doesn't output a number within finite time. If the program outputs a number, its result is known, and if it doesn't, the program is not valid because it doesn't output a number in finite time. Can you think of any particular way to obtain a ridiculously large number? – my pronoun is monicareinstate Jun 18 at 10:03
• A simple example is a program that enumerates all the valid proofs in ZFC and outputs the Godel encoding of the first proof it encounters of $A \wedge \neg A$. Since ZFC cannot prove its own consistency, it is not decidable in ZFC whether this program terminates. Worse still, if the program do terminate, ZFC cannot compute the return value either, because it is now inconsistent, rendering its deductions unreliable. – Trebor Jun 18 at 11:00
• @Trebor Halting and printing a single number is completely binary. Are you sure you are reading the challenge correctly? I'm asking not for the largest number that can be printed, but for the smallest number that can't be printed. – my pronoun is monicareinstate Jun 18 at 11:27
• @mypronounismonicareinstate Yes, that's why I'm "worried" instead of "sure". Also, these problems will not show up if we keep it small... – Trebor Jun 19 at 0:42
• Duplicate? – xnor Apr 30 at 4:04
• @xnor it's more closely related, as this has the additional source restriction that programs must be a magic square. Also, diagonals don't matter. – Lyxal Apr 30 at 4:21
• @dingledooper here's another example of when source code was required to be a magic square. I think your current scoring method is fine. – Lyxal Apr 30 at 4:23
• Ah, my mistake. I'd suggest using saying other than Magic Square in the title given that the differences are substantial. – xnor Apr 30 at 4:48
• @xnor Ok, I'll think of a better title! – dingledooper Apr 30 at 4:58
• Can I use custom SBCS for the codepoints? Also, I don't see any reason to ban null bytes (and banning it will be banning a random feature in a golfing language). – Bubbler May 8 at 5:43
• @Bubbler Sure, I've edited the question. – dingledooper May 8 at 6:03

## Divide into 2 isosceles triangles code-golfintegergeometry

Given the measures of two of the interior angles of a triangle (x and y; the other angle can be easily calculated with 180 - x - y), draw a line segment that cuts this triangle into two isosceles triangles. You need to output the angle measures of both of your triangles.

However, because the base angles are the same, you only need to output the list [apex angle, base angle] of the divided triangles for both of the isosceles triangles. You can output the divided triangles in any order.

## An example

Say your input is 100, 60.

Let's take a look at the complete triangle first. The triangle looks approximately like this.

100

60            20

Now we try to divide one of the angles such that two divided triangles are both isosceles triangles.

100

(40,20)           20

Now our bottom triangle is an isosceles triangle, since both of the base angles
of the bottom triangle are 20. The angle measures of the bottom triangle
looks approximately like this.

140
20             20

Now, is the top triangle an isosceles triangle?

100
40
40

It is an isosceles triangle, because two of the angle measures are 40.

Therefore, for [100, 60], you need to output [[100, 40], [140, 20]].



## Example cases

[20, 40] -> [[140, 20], [120, 40]]
[45, 45] -> [[90, 45], [90, 45]]
[36, 72] -> [[72, 36], [36, 72]]
[108, 36] -> [[108, 36], [36, 72]]


# Complete the landscape

Carcassonne is a tile-based game, where the objective is to construct Roads, Cities and Monasteries, in order to score points. The game works by players taking turns to draw and place tiles to construct a landscape, then claiming roads, cities and monasteries. An example landscape is:

There are $$\19\$$ distinct tiles (ignoring rotations), each of which contains at least one feature (Road, City or Monastery):

Also, notice that the landscape must be consistent. This means that roads must connect to other roads, city edges must connect to other city edges and fields must connect to fields. Therefore, these tiles are inconsistent:

To avoid this challenge being about image processing, we can translate each tile into a list containing $$\5\$$ values, according to this legend:

[North edge, East edge, South edge, West Edge, # of cities]

0: Field
2: City


For instance, this tile can be described as [2, 0, 1, 1, 1]. Using this legend, we can describe each tile uniquely, and it's rotations are rotations of the first four elements. The entire grid can be described as a rectangular matrix, with a $$\20^\text{th}\$$ distinct value for an empty square. Translating the first landscape into this format, we get:

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


using [] to represent an empty square. The complete list of tiles (ignoring rotations) in the same grid as the second image is

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


Your task is to take in a rectangular matrix where every element save one is one of the 19 tiles given above. This landscape will be consistent, as defined above. You should take in this input and output the array that would represent the tile(s) which would be able to fill the single empty space in the input matrix, keeping the landscape consistent.

# King+queen vs king checkmate code-golfchess

You are given a chess position, represented either in FEN or as a two-dimensional diagram like this (the example test cases will be using the latter format):

...k....
........
...K....
.....Q..
........
........
........
........


In the examples, K represents the white king, Q represents the white queen, k represents the black king and . represents blank space. You may choose different consistent values instead of these characters. You may also input the diagram as a list of lists or in any other way that is allowed by default for two-dimensional arrays.

It is white's move. The position will always be reachable from the starting position by a sequence of valid moves.

You have to find the minimum number of moves White must do to checkmate Black, assuming perfect play by Black.

# Test cases

Incomplete: too many test cases for 1 and no test cases for >1.

...k....
........
...K....
...Q....
........
........
........
........


Output: 1

k.......
........
..K.....
........
........
........
........
.Q......


Output: 1

k.......
..KQ....
........
........
........
........
........
........


Output: 1

• I know it would be a lot different, but have you considered the more general question that allows any (valid) disposition of the three pieces? Then the task would be to find the minimum number of moves to checkmate... Isn't it a bit "tautological" to input a position of which I already know it only takes one move to checkmate? -I most probably know also what this move is- – Domenico Modica Jun 8 at 16:02
• Moreover if it happens to be only 1 move from checkmate (or also, if you want, if the moves can be all determined), with this broader task you could totally ask what this (these) move is (are). – Domenico Modica Jun 8 at 16:11
• I think asking for the optimal depth to mate in White moves is a better question (far less simple than this, but still much less complicated than a proper chess engine); I'll change the proposal later; it's late here. – my pronoun is monicareinstate Jun 8 at 16:30

Every TeX user has been warned many times that their hboxes are terribly underfull or overfull. So much badness! This challenge is to rate how badly underfull or overfull a line of text is for a simplified line wrapper.

You're given a space-separated string or list of words. Output the minimal badness achievable for the first line.

The text needs to be wrapped on a line that's 10 characters wide, but it can only be split on spaces, no in the middle of words. Any letter that spills beyond the width counts for 1000 overfull badness each, and each leftover empty position at the end of the line counts for 1000 underfull badness.

Example

For input "Overfull hbox", we can keep the word "hbox" in the first line for 3000 overfull badness, or wrap it to the second line for 2000 underfull badness which is smaller, so the output is 2000.

0123456789

Overfull hbox
^^^
Overfull
hbox    ^^


Details

The input is a space-separated string or a list of words made of letters a-zA-Z. It won't have any words more than 10 letters long, or be more than 20 characters in total. It won't be empty or have any zero-length words.

Test cases

TODO

Sandbox: Is it OK to have a multiplier of 1000 for theme? Should the underfull and overfull badness penalties be different, like 1000 vs 2000?

• In my opinion, this might be a bit too simple for the big badness theme to be worth it. I feel like most golfing languages might spend nearly half their code multiplying by 1000 (throwing it together in Pyth, I got 1/4 used for multiplying). If it was say, the badness of each of the lines it might feel better. I don't feel terribly strongly about this though. – FryAmTheEggman Jun 9 at 20:52
• @FryAmTheEggman That for the feedback. I'm now thinking the challenge is too simple overall, multiplier or not. What would you think of something like words being able to be broken at certain places in the middle, either explicitly marked or dervied from some property of the letters? – xnor Jun 9 at 21:14
• I think some level of TeX uses hyphens to indicate possible word breaks, but they don't count for the length of words if unused. Adding that may help, while also being on theme? – FryAmTheEggman Jun 9 at 21:17

## Lucky dice rolls

In pen and paper roleplaying games dice are used for various chance calculations. The usual way to describe a roll is $$\n\textbf{d}k\$$ where $$\n\$$ is the number of dice and $$\k\$$ is the number of faces on a die. For example $$\3d6\$$ means that you need to roll the classical 6-sided die 3 times (or roll 3 dice at the same time). Both $$\n\$$ and $$\k\$$ are positive integers.

Usually the values are then summed and they are used for various game mechanics like chance to hit something or damage calculations.

A lucky roll will mean that you have Fortuna's favor on your side (or against you). Luckiness is an integer number that increases (or decreases) the sum in the following way. The roll is modified to $$\{(n+|luck|)}\textbf{d}{k}\$$ and the sum will be the $$\n\$$ best (or worst) values. Each die is fair, so they will have the same probability for the outcome of the possible values.

The $$\luck\$$ can be a negative number, in this case you need to get the $$\n\$$ worst values for the sum.

### Input

The integer values for $$\n,k,luck\$$ in any way.

### Output

The expected value for the sum of the (un)lucky roll. The expected value is $$\\sum{x_{i} p_{i}}\$$ where $$\x_{i}\$$ is the possible outcome of the sum and $$\p_{i}\$$ is the probability for $$\x_{i}\$$ occuring, and $$\i\$$ indexes all possible outcomes.

### Examples

n,k,luck    expected value
1,6,0       3.5
2,6,0       7
2,6,-1      5.541666666666667
2,6,1       8.458333333333334
2,10,-1     8.525
2,10,1      13.475


### Scoring

Shortest code in bytes wins.

Good luck! ;)

• Probably worth including a definition of expected value. To what precision should the output be determined? – Dingus Jun 10 at 12:50
• @Dingus Is it now a bit more understandable? – Gábor Fekete Jun 10 at 13:29
• Yes, that's good, though I'd suggest tweaking the wording a bit: 'The expected value is $\sum x_ip_i$ where $x_i$ is a possible value for the sum, $p_i$ is the probability of that sum occurring, and $i$ indexes all possible outcomes.' Perhaps I should rephrase my question about precision - what numeric formats are acceptable for output? Floats are obviously allowed, but do you require a certain number of decimal places? Is it acceptable to output rationals (for languages that support this)? What about 2 integers representing numerator and denominator, respectively? – Dingus Jun 11 at 12:13
• hmm, that's a valid point, but I don't know which one it should be. – Gábor Fekete Jun 11 at 12:19

# Compute the factorial, on both sides of 0

Why, why, why do factorials stop at zero? (Yes there are actual reasons). Make a factorial function (or full program) that doesn't stop at zero!

Your code-golfed program should, given an non-zero integer n (can be positive or negative, the rule still applies), find the product of the range n to -n excluding 0.

Graph that at least works for positive numbers

### Sample IO

 Input          | Output
----------------|------------
0               | 1 (product of 0 and -0 without 0 / empty product)
2               | 4 (2*1*-1*-2)
3               | -36 (3*2*1*-1*-2*-3)
4               | 576 (4*3*2*1*-1*-2*-3*-4)
-4              | 576


Probably not a duplicate, but it might not be that much of a challenge.

• Would the input always be positive? Is n=0 a possible input? – Bubbler Jun 11 at 23:02
• @Bubbler For now I'll say 0 is undefined, might change it later before posting if I have a good idea. – Wezl Jun 12 at 13:53
• As it is, isn't this always the factorial of the absolute value of the input squared, then made negative if the input is odd? - except in the edge case for zero? The sign of the input doesn't really appear to matter, which is an odd feeling. – FryAmTheEggman Jun 12 at 16:24
• @FryAmTheEggman Yes, see this graph of the values. Is that a bad thing? Do you have a better suggestion? – Wezl Jun 12 at 20:44
• "downvotes mean nothing but rudeness" - I downvoted this because I do not think "compute $|n|!^2 \cdot (-1)^n$" is a good challenge. I can't see how disagreement is rude. The requirements here seem completely arbitrary to me. This will result in the exact same approaches as were used in the factorial challenge. – my pronoun is monicareinstate Jun 14 at 8:27
• I think it is a bad thing in that it becomes dangerously close to a dupe of the factorial problem. I probably wouldn't hammer it immediately, but if most of the responses basically worked for both or many others had the same concern I'd probably close it. I'm not sure of a good way to modify this to be better, so unfortunately I don't have any suggestions at the moment. I will let you know if something occurs to me. – FryAmTheEggman Jun 15 at 20:09
• @FryAmTheEggman I wouldn't consider it a dupe but I wouldn't consider it a good question after all based off of what my pronoun is monicareinstate said. – Wezl Jun 16 at 21:47
• If you consider 0 as a valid input, I suggest that its expected output be 1, which corresponds to the empty product (Wikipedia). – Bubbler Jun 17 at 3:52
• For the interesting-ness, I believe it can be interesting in at least some languages (which IMHO justifies the value of having such a challenge). FWIW, I have two J solutions of equal length, one using the factorial built-in ! and the other not using it. – Bubbler Jun 17 at 3:53
• I'd likewise close this as a duplicate, but I'm known for having much broader standards than the rest of the community about what questions are closeworthy, so make of that what you will. – pppery Jun 18 at 2:38
• I'll just abandon this, but if @Bubbler wants to post it, they can. – Wezl Jun 18 at 21:17

### Iterate diagonally over nxn matrix

Given a matrix of size n, output the matrix into another matrix of size n such that:

• the outputted matrix, when traversed diagonally,will result in the original matrix.

For example, taking this 3x3 matrix, we arrive at our solution:

Which is checked by following the line beginning at 1:

## Specifications:

• The matrix will always be square
• You must output a grid with the same size as you were given (e.g. Not as a triangle)
• Mark the end of each row with a delimiter such as \n or  .

## Examples:

### Example 1

Input:

1 2 3
4 5 6
7 8 9


Output:

1 3 6
2 5 8
4 7 9


We can check the output by iterating over the array diagonally (follow the arrows for steps 1-5), which will give us the original matrix.

  ↗ ↗ ↗
1 ↗ ↗ ↗
2 ↗ ↗ ↗
3  4 5


### Example 2

Input:

a b c d
e f g h
i j k l
m n o p


Output:

a c f j
b e i m
d h l o
g k n p


We can check this by iterating the array in steps 1-7 which outputs the given array.

  ↗ ↗ ↗ ↗
1 ↗ ↗ ↗ ↗
2 ↗ ↗ ↗ ↗
3 ↗ ↗ ↗ ↗
4  5 6 7


Hint:

Looking at the coordinates, we can see a pattern:

(0,0) -> (0, 1) -> (1, 0) -> (0, 2) -> (1, 1) -> (2, 0) -> (1, 2) -> (2, 1) -> (2,2)

• Do the matrices always consist of one character per cell? – Trebor Jun 19 at 0:45
• they don't have to, but that can be a specification. Thoughts? – Peter S Jun 19 at 1:20
• Perhaps the title could be a bit more descriptive, like "put the contents of a matrix into its antidiagonals". Then you could add a definition of the antidiagonals, and then a description of how you traverse the matrix to get the ordering for the antidiagonalization. – Giuseppe Jun 19 at 17:42

Posted.

# Posted.

• It would ease readability if all of the test cases were in a single code block, with empty lines in between. Then you can add the explanations afterward for cases that really need it. – fireflame241 Jun 23 at 17:43
• Is there a limit to the depth of the tree? – fireflame241 Jun 23 at 17:44
• The problem statement involves a bunch of high-level math terms, which can deter some people. If possible, the challenge would be more approachable if you add an alternate definition, e.g. relating isomorphism to permutations (kinda) of the underlying set. For the explanation of the first case, it would be good to rewrite each line using normal infix notation, e.g. (x+y)+z = x+(y+z) and x+(-x) = 0. – fireflame241 Jun 23 at 17:49
• @fireflame241 I hid the technical details. And could you please explain why I should put a limit to the depth? In what ways does that make the challenge better? ;) – Trebor Jun 24 at 1:25
• I was just wondering. A golfer might be able to optimize for a limit depth of 2, but it's more interesting to have an arbitrary rank – fireflame241 Jun 24 at 1:29
• @fireflame241 After some thoughts, it is clear that every theory can be translated to one that has a limit depth of 2 ;) Also every practically interesting case happens at depth 2. So I think I'll add that. – Trebor Jun 24 at 1:53

# Write an expect program

If you're not already familiar, expect is a Tcl extension that makes it easier to script interactions with programs. It allows you to spawn a process, send lines to it, and wait for expected output before continuing.

## Challenge

The aim of this challenge is to write a very simple implementation of expect in as few bytes as possible (code golf). It should parse a script, with commands separated by newlines. Then it should use this script to interact with a program.

Here are the commands for this implementation:

• spawn <cmd>: spawn a process.
• write <line>: write a line into the process' input.
• expect <line>: expect a substring from the process' output. No timeout is necessary, if the line never appears it is OK for the program to hang.
• print <line>: print something to stdout.

You can assume that only one spawn will be found in the script, and that it will appear before any write or expect. If your language of choice doesn't have the ability to spawn processes, you can write a helper program in a different language that can pipe input and output through your main program. How you do this is left up to you.

Example script:

spawn /bin/bash
write whoami
expect root
write uname -a
expect Linux
print i am root on Linux


Output:

this is Linux


or

spawn /bin/bash
write uname -a
expect Windows
print this is Windows


(no output.)

## Restrictions

In order to keep things fresh, the use of the standard expect utility or any libraries that emulate expect functionality (such as pexpect on Python or jest on Node) are not allowed. The idea is that the bulk of the functionality should be written in the program and not handled in a library.

• Will the script always have 4 commands, namely those 4 in that order? – Adám Jun 30 at 3:52
• While prohibiting the standard expect utility is probably unambiguous, prohibiting expect-like libraries could potentially be problematic because there's no objective way to judge if any given feature is expect-like. I could claim that addition is expect-like, and you'd be hard pressed to counter that. – Adám Jun 30 at 3:55
• The script could have more commands. I will update the examples to reflect that change. As far as the library restrictions, I could remove them - I do see where it could lead to being a problem. Perhaps I could make it more unambiguous by mentioning specific libraries (one that comes to mind is python-pexpect.) – nununoisy Jun 30 at 16:10
• Can we make any assumptions about the order of the commands? – Adám Jun 30 at 18:06
• Yes, I forgot to mention that spawn will come before any command that needs the process. It should be updated now. – nununoisy Jun 30 at 20:23
• What should be done if the expect string is not found? – user202729 20 hours ago
• It was mentioned above but for clarity: 'No timeout is necessary, if the line never appears it is OK for the program to hang.' – nununoisy 3 hours ago

# Count faces in ASCII art code-golfascii-art

Here's a 2x2 ASCII art face:

oo
__


Here's a 3x3 ASCII art face:

o o

___


Here's a 4x4 ASCII art face:

o  o

____


Here's something closer to an actual specification.

The bottom of any face must be a contiguous horizontal row of underscores, such that cells to the right and to the left of it do not contain underscores. If the row is considered as the bottom row of an ASCII square, then that square forms a face if and only if its bottom row is all underscores, its upper left and upper right corners are os, and the rest is whitespace.

You may assume all lines in the input to be padded on the right with whitespace to an equal length. Faces cannot be smaller than 2x2.

[todo: more test cases]

o o
oo
_____


Output: 0

# Sandbox stuff

Is it clear what is considered a face and what is not?

# The almost impossible chessboard puzzle code-golfpuzzle-solvererror-correction

## Background

Prisoner 1 walks in, sees a chessboard (8x8) where each square has a coin on top, flipped either to heads or tails. The warden places the key under one of the squares, which prisoner 1 sees. Before prisoner 1 leaves, he must turn over one and only one coin. Prisoner 2 then walks in and is supposed to be able to figure out which squares the key is in just by looking at the arrangement of coins.

The prisoners are granted a reward if prisoner 2 correctly tells the location of the key.

Write two program/functions:

• One for prisoner 1, which outputs the location of the coin to flip given the current board state and the location of the key
• One for prisoner 2, which outputs the location of the key given the board state after prisoner 1 doing the flip.

If both the solutions are function they may share code with an auxiliary function, though the solutions may not share any information.

## Scoring

This is so shortest bytes wins

Heavily inspired by The almost impossible chessboard puzzle and The impossible chessboard puzzle

# Sandbox

• Should I include the tag
• Any more tags I should add
• Is something not clear

Also pretty sure this will require a lot of rewording before it can be asked

New contributor
Mukundan314 is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.
• Can the two solutions share code, for example by having two functions that both call a third auxiliary function? – Zgarb Jul 7 at 9:20
• Yes, the two solutions can share code but they cannot share information. Updated the question to reflect that – Mukundan314 Jul 7 at 9:30
• Can the auxiliary function be one of the programs? Can both of the programs be the same (and only counted once for bytes, having different behavior based on whether a second argument is passed)? – fireflame241 yesterday

# Tents and Trees feasibility code-golfpuzzle-solverdecision-problem

Sequel to Verify Tents and Trees solution.

## Background

Tents and Trees (try here) is a puzzle played on a square (or rectangular) grid, where the objective is to place tents horizontally or vertically adjacent to each of the trees, so that no two tents touch each other in 8 directions (horizontally, vertically, and diagonally) and the number of tents on each row/column matches the given clues.

### Example puzzle and solution

In these examples, trees are T and tents are A.

Puzzle
2 0 2 0 2 1
2 . T . T . .
1 . . . . T .
1 T . T . . .
2 . . . . . T
1 T . . . . .
0 . . . . . .

Solution
2 0 2 0 2 1
2 . T A T A .
1 A . . . T .
1 T . T . A .
2 A . A . . T
1 T . . . . A
0 . . . . . .


## Challenge

Given a grid with some trees, determine whether it is possible to place tents next to each of the trees so that they don't touch each other in 8 directions. Ignore the number clues in this challenge.

You may take the input in any reasonable way to represent a matrix containing two distinct values to represent a tree and an empty space respectively.

You can choose to follow your language's convention of truthy/falsy, or use two distinct values for true/false respectively.

Standard rules apply. The shortest code in bytes wins.

## Test cases

This uses the same notation as the above example; T for trees and . for empty spaces.

### Truthy

. . .
. . .
. . . (empty board)

T .

. T .
. . T

. .
T T
. .

. T .
T . T
. T .

. . .
T T .
. T T
. . .

. T . .
. . . T
T T . .
. . . .

. T . . . .
. . . . . .
. . T . . T
. T . T . .
T . T . . .
. T . . T .


### Falsy

(No space to place a tent)
T

T . T

T . T
. T .

. . . .
. T T T
T . . .

. T .
T T .
. T .

T . T
. . .
. T .

T . . . .
. . T . .
. T . T .
T . T . .
. T . . .

. . . . .
. T . . .
. T T . .
. . T T .
. . . . .


# Create a Boolean Calculator

Our boolean operators are AND, OR, XOR, NAND, NOR, XNOR and, in conjunction with one of those operators, NOT.

Our numbers are 1 and 0.

The challenge is to write a program or function that calculates the results of the input.

## Input

A string, array or other input; containing alternating numbers and operators, e.g. 1 NOR 1 or 1 OR 0 AND 1. It must contain the strings for the operators, and not .+^¬||&& etc. As an exception, NOT must come directly after another operator (e.g. 0 AND NOT 1).. You can't implement NOT by itself, and you won't ever get a chain of multiple NOTs (so 1 AND NOT NOT 0 is an invalid input).

## Output

Return or print a single number (1 or 0), derived using the calculation below. Invalid input can lead to any output you choose, or none.

## Calculation

We're ignoring any precedence rules here - just calculate them in the order they come in (i.e. left-to-right) - as if someone was typing it into a calculator and pressing Enter after each number. NOT is the only one that might cause some difficulties with that logic, as you need to figure out what it's NOT-ing before you can apply the other operator.

## Truth Tables

INPUT   OUTPUT
A   B   AND NAND OR NOR XOR XNOR
0   0    0   1   0   1   0   1
0   1    0   1   1   0   1   0
1   0    0   1   1   0   1   0
1   1    1   0   1   0   0   1

IN OUT
A  NOT A
0    1
1    0


## Examples

• 1 NOR 1 = 0
• 1 NOR NOT 0 = 0 (equivalent to 1 NOR 1)
• 1 NOR NOT 0 AND 1 = 0 (equivalent to 0 (from above) AND 1)
• 1 NOR NOT 0 AND 1 OR 1 = 1 (equivalent to 0 (from above) OR 1)
• 1 NOR NOT 0 AND 1 OR 1 XNOR 1 = 1 (equivalent to 1 (from above) XNOR 1)
• 1 NOR NOT 0 AND 1 OR 1 XNOR 1 NAND 0 = 1 (equivalent to 1 (from above) NAND 1)
• 1 NOR NOT 0 AND 1 OR 1 XNOR 1 NAND 0 XOR NOT 0 = 0 (equivalent to 1 (from above) XNOR NOT 0 = 1 XNOR 1 = 0)

## Scoring

This is code-golf, but with a twist.

Your score is the number of bytes in your code, divided by the number of operators your code implements. Smallest score wins.

For example, if you only implement AND, your score is the number of bytes of your code.

If you implement AND, OR, XOR, NAND, NOR, XNOR, NOT (the full list of operators); then you get to divide the number of bytes by 7.

You must implement at least one operator, and you cannot implement NOT by itself; as it must be preceded by another operator.

• cat, 0 bytes, score 0: implements not because not must be directly after another operator and therefore cannot be in the input. Therefore the output is the input. – my pronoun is monicareinstate Jul 3 at 11:32
• I would argue that you're not implementing NOT there – simonalexander2005 Jul 4 at 12:17
• You might want to clarify that you cannot only implement the NOT operator, you must implement at least one other operator besides NOT. You should also clarify that you must implement at least one operator, otherwise someone may try to divide their score by 0. Otherwise seems like it could be an interesting challenge! – MrSiliconGuy Jul 6 at 0:30
• Thanks, I'll clarify that – simonalexander2005 Jul 6 at 9:15
• Just noticed you didn't specify the tags. I suggest code-challenge logic and probably parsing. Just don't tag this code-golf since it is only for the plain code length scoring. – Bubbler Jul 6 at 10:02
• @Bubbler done, thanks – simonalexander2005 Jul 6 at 14:22
• Instead of saying "calculate them as they come in", just say "evaluate left to right" – qwr yesterday

## Write a compiler/interpreter for ...

Inspired by the lisp challenge here.
It is a series of puzzles.

I don't like to see a simple eval solution, so:

• interpreting the language is fine
• translating the language to a different language is fine.

I think this is specific for each language.

Only the syntax and the basic commands.
Also specific.

Winning criteria should not be code golf.
The goal should be that you can "learn" an other language by looking at the code.

Languages that might be good candidates:

• Lisp
• APL
• J
• Whitespace
• Forth
• This only works for languages which are small and well defined. BF fits those criteria. Whitespace does too. The others may not. Lisp and Forth have so many dialects that you would have to specify exactly which dialect to support; Lisp, Forth, APL and J might have too many built-ins to fit in an answer: there are character limits. – Peter Taylor May 12 '13 at 15:16
• You don't have to provide all the built-ins, but that is why it is here. – Johannes Kuhn May 12 '13 at 15:38
• What defines the "basic commands"? – ASCIIThenANSI Aug 31 '15 at 17:54
• I don't know? Maybe that you can do the basic stuff with it like +,-,print,... – Johannes Kuhn Aug 31 '15 at 18:22
• I suggest a programmer can implement the tiniest subset of those languages in order to be Turing-complete, as these are non-trivial subsets that can theoretically simulate the rest of the language... – user85052 Jun 28 '19 at 4:17
• Which human is learning the programming language by looking at the code? – MilkyWay90 Aug 26 '19 at 3:23

# Find Maximum number of 4+ letter words from Scabble Tiles

The challenge is to find the most words with 4 or more letters you can make with one set of scrabble tiles.

The tile distribution is as follows:

2 Blank Tiles
A 9  N 6    +====+===========+
B 2  O 8    | 01 | K J X Q Z |
C 2  P 2    | 02 | B C M P F |
D 4  Q 1    | 02 | H V W Y * |
E 12 R 6    | 03 | G         |
F 2  S 4    | 04 | L S U D   |
G 3  T 6    | 06 | N R T     |
H 2  U 4    | 08 | O         |
I 9  V 2    | 09 | A I       |
J 1  W 2    | 12 | E         |
K 1  X 1    +====+===========+
L 4  Y 2
M 2  Z 1


Valid words are any words that are 4+ that are available in this file, the official scrabble dictionary.

Tiles cannot be used twice. This means you can only have 1 word with a K, J, X, Q, and/or Z unless you use a blank tile to represent one of these letters.

I'm not sure how I'd do scoring on this. I want shorter code to score better, but I don't want a short piece of code that finds a lot less words to score better than a longer piece that finds many more words.

• Meh. I don't like dependency on external files; are we allowed to load it, or even embed it into the source code? – John Dvorak Dec 17 '13 at 20:00
• as for finding more vs. shorter code, you could demand all words be found – John Dvorak Dec 17 '13 at 20:19
• @JanDvorak Any way to use it. It's a text version of the official scrabble dictionary, it seemed to be the most fitting word list for the task. "All words being found" might be hard, considering there are probably many combinations of words that would deplete all the tiles. It's a maximum of 25 words, (25 words, 4 letters each, 100 tiles), but I don't know if it's possible to use all tiles with just 4 letter words. After so many words, you might not have enough tiles to make an actual word, which means you'd either have to go back or accept that you're not using all the tiles. – Rob Dec 17 '13 at 20:23
• As currently described, this is a no-input task, which means that the answer can be precomputed and then the program only needs to decompress it. Consider rewriting it to take input (either of the word list or of the tiles available). – Peter Taylor Dec 18 '13 at 8:01
• I suggest taking a list of tiles as input, loading the list of words from a predefined file and requiring all combinations / best combination to be found. Of course, if the input is the full list of tiles, the computation is going to take ages. I might allow preprocessing the word list outside the program itself (up to a certain point; a linearithmic growth?) – John Dvorak Dec 18 '13 at 8:32
• I suggest modifying this so that input is a list of tiles, limited to a full rack or less (therefore 4-7 tiles, since our minimum word length is 4). Input should be assumed to be valid based on the standard set of tiles (e.g.: it wont' have something like 3 J's or 4 G's). This would have some practical use for a player in a scrabble game to figure out their next move (though it does not take into account tiles available to them which are already on the board). – Iszi Dec 18 '13 at 21:14
• Alternative mode: Input is a list of tiles, maximum 96 (so that at least 4 are remaining in the set). Output only includes words (minimum 4 letters) which can be created without those tiles. This would be interesting as it provides words that may yet be created (though, again, not taking into account usable tiles on the board) at a given point in the game. – Iszi Dec 18 '13 at 21:15
• Output needs to be decided as either a list of all possible words, or only the highest-scoring word(s). Another enhancement may be to require that the list be sorted descending in order of score (if output is all words), then ascending alphabetically. There's no reason to take each program's output into account for scoring. Since everyone is expected to use the same dictionary, all programs' outputs should be identical (except perhaps in sorting, if that's left out of the spec). So, this should be Code Golf. – Iszi Dec 18 '13 at 21:15
• It's also worth noting that, as currently written, the task could just be to filter the given dictionary down to words which have 4 or more letters. By its very nature, the Scrabble dictionary should already exclude any words that cannot be made with a Scrabble set. – Iszi Dec 18 '13 at 21:18
• @Iszi it's not "what are all the words you can make", it's "what are all the words you can make, where every letter used depletes a tile". There's a max of 25 words if you can use all 100 tiles. – Rob Dec 19 '13 at 16:40
• I think I misunderstood the problem, then. I thought it was "all the words possible using a set of tiles" not "all the words possible, using only one set of tiles". Still, my point about code golf remains. There is an absolute maximum to the number of words (each with 4 or more letters) you can make with a single Scrabble set, and a finite number of permutations which can be used to hit that maximum. Every program written with this goal should end up with the same (or nominally similar) output. – Iszi Dec 19 '13 at 16:56

# Test for Irreducible Complexity (Check for Redundant Characters)

I may need some additional help coming up with the full spec for this competition. As of right now, this is just a concept.

Many interesting questions, such as the "42" question in this sandbox, involve finding the longest program which is not reducible. This means that no set of characters can be removed and still allow the program to function as desired.

The basic idea is that your program will test a Base Program to make sure that it contains no redundant characters. The input will consist of:

• Expected Output

Your program will simply evaluate all possible subsequences of the Base Program and verify that none of them give the Expected Output.

This challenge actually has a utility value to several other challenges. For example, it verifies the results of a "longest non-reducible"-type challenge. In addition, it could make sure that a golfed solution cannot be golfed further.

I assume that the winning criteria will be fastest program, as cycling through all the possibilities takes a long time.

## Problems

A sequence of length N has 2^N subsequences. Even if each evaluation is done very quickly, it might be unfeasible to test any program with more than 20 or so characters in a reasonable amount of time.

• Problem: some subsequences of legitimate answers may be pretty dangerous to the environment. You don't want to eval just everything. – John Dvorak Dec 23 '13 at 16:59
• @JanDvorak Yes that actually is a serious problem. To what extent is it possible to fix that? – PhiNotPi Dec 23 '13 at 17:04
• Forbidding any program with dangerous subsequences? :-) – John Dvorak Dec 23 '13 at 17:05
• A more reasonable (but very difficult) solution would be the requirement to implement a sandbox. – John Dvorak Dec 23 '13 at 17:07
• Even without dangerous behavior, the halting problem will be an issue: it's hard to tell whether a shortened program will terminate at all, especially for every conceivable input. – MvG Jan 7 '14 at 23:49

# Popularity Contest: Implementation of a Hash Table

Create a class in some OOP language for a hash table that supports getting, setting, and removing values. You can't use the built in hash table/dictionary/map implementation. Highest votes in one week wins.

A key is any valid string. A value is any valid string, number, or boolean.

Example functionality:

hash.set("key","value");
hash.get("key"); // returns "value"
hash.set("key", 1234);
hash.get("key"); // returns 1234
hash.set("key2",hash.get("key"));
hash.get("key2"); // returns 1234
hash.delete("key");
hash.get("key"); // returns null/undefined/none/etc. or throws an error
hash.get("key2"); // still returns 1234


Definition of a hash table (from Wikipedia):

In computing, a hash table (also hash map) is a data structure used to implement an associative array, a structure that can map keys to values. A hash table uses a hash function to compute an index into an array of buckets or slots, from which the correct value can be found.

The hash table cannot be simply an array that is searched in linear time. It must be an actual hash table that uses a hash function to map the keys to the value.

• Popularity contest and shortest don't mix. That aside, the spec is too vague. What is a "value"? What assumptions can be made about hashcodes? If the language makes all types nullable, should null be permitted as a key? What should the type be in languages which have co- and contravariance? And for that matter, what qualifies as a "hash table", bearing in mind that people will try to exploit any loophole? – Peter Taylor Jan 2 '14 at 23:16
• @PeterTaylor Thank you for the feedback! Please see my edits, and let me know what you think. Could you meant about co/contravaraince? I looked at the wikipedia article about it but I'm not really sure how that has anything to do with this question. – hkk Jan 2 '14 at 23:37
• I think it's still vulnerable to the loophole of "I have a hashtable with one bucket" (i.e. it's really a list of (key, value) pairs which I traverse in linear time). The thing about variance is to do with static typing of the elements of the map. E.g. in Java Map<String, Integer>'s get method has signature public Integer get(Object); in C#, a Dictionary<string, int>'s Get method has signature public int Get(string). The edited version makes it clear enough that the hashtable isn't expected to be genericised. – Peter Taylor Jan 3 '14 at 0:08

# Wordlist detector

You are to write a program which, given a list of words, constructs a regular expression to match all these words but nothing else. Both your program and the constructed regular expressions are to be as short as possible.

## Input and Output

Input comes on standard input and consists of one line giving n, the total number of words, followed by n lines with one word each. The number of words will be less than 1000, the length of each word less than 30. Words will consist only of lower case ASCII letters, i.e. a-z. You may choose to ignore the first line and use EOF instead to end the list.

Output shall be written to standard output. It consists of a single line, giving a POSIX extended regular expression to match these words and no others. Since input for this regex is not restricted to letters only, elements like . or [^…] won't make too much sense, which limits the language in a natural way. You may choose whether you want to terminate the line with a newline or not. Programs may choose to print multiple lines of output, in which case only the last one will be used for scoring. So you might print intermediate results and continue searching for improvements.

## Test cases

Each submission may be accompanied by one regular expression. When scoring the submissions, I'll use this regular expression to reconstruct a word list from it. The code to do this reconstruction can be found at the end of this post. The reconstructed word list must fit the input specification above in terms of word count and length. It would be nice if your own program would be able to regenerate that regular expression from the word list, but that is not a strict requirement. But please don't paste bogus programs just to submit a challenging regular expression, though.

These test cases will be collected and fed to all programs for scoring.

## Scoring

The final score of each program will be the program size plus the size of all its generated regular expressions for the inputs collected from submitted answers, including the example from this question. So short code which produces too long results might get beaten by longer code which generates shorter expressions.

Does this still qualify as ?

Submissions which generate an incorrect regular expression for one of the test cases will be disqualified, as will those which don't terminate in the allotted time. You can use the input reconstruction program below to check whether a produced regular expression does encode the correct word list.

## Requirements

All submissions are welcome, but in order to include your submission in the tournament, it must be executable with reasonable effort on my Linux machine. It shouldn't depend on any exotic libraries, or any specialized ones which take too much work away from your own program. It must operate in reasonable time, say no more than five minutes per input. Your output must be reproducible, so if you use randomization at some point, please seed the randomizer, and please don't terminate an improove loop by a timer measuring execution time or some such.

## Tournament times

I'll run the first major tournament two weeks after posting this question. I'll include a table of the results in this question. I'll try to run tournaments repeatedly as late submissions arrive, but I'll not promise any regular schedule.

## Example

An very simple example application would be in Python 3 (53 chars):

print('|'.join(input() for i in range(int(input()))))


And here is a test case which could be posted along with the program, although this program obviously doesn't generate exactly this concise output:

bann?ana|ap(fel|ple)|s[ou]n|[hs](a|ou)nd


The expansion of that expression could be turned into the following example input, which need not be posted as part of an answer since it can be deduced from the regular expression:

10
banana
bannana
apfel
apple
son
sun
hand
hound
sand
sound


## Regex expander program

And here is a program to turn regular expressions into word lists, again written in Python 3.

#!/bin/env python3
concat = set(('',))
altin = set(('',))
altout = set()
prev = None
stack = []
regex = iter(input())
for ch in regex:
if ch == '(':
stack.append((concat, altin, altout))
altin = concat
altout = set()
prev = None
elif ch == ')':
concat.update(altout)
prev, altin, altout = stack.pop()
elif ch == '|':
altout.update(concat)
concat = altin
elif ch == '[':
ch = regex.__next__()
cls = []
while ch != ']':
if ch == '-':
crange = range(ord(cls[-1]), ord(regex.__next__()) + 1)
cls.extend(map(chr, crange))
else:
cls.append(ch)
ch = regex.__next__()
prev = concat
concat = set(w + c for w in prev for c in cls)
elif ch == '?':
concat.update(prev)
prev = None
elif ch >= 'a' and ch <= 'z':
prev = concat
concat = set(w + ch for w in prev)
else:
raise Exception("Illegal input")
if stack:
raise Exception("Unclosed group")
concat.update(altout)
words = sorted(concat)
print(len(words))
print('\n'.join(words))


This is restricted to the part of regular expression syntax which I expect for this answer. If you have good reason to use something I did not consider, feel free to do so although I will likely have to update this code to cope with it. If you find a bug, please let me know.

• This is just Meta regex golf under the constraint that the two lists between them cover all possible words. Given that some people are tackling that existing question on that basis, this would qualify for closing as a duplicate. – Peter Taylor Jan 8 '14 at 8:45

## Code-Golf: Write a number as an expression that's as short as possible

The goal of this code-golf is to create a program that takes a number as input (using STDIN, command line arguments, or prompting for input), and outputs that number, but written as an expression that's as short as possible. So, 10000 should become 10^4. If there is no way to write an expression that's shorter than the number, then output just the number.

### Other rules

1. No network access.
2. You're not allowed to execute an external program.
3. Only use the operators +, -, *, / and ^ (that's raising power, not XOR).
4. Order of operations must be taken in account. Use parentheses if necessary.
5. This is a code golf, so the code with the smallest amount of characters wins.
6. The input will always be smaller than 2^32.

### Test cases

500000000   -->    5*10^8     or    10^9/2
999999      -->    10^6-1
10          -->    10
4294967295  -->    2^32-1
16384       -->    2^14


## Rhymalator

(at the point, it's just something that came to me before i wake up, so it may need some adjusting, and i'd like some feedback as to if this could be fun)

The code challenge is to write a program that takes as input a calculation in Reverse Polish Notation and outputs the result. It must at least implement + - * /. It So far so easy, but to make it fun and "artistic", the following restriction applies:

• The source code must rhyme when read. Example in PHP

$iterator = str_split($a);
foreach ($iterator as$key=>$value){ if ($key > 3){
++\$virtue;
}
}


(the rhyme is on value-virtue)

• Lines whitout readable characters count as whitespace (the two lines with } in the example)

• How does that example rhyme...? – Doorknob Jan 25 '14 at 12:54
• @DoorknobofSnow well, i'm not really a poet, that's why i propose it as a challenge for others :p. if you have a better example i'll replace it – Einacio Jan 27 '14 at 15:58