title: Generate a Davenport-Schinzel Sequence

text:
# Question
Title: Generate a Davenport-Schinzel Sequence
## Background

A *Davenport-Schinzel sequence* has two positive integer parameters `d` and `n`. We will denote the set of all Davenport-Schinzel sequences for given parameters by `DS(d,n)`.

Consider all sequences of the natural numbers `1` to `n`, inclusive, which satisfy:

* No two consecutive numbers in the sequence are identical.
* There is no subsequence (not necessarily consecutive) of length greater than `d`, which alternates between two different numbers.

Let `L` denote the maximum length of such a sequence (given `d` and `n`). Then, `DS(d,n)` is the set of all such sequences with length `L`.

Some examples might help. Let `d = 4`, `n = 3`. The longest possible sequences with these constraints have `L = 8`. So the following is a member of `DS(4,3)`:

```
[1, 2, 1, 3, 1, 3, 2, 3]

```

There are no consecutive identical numbers and there are alternating subsequences of length `4`, but not longer ones:

```
 1  2  1           2
 1  2        1     2
 1        3  1  3
 1        3  1        3
    2     3        2  3
    2           3  2  3
       1  3  1  3
       1  3  1        3

```

The following examples are *not* in `DS(4,3)`:

```
[1, 2, 2, 3, 1, 3, 2, 3]  # Two consecutive 2's.
[1, 2, 1, 3, 1, 3, 2, 1]  # Contains alternating subsequences of length 5.
[1, 2, 1, 3, 1, 3, 2]     # Longer valid sequences for d = 4, n = 3 exist.

```

For further information see MathWorld and OEIS and the references they list.

## The Challenge

Given two positive integers, `n` and `d`, generate any Davenport-Schinzel sequence in `DS(d,n)`. Note that these are not generally unique, so output any single valid result.

You may write a program or function, taking input via STDIN (or closest alternative), command-line argument or function argument, and returning the result from the function or printing it to STDOUT (or closest alternative).

You may use any convenient, unambiguous string or list format for output.

This is code golf, so the shortest submission (in bytes) wins.

## Sequence Lengths

Since the sequences are not unique, there is not much use for individual examples in this challenge. However, the two general validity problems are fairly easy to check for any output, so the main question is just whether the sequence has the right length (or there's a longer valid sequence). Therefore, here is a list of the known1 `L` for given `d` and `n`:

```
 \
 d\n 1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20
   \-----------------------------------------------------------
 1 | 1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1
 2 | 1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20
 3 | 1  3  5  7  9 11 13 15 17 19 21 23 25 27 29 31 33 35 37 39
 4 | 1  4  8 12 17 22 27 32 37 42 47 53 58 64 69 75 81 86 92 98
 5 | 1  5 10 16 22 29 ...
 6 | 1  6 14 23 34 ...
 7 | 1  7 16 28 41 ...
 8 | 1  8 20 35 53 ...
 9 | 1  9 22 40 61 ...
10 | 1 10 26 47 73 ...

```

You must not hardcode any information from this table into your submission.

1 This table is from 1994, so there may have been more progress since then, but I doubt that any submission will be able to handle even the larger entries in this table in a reasonable amount of time.

# Answer
# Python 2: 172

```
from itertools import*
d,n=input();S=[[1]]
for s in S:
 for v in range(1,n+1):
  if(v!=s[-1])*all(w[2:]!=w[:-2]for w in combinations(s+[v],d+1)):S.append(s+[v])
print S[-1]

```

Input is simply in the format `4, 3`.

I iteratively create all sequences, which start with `1` and satisfy the two properties, and store them in `S`. Since I create them in sorted order (sorted by length \[and by values\]), the last entry has to be a Davenport-Schinzel-sequence. Uses the nice fact, that you can iterate over a list while appending to it.
> 2 votes

---
Tags: code-golf, combinatorics, sequence, subsequence
---


# Question
Title: Noel Constant's idiotically simple investment system
> Noel Constant did it without genius and without spies.
>
> His system was so idiotically simple that some people can't understand it, no matter how often is is explained. The people who can't understand it are people who have to believe, for their own peace of mind, that tremendous wealth can be produced only by thremendous cleverness.
>
> This was Noel Constant's system:
>
> He took the Gideon Bible that was in his room, and he started with the first sentence in Genesis.
>
> The first sentence in Genesis, as some people may know, is: "In the beginning God created the heaven and the earth." Noel Constant wrote the sentence in capital letters, put periods between the letters, divided the letters into pairs, rendering the sentence as follows: "I.N., T.H., E.B., E.G., I.N. N.I., N.G., G.O., D.C., R.E., A.T., E.D., T.H., E.H., E.A., V.E., N.A., N.D., T.H., E.E., A.R., T.H."
>
> And then he looked for corporations with those initials, and bought shares in them. His rule at the beginning was that he would own shares in only one corporation at a time, would invest his whole nest-egg in it, and would sell the instant the value of his shares had doubled.

–Kurt Vonnegut, *Sirens of Titan*

The investor Noel Constant is getting tired of using his system manually. He needs the power of computers to pick the companies to invest in.

Noel Constant is willing to learn how to execute a command line script or a function in the language of your choice. He will provide a single string of input. He won't bother removing any whitespace, punctuation, or change case for the input string. He doesn't like that kind of work.

In return he expects to see a list of companies he can invest in, produced according to his idiotically simple system. He wants to see each company on its own line with the initials in brackets. If there isn't a company with the initials needed he wants to see three dots (`...`).

```
International Nitrate (IN)
Throwbridge Helicopter (TH)
Electra Bakeries (EB)
Eternity Granite (EG)
... (IN)

```

His company, Magnum Opus, provided a list of company names and their initials for you: https://gist.github.com/britishtea/2f57710a114cfd79616d.

As you may have guessed, Noel Constant doesn't like reading, so he'll want the shortest program or function possible.

### EDIT

To clarify, the input to the function or program is *string* (*with* punctuation and whitespace, case unaltered). An example of such a string is "In the beginning God created the heaven and the earth." The list of company names and initials *is not* an input source, it should be read some other way (from disk for example).

The output is a list in the above format. I forgot to mention in the original challenge that the order the company names appear in shouldn't be altered, i.e. if you read the initials in the output from top to bottom it renders the original input (stripped of punctuation and whitespace).

**This is no longer a requirement**, but if your function or program satisfies this condition, there is a `0.9` bonus (`# characters * 0.9`) in it for you.

# Answer
> 4 votes
**Unix tools, 111 * 0.9**

(Not counting downloading and parsing the Bible)

```
$ curl -s https://www.gutenberg.org/cache/epub/10/pg10.txt|grep '^[0-9]:'|cut -d' ' -f2-|sed 's/[^a-z]//gi'|tr -d \\n|fold -w2|xargs -n1 sh -c 'grep -i ^$0 symbols.txt'|sed -r 's/(..) (.*)/\2 \(\1\)/'
Zylog Systems Ltd (IN)
Zynga Inc - Cl A (TH)
Zwahlen & Mayr Sa-br (EB)
Surpapelcorp Sa (EG)
Zylog Systems Ltd (IN)
Nisource Inc. (NI)
Novagold Resources Inc. (NG)
Zealand Pharma A/s (DC)
Everest Re Group, Ltd. (RE)
Atlantic Power Corporation (AT)
^C

```

I am not a professional investor but I think that the more times a company is mentioned in the Bible the more successful it will be, so I would invest in these:

```
  10027 th - Zynga Inc - Cl A
   9026 he - Hawaiian Electric Industries, Inc.
   4748 nd - *
   3681 an - Autonation, Inc.
   3150 ha - Hawaiian Holdings, Inc.
   3109 er - *
   2925 re - Everest Re Group, Ltd.
   2829 in - Zylog Systems Ltd
   2665 nt - *
   2519 es - *

```

(Future founders, consider creating a company with stock symbols I marked with `*`, they are not yet taken)

# Answer
> 1 votes
# Mathematica, 186

```
Grid[{If[Length[a=FinancialData[#,"Lookup"]]>0,FinancialData[a[[1]],"Company"],"..."],#}&/@StringJoin/@Partition[Select[Characters[ToUpperCase@#],IntersectingQ[{#},CharacterRange["A","Z"]]&],2]]&

```

The output looks like this:

This actually doesn't quite work, but I think it's pretty neat that Mathematica can do this. For some reason, though, it has trouble finding its own stocks. For example, it finds "NYSE:IN" but then says it's not a known entity:

Still, that's about as far as I think I'll go with it, unless someone knows why it's confused about the NYSE stocks. Feel free to expand or golf.

# Answer
> 1 votes
# Python 3, 174 * 0.9 = 156.6 bytes

Rereading the rules, the company names can be in a file. This works with a file named `w` (No file extension) in the same format as the github.gist in the question. Takes input via stdin and outputs in the format `company name (SC)` or `... (SC)` where `SC` is the stock code.

```
a={l[:2]:l[3:-1]for l in open("w").readlines()}
s="".join(c.upper()for c in input()if c.isalpha())
for i in(s[c:c+2]for c in range(0,len(s),2)):print(a.get(i,"..."),"(%s)"%i)

```

### Old version, ~~248~~ ~~241~~ 238 * 0.9 = 214.2 bytes

This is the same as above, except it gets the stock codes from the internet.

```
from urllib.request import*
a={l[:2]:l[3:]for l in urlopen("http://goo.gl/lZVoIE").read().decode().split("\n")}
s="".join(c.upper()for c in input()if c.isalpha())
for i in(s[c:c+2]for c in range(0,len(s),2)):print(a.get(i,"..."),"(%s)"%i)

```

The `goo.gl` link is the link to the gist shortened.

---
Tags: code-golf
---


title: Python 3 - Tried Golfing My Assignment

text:
# Question
Title: Python 3 - Tried Golfing My Assignment
**Note:** This isn't as much a golfing challenge; it is more so asking for golfing suggestions.

Recently I had a Python assignment for my web development class, in order to check whether we could code. Since I already feel comfortable in Python, I decided to try and golf it, and I was wondering if people could point out things that I missed.

I already know that there are extra spaces in some places, but I'm more interested in conceptual things, like using `while r:` when r is a variable, and then waiting for it to "run out"!

The assignment

```
import random
from collections import Counter
s=l=''
c=['yellow','blue','white','green','Black', 'purple', 'silver', 'cyan', 'magenta', 'red']
n=[10,15,1,10,6,15,10,25,1,12,5,10,4,6,5,12,0,10,1,1]
o=i=0
for y in c:l+=y[0]*(random.randint(n[o],n[o+1]));o+=2
l=list(l)
print("Welcome to the CIMS Gumball Machine Simulator\nYou are starting with the following gumballs:")
for b in c:print(str(l.count(b[0])) + " "+b);random.shuffle(l)
print("Here are your random purchases:")
while 'r' in l:
    random.shuffle(l); r=l.pop(); s+=r
    for j in c:
        if j[0] == r:print(j.capitalize())
print("You purchased %i gumballs, for a total of $%.2f \nMost common gumball(s):" % (len(s),len(s)*25/100))
a=Counter(s).most_common()
m=[x[1] for x in a]
while m[0] == m[i]:
    for j in c:
        if j[0] == a[i][0]:print(j.capitalize(), end=" ")
if(i<(len(m)-1)):i+=1
else:break

```

Also: I'm sorry if this isn't an appropriate question for the code golf page, since it is not a challenge and will remove it on request.

# Answer
> 20 votes
Here's a whole bunch of micro-optimisations you can do:

**Use `.split()` to create a long list (-17 bytes):**

```
c=['yellow','blue','white','green','Black', 'purple', 'silver', 'cyan', 'magenta', 'red']
c='yellow blue white green Black purple silver cyan magenta red'.split()

```

**Remove extraneous brackets (-2 bytes):**

```
l+=y[0]*(random.randint(n[o],n[o+1]))
l+=y[0]*random.randint(n[o],n[o+1])

```

**Use splat (-2 bytes):**

```
random.randint(n[o],n[o+1])
random.randint(*n[o:o+2])

```

**Use extended iterable unpacking to turn something into a list (-4 bytes):**

```
l=list(l)
*l,=l

```

**Import all the things (-15 bytes):**

```
import random;random.randint;random.shuffle;random.shuffle
from random import*;randint;shuffle;shuffle

```

**Use other functions that can do the same job here (-5 * 2 = -10 bytes):**

```
j.capitalize()
j.title()

```

**`print` separates by space by default (-11 bytes):**

```
print(str(l.count(b[0])) + " "+b)
print(l.count(b[0]),b)

```

**More unpacking (-3 bytes):**

```
r=l.pop()
*l,r=l

```

**Abuse side-effects (-1 byte, plus indents):**

```
if j[0]==r:print(j.capitalize())
r!=j[0]or print(j.capitalize())

```

**Anything reused and over 5 chars might be worth saving as a variable (-1 byte):**

```
len(s);len(s)
L=len(s);L;L

```

**Simplify fractions (-5 bytes):**

```
len(s)*25/100
len(s)/4

```

**Unary abuse (-4 bytes):**

```
if(i<(len(m)-1)):i+=1
if~-len(m)>i:i+=1

```

Or the biggest one of all...

## Look at your algorithm, and see if it needs changing altogether

```
from random import*
*s,P,S=print,shuffle
P("Welcome to the CIMS Gumball Machine Simulator\nYou are starting with the following gumballs:")
*l,c,C='yellow blue white green Black purple silver cyan magenta red'.split(),s.count
for x,y,z in zip(c,[10,1,6,10,1,5,4,5,0,1],[15,10,15,25,12,10,6,12,10,1]):n=randint(y,z);l+=[x]*n;P(n,x)
S(l)
P("Here are your random purchases:")
while'red'in l:S(l);*l,r=l;s+=r,;P(r.title())
L=len(s)
P("You purchased %i gumballs, for a total of $%.2f\nMost common gumball(s):"%(L,L/4))
for x in c:C(x)!=max(map(C,c))or P(x.title())

```

(If you ever find yourself importing `Counter` in a code-golf, you're probably doing something very wrong...)

---
Tags: code-golf, tips, python
---


title: A Mnemonic for Remembering 23940

text:
# Question
Title: A Mnemonic for Remembering 23940
The major system is a mnemonic device for converting numbers into words so they can be memorized more easily.

It is based on how words sound phonetically, but to keep things simple for the challenge we'll only be concerned with how words are spelled. This means there will be some incorrect conversions, but that's alright.

> To convert a number into a word using our simplified major system:
>
> * Replace each `0` with `s` or `z`. (Some could be `s` and some could be `z`. Same goes below.)
> * Replace each `1` with `t` or `d` or `th`.
> * Replace each `2` with `n`.
> * Replace each `3` with `m`.
> * Replace each `4` with `r`.
> * Replace each `5` with `l`.
> * Replace each `6` with `j` or `sh` or `ch`.
> * Replace each `7` with `k` or `c` or `g` or `q`.
> * Replace each `8` with `f` or `v`.
> * Replace each `9` with `p` or `b`.
> * Add the letters `aehiouwxy` anywhere in any amounts to make a real English word, *if possible*.
> **The only exception is that `h` may not be inserted after an `s` or `c`.**
>
> The number may actually be any string of the digits 0-9 (no decimals or commas or signs).
> The word can only contain the lowercase letters a-z.

## Examples

The number `32` must be converted as `?m?n?`, where `?` represents any finite string made from the letters `aehiouwxy` (a string from the free monoid if you prefer). There are many ways this could be made into a real English word: `mane`, `moon`, `yeoman`, etc.

The number `05` could be converted as `?s?l?` or `?z?l?`. Some possibilities are `easily`, `hassle`, and `hazel`. The word `shawl` is not allowed because `h` may not be placed after `s`; it would be incorrectly read as `65`.

# Challenge

Write a program or function that takes in a string of the digits 0-9 and finds all the words that it could be converted into using the simplified major system mnemonic.

Your program has access to a word list text file that defines what all the "real" English words are. There is one lowercase a-z word on each line of this file, and you may optionally assume it has a trailing newline. Here is a list of real words you can use for testing. You can assume this word list file is called `f` (or something longer) and lies in any convenient directory.

For a 35 byte penalty (add 35 to your score) you may assume the word list is already loaded into a variable as a list of strings. This is mainly for languages that can't read files, but any submission may take advantage of it.

Your program must output **all** the words in the word list that the input number can be converted to. They should be printed to stdout (or similar), one per line (with an optional trailing newline), or they can be returned as a list of strings if you chose to write a function. The word list is not necessarily alphabetized and the output doesn't need to be either.

If there are no possible words then the output (or the list) will be empty. The output is also empty if the empty string is input.

Take input via stdin, command line, or as a string argument to a function. The word list, or its file name, should not be part of the input, only the digit string.

You are only matching single words in the word list, not sequences of words. The word `noon` would probably be one of the results for `22`, but the word sequence `no one` wouldn't.

## Test Cases

Suppose this is the word list:

```
stnmrljkfp
zthnmrlshqfb
asatanamaralajakafapa
aizxydwwwnhimouooraleshhhcavabe
zdnmrlshcvb
zdnmrlshchvb
sthnmrlchgvb
shthnmrlchgvb
bob
pop
bop
bopy
boppy

```

The input `0123456789` should give all the long words except `zdnmrlshchvb` and `shthnmrlchgvb`:

```
stnmrljkfp
zthnmrlshqfb
asatanamaralajakafapa
aizxydwwwnhimouooraleshhhcavabe
zdnmrlshcvb
sthnmrlchgvb

```

The input `99` should give:

```
bob
pop
bop
bopy

```

(The output words may be in any order.)

## Scoring

The shortest submission in bytes wins. Tiebreaker goes to the submission posted first.

*Nifty related site: numzi.com.*

# Answer
# Perl, ~~87~~ 84

```
open A,f;"@ARGV"eq s/[cs]h/j/gr=~y/stnmrljkfpzdcgqvb\0-z/0-90177789/dr&&print for<A>

```

Takes input in as the command line parameter:

```
$perl m.pl 23940

```

Can be made somewhat shorter if the word list would be allowed on the standard input:

```
$perl -lnE'INIT{$;=pop}$;eq s/[cs]h/j/gr=~y/stnmrljkfpzdcgqvba-z/0-90177789/dr&&say' 99 <f

```
> 6 votes

# Answer
# Python 2, ~~215~~ 208 bytes

This Python solution builds a regex from parts indexed by the command line argument, then tests each word with that (rather large) regex.

```
import re,sys
a='[sz] (d|th?) n m r l (j|sh|ch) [kcgq] [fv] [pb]'.split()
b=z='((?<![sc])h|[aeiouwxy])*'
for i in sys.argv[1]:b+=a[int(i)]+z
for d in open('f'):
 d=d.strip()
 if re.match('^'+b+'$',d):print d

```

Original source before the minifier:

```
import re,sys
regexbits = '[sz] (d|th?) n m r l (j|sh|ch) [kcgq] [fv] [pb]'.split()

regex = other = '((?<![sc])h|[aeiouwxy])*'
for i in sys.argv[1] :
    regex += regexbits[int(i)] + other
print regex     # DEBUG

for word in open('f'):
    word = word.strip()
    if re.match('^'+regex+'$', word) :
        print word

```

For example, the regex for the test `99` is:

```
^((?<![sc])h|[aeiouwxy])*[pb]((?<![sc])h|[aeiouwxy])*[pb]((?<![sc])h|[aeiouwxy])*$

```

The `(?<![sc])h` bit is a "look behind negative assertion" component that makes sure a `h` does not follow a `s` or `c` in the general filler parts.

Thanks Calvin. This challenge motivated me to brush up on my rusty regex skills.
> 4 votes

# Answer
# Python 3, 170

```
import sys,re
t=str.maketrans('sztdnmrljkcgqfvpb','00112345677778899','aehiouwxy\n')
for s in open('f'):re.sub('sh|ch','j',s).translate(t)!=sys.argv[1] or print(s,end='')

```

Readable version:

```
import sys, re

table = str.maketrans('sztdnmrljkcgqfvpb', '00112345677778899', 'aehiouwxy\n')

for line in open('f'):
    line = re.sub('sh|ch', 'j', line)
    if line.translate(table) == sys.argv[1]:
        print(line, end='')

```

The code makes use of the fact that `th` is redundant (since it maps to the same number as `t`, and `h` is a padding character).

The static `maketrans` function creates a table mapping the characters of the first argument to those of the second argument, and the characters of the third argument to `None` (which will result in those characters being deleted).

The final code could be made a few bytes shorter by creating the table as a direct argument of `translate`.
> 2 votes

# Answer
# sed,paste,grep,cut - 109

```
sed -e 's/[sc]h/6/g;s/[aehiouwxy]//g;y/sztdnmrljkcqgfvpb/00112345677778899/' w|paste w -|grep " $1$"|cut -f1

```

Takes a file "w", converts each word to its number, paste back to the original, grep for the number and return the word matched. Note that the whitespace after the quote after grep is a tab, paste's default delimiter.

I know Perl is way ahead, just wanted a better shell version as an example.

Oh yeah, the $1 part means that this is supposed to be run from a shell script, (most shells should work), so it takes a command-line argument.
> 2 votes

# Answer
# Bash + coreutils, 216

```
sed -n "$(sed 's/[aeiouwxy]//g
:l
s/\([^sc]\)h/\1/g
tl'<w|grep -nf <(eval printf '%s\\n' `sed 's/0/{s,z}/g
s/1/{t,th,d}/g
y/2345/nmrl/
s/6/{j,sh,ch}/g
s/7/{k,c,g,q}/g
s/8/{f,v}/g
s/9/{p,b}/g'<<<$1`)|sed s/:.\*/p/)" w

```
* The word list in a file called `w`
* The innermost `sed` replaces digits with their possible replacements
* The `eval printf` uses shell brace expansions to expand out all the possible substitutions
* The second `sed` on the 1st line removes `aeiouwxy` and `h` (when not preceded by `[sc]`) from the word list
* The grep prints out all matches, with line numbers
* Since we have stripped out `aeiouwxy` and `h` from the word list, the last `sed` turns the results of grep (line numbers of each match) to another `sed` expression, which is processed by the outermost `sed` to reveal all possible words from the wordlist.

### Output:

The word list file is specified as a command-line arg, followed by the number to mnemonicize:

```
ubuntu@ubuntu:~$ ./numzi.sh 99
bob
pop
bop
bopy
boppy
$ ./numzi.sh 0123456789
stnmrljkfp
zthnmrlshqfb
asatanamaralajakafapa
aizxydwwwnhimouooraleshhhcavabe
zdnmrlshcvb
sthnmrlchgvb
$

```
> 1 votes

# Answer
**tr, sed, grep, xargs, sh, 77**

```
tr 0123456789 ztnmrljkfp|sed 's/ */[aehiouwxy]*/g'|xargs sh -c 'grep -x $0 f'

```

Expects the number in stdin and the word list should be stored in the file `f`.

Does not uses all replacements (1 will always be z, 7 will always be k), so it may be called a lazy solution, but it finds at least one mnemonic for 95 numbers in \[1-100\].
> -1 votes

---
Tags: code-golf, string
---


title: Am I code-golfing properly?

text:
# Question
Title: Am I code-golfing properly?
I am curious if I am Code Golfing properly. I set the challenge for myself to make a small hashing program into a single statement in Python. I first started off with:

```
from itertools import permutations
from string import ascii_lowercase
from random import sample

def test():
    chars = sample(ascii_lowercase, 9)
    sums = list(map(h, permutations(chars)))
    if len(set(sums)) == len(sums):
       print("unique results for permutations of given string")
    else:
       print("duplicate entries present in test results")

def h(s):
    r = 0
    for i in range(len(s)):
        r += ord(s[i]) << (i * len(s))
    return r

test()

```

I then made the function recursive:

```
def h(s, i=0):
    if i < len(s) - 1: return h(s, i+1) + ord(s[i]) << (i * len(s))
    else: return ord(s[i]) << (i * len(s))

```

I tried shortening it with a lambda for repeating code (it didn't work):

```
def h(s, i=0, f=lambda s,i: ord(s[i]) << (i * len(s))):
    if i < len(s) - 1: return h(s, i+1) + f(s,i)
    else: return f(s,i)

```

Finally I ended up with a lambda:

```
h=lambda s,i=0:h(s,i+1)+ord(s[i])<<(i*len(s))if i<len(s)-1 else ord(s[i])<<(i*len(s))

```

I wanted the program to be one statement, so first I came up with:

```
def test():
    chars = sample(ascii_lowercase, 9)
    sums = list(map((lambda s,i=0,f=lambda s,i,f:f(s,i+1,f)+ord(s[i])<<(i*len(s))if i<len(s)-1 else ord(s[i])<<(i*len(s)):f(s,i,f)), permutations(chars)))
    if len(set(sums)) == len(sums):
       print("unique results for permutations of given string")
    else:
       print("duplicate entries present in test results")

```

And lastly I ended up with:

```
print((lambda x=list(map((lambda s,i=0,f=lambda s,i,f:f(s,i+1,f)+ord(s[i])<<(i*len(s))if i<len(s)-1 else ord(s[i])<<(i*len(s)):f(s,i,f)), permutations(sample(ascii_lowercase, 9)))): "unique results for permutations of given string" if len(set(x)) == len(x) else "duplicate entries present in test results")())

```

Is this how codegolf problems are worked out? I've never really done this sort of thing, so right now I just want to know if I am doing it right.

**Amendment:** This program does all the work for you; so I will here refer to the function: As input, the program takes in all the permutations of a given string; here the string is nine characters randomly picked from `ascii_lowercase`. The output is a human-readable string defining whether the result of each permutation of the given string is a duplicate of another result for a different string. If there are no duplicates for all permutations, the program indicates success. Nine characters was picked as being the largest length of characters readily computed repeatedly on my box.

**Amendment II** As pointed out by a studious reader, the intended purpose described is not obtained through the accompanying code. The test case is obviously inadequate.

# Answer
There is no 'right' way to golf. You've done well, and the process you've used is fairly standard. Making the program into one statement isn't usually a requirement though.

If it helps, here's how I would approach golfing down your program...

In the hashing function, the for statement can be replaced with a sum:

```
def h(s):
    r = 0
    r = sum(ord(s[i]) << (i * len(s)) for i in range(len(s)))
    return r

```

This can then be defined as a lambda function:

```
h = lambda s: sum(ord(s[i]) << (i * len(s)) for i in range(len(s)))

```

And now we remove unnecessary spaces and brackets:

```
h=lambda s:sum(ord(s[i])<<i*len(s)for i in range(len(s)))

```

As Sp3000 pointed out, this can be shortened further with enumerate:

```
h=lambda s:sum(ord(x)<<i*len(s)for i,x in enumerate(s))

```

Moving on to the test function, we merge its first two lines:

```
def test():
    sums = list(map(h, permutations(sample(ascii_lowercase, 9))))
    ...

```

Since both functions are only used once, we can move everything inline:

```
sums = list(map(lambda s:sum(ord(x)<<i*len(s)for i,x in enumerate(s)), permutations(sample(ascii_lowercase, 9))))
...

```

This is shorter as a list comprehension:

```
sums = [sum(ord(x)<<i*len(s)for i,x in enumerate(s)) for s in permutations(sample(ascii_lowercase, 9))]

```

Next, we give it a shorter name and remove unnecessary spaces again:

```
x=[sum(ord(x)<<i*len(s)for i,x in enumerate(s))for s in permutations(sample(ascii_lowercase,9))]

```

The if statement can be moved inside the print function:

```
print('unique...' if len(set(x)) == len(x) else 'duplicate...')

```

However, it's usually shorter to use and/or:

```
print(len(set(x)) == len(x) and 'unique...' or 'duplicate...')

```

Since `len(x)` doesn't change, we can calculate and hardcode its value:

```
print(len(set(x)) == 362880 and 'unique...' or 'duplicate...')

```

After removing unnecessary spaces and switching around the comparison, we get:

```
print(len(set(x))<362880and'duplicate...'or'unique...')

```

This lets us move everything into one statement:

```
print(len(set([sum(ord(x)<<i*len(s)for i,x in enumerate(s))for s in permutations(sample(ascii_lowercase,9))]))<362880and'duplicate...'or'unique...')

```

And now we can use a set comprehension instead:

```
print(len({sum(ord(x)<<i*len(s)for i,x in enumerate(s))for s in permutations(sample(ascii_lowercase,9))})<362880and'duplicate...'or'unique...')

```

The result is 210 bytes, excluding imports. The next step would probably be to golf down the imports or the long strings.
> 11 votes

---
Tags: code-golf, tips, python
---


title: Sierpinskified Code

text:
# Question
Title: Sierpinskified Code
Write a rectangular block of text that when arranged into a Sierpinski carpet, using same-sized blocks of spaces for the empty portions, creates a program that outputs the iteration number of the carpet.

For example, if your text block is

```
TXT
BLK

```

then running the program

```
TXTTXTTXT
BLKBLKBLK
TXT   TXT
BLK   BLK
TXTTXTTXT
BLKBLKBLK

```

should output `1` because the shape of the program represents the first iteration of the Sierpinski carpet.

Similarly, running

```
TXTTXTTXTTXTTXTTXTTXTTXTTXT
BLKBLKBLKBLKBLKBLKBLKBLKBLK
TXT   TXTTXT   TXTTXT   TXT
BLK   BLKBLK   BLKBLK   BLK
TXTTXTTXTTXTTXTTXTTXTTXTTXT
BLKBLKBLKBLKBLKBLKBLKBLKBLK
TXTTXTTXT         TXTTXTTXT
BLKBLKBLK         BLKBLKBLK
TXT   TXT         TXT   TXT
BLK   BLK         BLK   BLK
TXTTXTTXT         TXTTXTTXT
BLKBLKBLK         BLKBLKBLK
TXTTXTTXTTXTTXTTXTTXTTXTTXT
BLKBLKBLKBLKBLKBLKBLKBLKBLK
TXT   TXTTXT   TXTTXT   TXT
BLK   BLKBLK   BLKBLK   BLK
TXTTXTTXTTXTTXTTXTTXTTXTTXT
BLKBLKBLKBLKBLKBLKBLKBLKBLK

```

should output 2 because this is the shape of the second Sierpinski carpet iteration.

Running the text block as is

```
TXT
BLK

```

should output `0` because it can be considered the zeroth iteration.

This should work for all further iterations. (At least theoretically, assuming the computer has the memory and all.)

# Details

* Programs may not read or access information about their source code. Treat this like a strict quine challenge.
* Output goes to stdout or similar alternative. Only output the number and an optional trailing newline. There is no input.
* The text block may contain any characters that are not considered line terminators. The text block may contain spaces.
* The "empty space" in the carpet must consist entirely of space characters.
* You may optionally assume all the programs have a trailing newline.

You can use this stack snippet to generate a carpet for a given text block at any iteration:

```
<style>#o,#i{font-family:monospace;}</style><script>function c(e){e=e.split("\n");for(var n=new Array(3*e.length),t=0;t<n.length;t++){var l=t%e.length;n[t]=e[l]+(t>=e.length&&t<2*e.length?e[l].replace(/./g," "):e[l])+e[l]}return n.join("\n")}function f(){for(i=document.getElementById("i").value,n=parseInt(document.getElementById("n").value);n>0;)i=c(i),n--;document.getElementById("o").value=i}</script><textarea id='i'placeholder='code block...'rows='8'cols='32'></textarea><br>Iterations <input id='n'type='text' value='1'><br><br><button type='button'onclick='f()'>Generate</button><br><br><textarea id='o'placeholder='output...'rows='8'cols='32'style='background-color:#eee'readonly></textarea>
```

# Scoring

The submission whose initial text block is smallest by area (width times height) is the winner. The `TXT\nBLK` example is 3 by 2 for a score of 6. (Basically the shortest code wins, hence the code-golf tag.)

Tiebreaker goes to the submission that uses the fewest distinct characters in their text block. If still tied, answer posted first wins.

# Answer
# CJam, 9 bytes

I think this can be improved, but for now, lets go with it...

```
];U):U8mL

```

**How it works**:

```
];             "Wrap everything on stack in an array and discard it";
               "Before this point, the only thing on array can be the log 8 result of";
               "last updated value of U, or nothing, if its the first code";
  U):U         "Increment by 1 and update the value of U (which is pre initialized to 0)";
      8mL      "Take log base 8 of U. This is the property of Sierpinski carpet that";
               "the occurrence of the code is 8 to the power iteration count, indexed 0";

```

Try it online here
> 23 votes

# Answer
# piet - 32\*6 = 192

I filled the empty space with the checker pattern. I think it makes the Sierpinski a bit trippier.

Here is the second iteration:

## original : 32\*7
> 34 votes

# Answer
# \>\<\>, 11 * 2 = 22

```
";n"00pbi1v
+$3*:@3-0.>

```

Here we take a different approach by using \>\<\>'s jump/teleport functionality.

The program only executes blocks in the top row, running the 1st/2nd block, then the 3rd/4th blocks, 9th/10th blocks, 27th/28th blocks, etc. (going up in powers of 3). As the top row has `3^n` blocks, only `n` blocks are executed before the program wraps back to the start, outputs the top of the stack and halts (due to the `n` instruction placed via `p`).

The program exploits the rule "There is no input.", as the `i` command pushes -1 onto the stack if EOF is met. So to test this you'll need to pipe in an empty file.

---

## Previous submission, 7 * 4 = 28

```
l"v"10p
v>:1=?v
3  ;n{<
<^}+1{,

```

The first line continuously pushes the length of the stack for every block, and changes the first `"` quote to a down arrow `v` using the `p` put command. By the time the first line is over, the stack looks like

```
[0, 1, 2, .., 3^n]

```

(Note that the initial `l` is used twice.)

The last three lines then count how many times we need to divide by 3 before we hit 1 (since \>\<\> doesn't have a log function). The bottom zero is used to keep track of the count.
> 19 votes

# Answer
# Perl, 26

```
$_+=.91/++$n;
die int."\n";

```

This uses the harmonic series to approximate the base 3 logarithm. I think it works, but I've only tried it for small numbers. Thanks to squeamish ossifrage for the idea of using `die`.

Old version (34):

```
$n--or$n=3**$s++;
print$s-1if!$o++;

```
> 13 votes

# Answer
# Perl, 30 (15×2)

First of all, I'm going to claim that 10 iterations is a reasonable limit, not 232. After 10 iterations, a program consisting of *N* bytes will have expanded to (*N* × 320) bytes (plus line breaks), which is over 3 gigabytes even for *N*=1. A 32-bit architecture would be completely unable to handle 11 iterations. (And obviously there aren't enough particles in the universe for 232 iterations).

So here's my solution:

```
$n++; $_=log$n;
print int;exit;

```

This works by incrementing the variable `$n` in the first line and calculating its logarithm at each step. The second line prints the integer part of this logarithm and quits.

A simple logarithm to base *e* (2.718..) is close enough to give correct results for the first 10 iterations.
> 10 votes

# Answer
# Golfscript, 9 * 2 = 18

```
0+
,3base,(}

```

*(Note that the first line has trailing spaces to make it rectangular)*

I couldn't find a log function for Golfscript, so `base` had to do.

Golfscript starts off with an empty string, so `0+` just increases the length of the string by 1 (by coersion). By the time the first line is over, the stack will have a string of length `3^n`, which we take the log base 3 of before we super comment. `n` is then automatically printed.
> 9 votes

# Answer
# **C, 12x8 = 96**

Inspired by @ciamej, I've reduced it. It uses that divide by 3 trick, plus the realization that the carpet effectively converts an if into a while loop.

The code was tested on gcc/Ubuntu for iterations up to 3.

```
#ifndef A //
#define A //
x;main(a){//
a++;/*    */
if(a/=3)x++;
printf(   //
"%d",x);} //
#endif    //

```

---

*Previous Solution: **C, 11x12***

Not a size winner, but hey, it's C.

It finds log2 of the blockcount by bitshifting, then uses some magic numbers and int truncation to estimate log3. The math should work up to 26 iterations (a 42 bit number).

```
#ifndef A//
#define A//
int n=0;//_
int main//_
(v,c){//___
n+=1;/*..*/
while(n//__
>>=1)v++;//
n=.3+.62*v;
printf(//__
"%d",n);}//
#endif//__

```
> 8 votes

# Answer
# CJam, 9 bytes

The idea of using `]` is from Optimizer, but it uses a very different method to count.

```
X~]:X,8mL

```

Try it online

How it works:

```
X~          "push X and dump its contents.  On the zeroth iteration, X is a single number, but later is it an array.";
  ]         "wrap everything into an array.  The stack would contain the contents of X plus the result of the previous instance of the code";
   :X       "store this array back into X.  X is now 1 element longer";
     ,      "take the length of X";
      8mL   "do a base-8 logarithm of it";

```

## Two other 9 byte solutions

```
]X+:X,8mL

],X+:X8mL

```
> 6 votes

# Answer
# Python 2, 15 * 3 = 45

```
m=n=0;E=exit  ;
m+=1;n+=m>3**n;
print n;E()   ;

```

Another implementation of the count-first-row-then-log-three-and-exit idea. Can probably still be golfed a fair bit more.
> 4 votes

# Answer
# \>\<\> (Fish), 12 * 3 = 36

A more straightforward \>\<\> solution:

```
'v'00p0l1+
>  :2-?v$1+v
^$+1$,3< ;n<

```

We first run the top row of the top blocks. `'v'00p` puts `v` at the very first position of the whole program directing the program pointer downwards when it gets back to the start after reaching the end of the line. Before that every block pushes 0 and the length of the stack + 1 onto it. (stack will be `0 2 0 4 0 6 ...`)

On the first half of the second and third we count how many times we can divide the top stack element before we get 2 (we store this in the second to top element).

At the end we output the second to top element of the stack.
> 2 votes

# Answer
# bc, 2\*16+1 = 33

The extra +1 in the score is because the `-l` bc option is required:

```
a+=1;
l(a)/l(3);halt;

```
> 2 votes

# Answer
# Golfscript, 7 * 2 = 14

```
1+~abs(
3base,}

```

This is inspired by Sp3000's answer, and in particular by the desire to optimise the long second line. `3base,` is as short as a base-3 logarithm will get in GS, and the super-comment `}` is clearly optimal.

What's required for the first line is to map the empty string `''` from the initial stdin to 0, and then to map each non-negative integer to its successor. In this way we end the first line with `3^n - 1` on the stack, and `3base,` doesn't require any decrement.
> 2 votes

# Answer
# C, 13x8

```
#ifndef A//__
#define A//__
x;a;main(){//
a++;;;;;;;;;;
while(a/=3)//
x++;printf(//
"%d",x);}//__
#endif//_____

```
> 2 votes

# Answer
# Perl, 76

I know there's probably not much point in posting this since it's already been thoroughly beaten, but here's my current solution anyways.

```
$_++;
if(not$_&$_-1){print log()/log 8;$_--}

```
> 1 votes

# Answer
# PHP, 22×2 = 44 27×2 = 54

```
<?php $i++          ?>
<?php die(log($i,3))?>

```

Just another take on count-log3-out. Not very small, but my first golf ;)
> 1 votes

# Answer
# Lua, 3 * 17 = 51

Same strategy as most people:

```
x=(x or 0)+1;
y=math.log(x,3)
print(y)os.exit()

```
> 1 votes

---
Tags: code-golf, source-layout, fractal
---


# Question
Title: Random Golf of the Day #3: Integer Partitions
# About the Series

First off, you may treat this like any other code golf challenge, and answer it without worrying about the series at all. However, there is a leaderboard across all challenges. You can find the leaderboard along with some more information about the series in the first post.

Although I have a bunch of ideas lined up for the series, the future challenges are not set in stone yet. If you have any suggestions, please let me know on the relevant sandbox post.

# Hole 3: Integer Partitions

Time to increase the difficulty a bit.

A **partition** of a positive integer `n` is defined as a multiset of positive integers which sum to `n`. As an example if `n = 5`, the following partitions exist:

```
{1,1,1,1,1}
{2,1,1,1}
{2,2,1}
{3,1,1}
{3,2}
{4,1}
{5}

```

Note that these are multisets, so there is no order to them, `{3,1,1}`, `{1,3,1}` and `{1,1,3}` are all considered identical.

Your task is, given `n`, to generate a random partition of `n`. Here are the detailed rules:

* The distribution of partitions produced must be **uniform**. That is, in the above example, each partition should be returned with probability 1/7.

Of course, due to the technical limitations of PRNGs, perfect uniformity will be impossible. For the purpose of assessing uniformity of your submission, the following operations will be regarded as yielding perfectly uniform distributions:

+ Obtaining a number from a PRNG (over any range), which is documented to be (approximately) uniform.
    + Mapping a uniform distribution over a larger set of numbers onto a smaller set via modulo or multiplication (or some other operation which distributes values evenly). The larger set has to contain at least 1024 times as many possible values as the smaller set.
* Since the partitions are multisets you may return them in any order, and this order does not have to be consistent. However, for the purpose of the random distribution, the order is ignored. That is, in the above example, `{3,1,1}`, `{1,3,1}` and `{1,1,3}` *together* must have a probability of 1/7 of being returned.
* Your algorithm must have a **deterministic runtime.** In particular, you cannot generate random multisets and reject them if they don't sum to `n`.
* Your algorithm's time complexity must be polynomial in `n`. In particular, you cannot simply generate all partitions and select a random one (since the number of partitions grows exponentially with `n`). You may assume that the PRNG you're using can return uniformly distributed values in O(1) per value.
* You must not use any built-in function which solves this task.

You may write a full program or a function and take input via STDIN or closest alternative, command-line argument or function argument and produce output via return value or by printing to STDOUT (or closest alternative).

You may assume that `n ≤ 65` (such that the number of partitions is less than 221). Output may be in any convenient, unambiguous list or string format.

If you submit a function, please consider also providing a little test program which calls the function a number of times and prints the results. It's okay if the parameters have to be tweaked in the code. This is just so people can check that the solution is at least approximately uniform.

This is code golf, so the shortest submission (in bytes) wins. And of course, the shortest submission per user will also enter into the overall leaderboard of the series.

# Leaderboard

**The first post of the series generates a leaderboard.**

To make sure that your answers show up, please start every answer with a headline, using the following Markdown template:

```
# Language Name, N bytes

```

where `N` is the size of your submission. If you improve your score, you *can* keep old scores in the headline, by striking them through. For instance:

```
# Ruby, <s>104</s> <s>101</s> 96 bytes

```

*(The language is not currently shown, but the snippet does require and parse it, and I may add a by-language leaderboard in the future.)*

# Answer
# Python 2, 179 bytes

```
from random import*
m=r=input();i=q=r+1;h=[1]+[0]*q*q;exec"h[i]=h[i+~q]+h[i-i%q*q];i+=1;"*r*q
while r:
 x=random()*sum(h[r*q:r*q-~m]);m=0
 while x>0:m+=1;x-=h[r*q+m]
 print m;r-=m

```

I used formula (39) from this Knuth extract, which gives the number of partitions of `n` that have exactly `m` parts. This happens to equal the number of partitions of `n` that have `m` as the maximum element, which is the interpretation I'm using. The elements of the partition are generated from greatest to least. At each stage the formula is reused with the current remainder of `n` and maximum allowed element.
> 8 votes

# Answer
# Dyalog APL, ~~67~~ ~~59~~ 51 bytes

`p←{⍵,⊂1,⍨+/¨⌽⍵↑¨⍨⌽⍳⍴⍵}⍣⎕⊢⍬⋄f←{⍵=0:⍬⋄a,a∇⍵-a←{1++/(?+/⍵)>+\⍵}⍺↑⍵⊃p}⍨` (67 bytes)

`p` is a vector of vectors in which `p[n][k]` is the number of partitions of `n` into `k` summands, or equivalently: the number of partitions with greatest summand `k`. We build `p` by starting with the empty vector , reading `n` (the  reads input) and repeatedly applying the following:

```
{⍵,⊂1,⍨+/¨⌽⍵↑¨⍨⌽⍳⍴⍵}
                 ⍴⍵   ⍝ the current length, initially 0
                ⍳⍴⍵   ⍝ 1 2 ... length
               ⌽⍳⍴⍵   ⍝ length ... 2 1
           ⍵↑¨⍨       ⍝ take length elements from p[1], length-1 from p[2], etc
                      ⍝ padded with 0-s, e.g. if p was (,1)(1 1)(1 1 1)(1 2 1 1)(1 2 2 1 1):
                      ⍝ we get:     (1 0 0 0 0)(1 1 0 0)(1 1 1)(1 2)(,1)
          ⌽           ⍝ reverse it: (,1)(1 2)(1 1 1)(1 1 0 0)(1 0 0 0 0)
       +/¨            ⍝ sum each:   1 3 3 2 1
    1,⍨               ⍝ append 1:   1 3 3 2 1 1
 ⍵,⊂                  ⍝ append the above to the vector of vectors

```

After `n` applications (`⍣⎕`), we have built `p`.

`f` picks a random partition. `n f k` is a random partition of *at most* `k` summands. `f n` is `n f n`.

```
{⍵=0:⍬⋄a,a∇⍵-a←{1++/(?+/⍵)>+\⍵}⍺↑⍵⊃p}⍨
                                     ⍨ ⍝ "selfie" -- use n as k if no k is provided
 ⍵=0:⍬                                 ⍝ if n=0 return empty
                                 ⍵⊃p   ⍝ pick the n-th element of p
                               ⍺↑      ⍝ take k elements from that
               {1++/(?+/⍵)>+\⍵}        ⍝ use them as weights to pick a random number 1...k
               {           +\⍵}        ⍝   partial sums of weights
               {    (?+/⍵)    }        ⍝   a random number 1...sum of weights
               {    (?+/⍵)>+\⍵}        ⍝   which partial sums is it greater than?
               {  +/          }        ⍝   count how many "greater than"-s
               {1+            }        ⍝   we're off by one
             a←                        ⍝ this will be the greatest number in our partition
         a∇⍵-a                         ⍝ recur with n1=n-a and k1=a
       a,                              ⍝ prepend a

```

---

Some improvements:

* inline `p` at the cost of slightly worse (but still good enough) performance
* in the computation of `p` rearrange  and `1,` to save a character
* turn `{1++/(?+/⍵)>+\⍵}` into a train with `1+` in front: `1+(+/(?+/)>+\)`
* make `f` an anonymous function and supply  (eval'ed input) as an argument to obtain a complete program

`{⍵=0:⍬⋄a,a∇⍵-a←1+(+/(?+/)>+\)⍺↑⍵⊃{⍵,⊂⌽1,+/¨⍵↑¨⍨⌽⍳⍴⍵}⍣⍵⊢⍬}⍨⎕` (59 bytes)

Test with n=5

Test with n=65

And the following link runs n=5 thousands of times and gathers statistics about the frequency of each partition: `⎕rl←0 ⋄ {⍺,⍴⍵}⌸ {⍵=0:⍬⋄a,a∇⍵-a←1+(+/(?+/)>+\)⍺↑⍵⊃{⍵,⊂⌽1,+/¨⍵↑¨⍨⌽⍳⍴⍵}⍣⍵⊢⍬}⍨ ¨10000⍴5`

---

More improvements, with help from Roger Hui:

* replace `{⍵=0:A⋄B}` with `{×⍵:B⋄A}`. Signum (`×⍵`) returns true for `⍵>0` and false for `⍵=0`.
* replace `(+/(?+/)>+\)` with `+/b<?⊃⌽b←+\`, it saves a character
* use a matrix instead of vector of vectors to compute `p`: replace `⍵⊃{⍵,⊂⌽1,+/¨⍵↑¨⍨⌽⍳⍴⍵}⍣⍵⊢⍬` with `⊃↓(0,⍨⊢⍪⍨1 1⍉+\)⍣⍵⍪1`.

`{×⍵:a,a∇⍵-a←1++/b<?⊃⌽b←+\⍺↑⊃↓(0,⍨⊢⍪⍨1 1⍉+\)⍣⍵⍪1⋄⍬}⍨` (51 bytes)

test n=5; test n=65; freq stats
> 6 votes

# Answer
## GolfScript, 90 bytes

```
~[[[1.]]]\({..[[{{(\{)}%+}%1$,1$,-=}%[1,]@0=+{1+}%]zip{{(\.,/*~}%.,.rand@=+}:^%]\+}*0=^(;`

```

Online demo

This is an adaptation of my (simpler) partition counting code which instead of merely tracking a count tracks both a count and a uniformly selected one of the counted elements.

Side-by-side comparison of the two:

```
~[[[1.]]]\({..[[{{(\{)}%+}%1$,1$,-=}%[1,]@0=+{1+}%]zip{{(\.,/*~}%.,.rand@=+}:^%]\+}*0=^(;`
 [[ 1  ]]\({..[[{          1$,1$,-=}%  0 @0=+     ]zip{{+}*                }:^%]\+}*0=^

```

Differences:

* The initial `~` is because this is a program rather than a snippet.
* The `[1.]` replacing `1` corresponds to the change in what's tracked.
* The additional `{(\{)}%+}%` increments each element in that partition, and the `{1+}%` adds `1` to the partition.
* `0` becomes `[0]` (golfed to `1,`) as part of the change in what's tracked, but because it needs to remain an array when prepended to another one it needs the extra `[ ]`.
* The simple sum `{+}*` becomes a weighted selection from the partitions, combined with a summing of their count.
* The `(;`` removes the count from the output and puts the partition into a nice format.

### Test framework

```
;7000,{;
  '5'

  ~[[[1.]]]\({..[[{{(\{)}%+}%1$,1$,-=}%[1,]@0=+{1+}%]zip{{(\.,/*~}%.,.rand@=+}:^%]\+}*0=^(;`

}%
:RESULTS
.&${
  RESULTS.[2$]--,' '\n
}/

```

Tweak the initial 7000 if you want to run a different number of trials. Note that this is far too slow for an online demo.
> 4 votes

# Answer
# Pyth, 64 bytes

Uses https://stackoverflow.com/a/2163753/4230423 except that a)No cache since Pyth automatically memoizes, b)Prints each instead of appending to list, and c) is translated to Pyth.

```
M?smg-Gddr1hhS,GHG1Akd,QOgQQWQFNr1hhS,QkKg-QNNI<dKB-=dK)N=kN-=QN

```

I'll post an explanation of this when I have the time, but here is the corresponding python code:

```
g=lambda G,H: sum(map(lambda d:g(G-d, d), range(1, (H if H<G else G) + 1))) if G else 1
Q=input()
k,d = Q,random.randrange(g(Q, Q))
while Q:
    for N in range(1, min(k, Q) + 1):
        K = g(Q-N, N)
        if d < K:
            break
        d -= K
    print N
    k=N
    Q -= N

```

**Edit:** I finally got around to doing the explanation:

```
M                Lambda g(G,H)
 ?         G     If G truthy
  s              Sum
   m             Map
    g            Recursive call
     -Gdd        G-d,d
    r            Range
     1           1 to
     h           +1
      hS         First element of sorted (does min)
       ,GH       From G and H
   1             Else 1
A                Double assign
 kd              Vars k and d
 ,               To vals
  Q              Q (evaled input)
  O              Randrange 0 till val
   gQQ           Call g(Q, Q)
WQ               While Q is truthy
 FN              For N in
  r              Range
   1             From one
   h             Till +1
    hS,QK        Min(Q,K)
  Kg             K=g(
   -QN           Q-N
   N             N
  I<dK           If d<k
   B             Break (implicit close paren)
  -=dk           Subtracts d-=k
 )               Close out for loop
 N               Prints N
 =kN             Set k=N
 -=QN            Subtracts Q-=N

```
> 4 votes

# Answer
# Java, ~~285~~ 267 bytes

```
int[][]p;void p(int n){p=new int[n+1][n+1];int a=n,b=k(n,a),c,d;for(b*=Math.random();n>0;System.out.print(c+" "),n-=a=c)for(c=0;c++<(a<n?a:n)&b>=(d=k(n-c,c));b-=d);}int k(int n,int k){if(p[n][k]<1)for(int a=0,b=0;b<k&b++<n;p[n][k]=a)a+=k(n-b,b);return n>0?p[n][k]:1;}

```

This is the same method as TheBestOne's answer, but it uses a simple array instead of a map. Also, instead of returning the random partition as a `List`, it prints them to the console.

Below is a test program that runs it 100000 times. For the example `n=5`, all sets were within 0.64% of a perfect 1/7 on my last run.

```
public class Partition {
    public static void main(String[] args) {
        Partition p = new Partition();
        for(int i=0;i<100000;i++){
            p.p(5);
            System.out.println();
        }
    }

    int[][]p;

    void p(int n){
        p=new int[n+1][n+1];
        int a=n,b=k(n,a),c,d;
        for(b*=Math.random();n>0;System.out.print(c+" "),n-=a=c)
            for(c=0;c++<(a<n?a:n)&b>=(d=k(n-c,c));b-=d);
    }

    int k(int n,int k){
        if(p[n][k]<1)
            for(int a=0,b=0;b<k&b++<n;p[n][k]=a)
                a+=k(n-b,b);
        return n>0?p[n][k]:1;
    }

}

```
> 3 votes

# Answer
# CJam, 64 56 bytes

```
ri_L{_0>{\,f{)_@1$-j+}{)@)2$+:Umr@<@@?U+}*}{!a\;}?}2j);p

```

You can test it with this script:

```
ria100*{_L{_0>{\,f{)_@1$-j+}{)@)2$+:Umr@<@@?U+}*}{!a\;}?}2j);}%__|\f{_,\2$a-,-}2/p

```

### Explanation

```
ri_                  " Read an integer and duplicate. ";
L{                   " Create a memoized function of the maximum and the sum, which returns
                       a random partition, and the total number of partitions as the last item. ";
    _0>              " If sum > 0: ";
    {
        \,f{         " For I in 0..max-1: ";
            )_@1$-   " Stack: I+1 I+1 sum-I-1 ";
            j+       " Recursively call with the two parameters, and prepend I+1. ";
        }
        {            " Reduce on the results: ";
            )@)2$+   " Stack: partition1 total1 partition2 total1+total2 ";
            :Umr     " U = total1+total2, then generate a random number smaller than that. ";
            @<@@?    " If it is <total1, choose partition1, else choose partition2. ";
            U+       " Append the total back to the array. ";
        }*
    }
    {!a\;}?          " Else return [0] if negative, or [1] if zero. ";
}2j
);p                  " Discard the total and print. ";

```
> 3 votes

# Answer
# Octave, 200

```
function r=c(m)r=[];a=eye(m);a(:,1)=1;for(i=3:m)for(j=2:i-1)a(i,j)=a(i-1,j-1)+a(i-j,j);end;end;p=randi(sum(a(m,:)));while(m>0)b=a(m,:);c=cumsum(b);x=min(find(c>=p));r=[r x];p=p-c(x)+b(x);m=m-x;end;end

```

Ungolfed:

```
function r=c(m)
  r=[];
  a=eye(m);
  a(:,1)=1;
  for(i=3:m)
    for(j=2:i-1)
      a(i,j)=a(i-1,j-1)+a(i-j,j);
    end;
  end;
  p=randi(sum(a(m,:)));
  while(m>0)
    b=a(m,:);
    c=cumsum(b);
    x=min(find(cumsum(b)>=p));
    r=[r x];
    p=p-c(x)+b(x);
    m=m-x;
  end
end

```

Construct a square matrix where each cell (m,n) reflects the number of partitions of `m` whose largest number is `n`, according to the Knuth extract @feersum so kindly cited. For example, `5,2` gives us 2 because there are two valid partitions `2,2,1` and `2,1,1,1`. `6,3` gives us 3 for `3,1,1,1`,`3,2,1` and `3,3`.

We can now deterministically find the p'th partition. Here, we are generating `p` as a random number but you can alter the script slightly so `p` is a parameter:

```
function r=c(m,p)
  r=[];
  a=eye(m);
  a(:,1)=1;
  for(i=3:m)
    for(j=2:i-1)
      a(i,j)=a(i-1,j-1)+a(i-j,j);
    end;
  end;
  while(m>0)
    b=a(m,1:m);
    c=cumsum(b);
    x=min(find(c>=p));
    r=[r x];
    p=p-c(x)+b(x);
    m=m-x;
  end
end

```

We can now deterministically show that each outcome is solely dependent on p:

```
octave:99> for(i=1:7)
> c(5,i)
> end
ans =

   1   1   1   1   1

ans =

   2   1   1   1

ans =

   2   2   1

ans =

   3   1   1

ans =

   3   2

ans =

   4   1

ans =  5

```

Thus, going back to the original where p is randomly generated, we can be assured each outcome is equally likely.
> 2 votes

# Answer
# R, 198 bytes

```
function(m){r=c();a=diag(m);a[,1]=1;for(i in 3:m)for(j in 2:(i-1))a[i,j]=a[i-1,j-1]+a[i-j,j];p=sample(sum(a[m,]),1);while(m>0){b=a[m,];c=cumsum(b);x=min(which(c>=p));r=c(r,x);p=p-c[x]+b[x];m=m-x};r}

```

Ungolfed:

```
f <- function(m) {
    r <- c()
    a <- diag(m)
    a[, 1] <- 1
    for (i in 3:m)
        for (j in 2:(i-1))
            a[i, j] <- a[i-1, j-1] + a[i-j, j]
    p <- sample(sum(a[m, ]), 1)
    while (m > 0) {
        b <- a[m, ]
        c <- cumsum(b)
        x <- min(which(c >= p))
        r <- c(r, x)
        p <- p - c[x] + b[x]
        m <- m - x
    }
    return(r)
}

```

It follows the same structure as @dcsohl's great solution in Octave, and is thus also based on the Knuth extract posted by @feersum.

I'll edit this later if I can come up with a more creative solution in R. In the meantime, any input is of course welcome.
> 2 votes

# Answer
# Java, 392 bytes

```
import java.util.*;Map a=new HashMap();List a(int b){List c=new ArrayList();int d=b,e=b(b,d),f=(int)(Math.random()*e),g,i;while(b>0){for(g=0;g++<Math.min(d, b);f-=i){i=b(b-g,g);if(f<i)break;}c.add(g);d=g;b-=g;}return c;}int b(int b,int c){if(b<1)return 1;List d=Arrays.asList(b,c);if(a.containsKey(d))return(int)a.get(d);int e,f;for(e=f=0;f++<Math.min(c, b);)e+=b(b-f,f);a.put(d,e);return e;}

```

Call with `a(n)`. Returns a `List` of `Integer`s

Indented:

```
import java.util.*;

Map a=new HashMap();

List a(int b){
    List c=new ArrayList();
    int d=b,e=b(b,d),f=(int)(Math.random()*e),g,i;
    while(b>0){
        for(g=0;g++<Math.min(d, b);f-=i){
            i=b(b-g,g);
            if(f<i)
                break;
        }
        c.add(g);
        d=g;
        b-=g;
    }
    return c;
}

int b(int b,int c){
    if(b<1)
        return 1;
    List d=Arrays.asList(b,c);
    if(a.containsKey(d))
        return(int)a.get(d);
    int e,f;
    for(e=f=0;f++<Math.min(c, b);)
        e+=b(b-f,f);
    a.put(d,e);
    return e;
}

```

Adapted from https://stackoverflow.com/a/2163753/4230423 and golfed

**How this works:** We can calculate how many partitions of an integer *n* there are in O(*n*2) time. As a side effect, this produces a table of size O(*n*2) which we can then use to generate the *k*th partition of *n*, for any integer *k*, in O(*n*) time.

So let *total* = the number of partitions. Pick a random number *k* from 0 to *total* \- 1. Generate the *k*th partition.

***As usual***, suggestions are welcome :)
> 1 votes

# Answer
# Python 2, 173 bytes

```
from random import*
N,M=input__
R=67;d=[(0,[])]*R*R
for k in range(R*R):p,P=d[k+~R];q,Q=d[k-k%R*R];d[k]=p+q+0**k,[[x+1 for x in Q],[1]+P][random()*(p+q)<p]
print d[N*R+M][1]

```

Recursively makes a dictionary `d`, with keys `k` representing a pair `(n,m)` by `k=67*n+m` (using the guaranteed `n<=65`). The entry is the tuple of the number of partition of `n` into `m` parts, and a random such partition. The counts are computed by the recursive formula (thanks to feersum for pointing it out)

`f(n,m) = f(n-1,m-1) + f(n,n-m)`,

and the random partition is updated by picking one of the two of its branches with probability proportional to its count. The update is done by adding is done by appending a `1` for the first branch and incrementing every element for the second.

I had a lot of trouble getting out-of-bounds values of `m` and `n` to give counts of zero. At first, I used a dictionary that defaults to a count of 0 and an empty list. Here, I'm using a list and padding it with this default entry instead. Negative indices cause the list to be read from its end, which gives a default entry is nothing near the end as ever reached, and wraparounds only touch a region where `m>n`.
> 1 votes

# Answer
# 80386 machine code, 105 bytes

Hexdump of the code:

```
60 8b fa 81 ec 00 41 00 00 33 c0 8b f4 33 d2 42
89 14 06 42 33 ed 8b d8 03 2c 1e 2a fa 73 f9 83
c6 04 89 2c 06 42 3b d1 76 ea fe c4 3a e1 76 db
33 d2 0f c7 f0 f7 f5 86 e9 85 d2 74 1b 33 c0 8d
34 0c 39 14 86 77 03 40 eb f8 2b 54 86 fc 40 89
07 83 c7 04 2a e8 77 e1 42 89 17 83 c7 04 fe cd
7f f7 4a b6 41 03 e2 61 c3

```

As a C function: `void random_partition(int n, int result[]);`. It returns the result as a list of numbers in the supplied buffer; it doesn't mark the end of the list in any way, but the user can discover the end by accumulating the numbers - the list ends when the sum is equal to `n`.

How to use (in Visual Studio):

```
#include <stdio.h>

__declspec(naked) void __fastcall random_partiton(int n, int result[])
{
#define a(byte) __asm _emit 0x ## byte
a(60) a(8b) a(fa) a(81) a(ec) a(00) a(41) a(00) a(00) a(33) a(c0) a(8b) a(f4) a(33) a(d2) a(42)
a(89) a(14) a(06) a(42) a(33) a(ed) a(8b) a(d8) a(03) a(2c) a(1e) a(2a) a(fa) a(73) a(f9) a(83)
a(c6) a(04) a(89) a(2c) a(06) a(42) a(3b) a(d1) a(76) a(ea) a(fe) a(c4) a(3a) a(e1) a(76) a(db)
a(33) a(d2) a(0f) a(c7) a(f0) a(f7) a(f5) a(86) a(e9) a(85) a(d2) a(74) a(1b) a(33) a(c0) a(8d)
a(34) a(0c) a(39) a(14) a(86) a(77) a(03) a(40) a(eb) a(f8) a(2b) a(54) a(86) a(fc) a(40) a(89)
a(07) a(83) a(c7) a(04) a(2a) a(e8) a(77) a(e1) a(42) a(89) a(17) a(83) a(c7) a(04) a(fe) a(cd)
a(7f) a(f7) a(4a) a(b6) a(41) a(03) a(e2) a(61) a(c3)
}

void make_stack() // see explanations about stack below
{
    volatile int temp[65 * 64];
    temp[0] = 999;
}

int main()
{
    int result[100], j = 0, n = 64, counter = n;
    make_stack(); // see explanations about stack below

    random_partiton(n, result);

    while (counter > 0)
    {
        printf("%d ", result[j]);
        counter -= result[j];
        ++j;
    }
    putchar('\n');
}

```

Example output (with n = 64):

> 21 7 4 4 3 3 3 3 2 2 2 2 2 1 1 1 1 1 1

This requires much explanations...

Of course I used the algorithm that everyone else used as well; there wasn't any choice with the requirement about complexity. So I don't have to explain the algorithm too much. Anyway:

I denote by `f(n, m)` the number of partitionings of `n` elements using parts no greater than `m`. I store them in a 2-D array (declared in C as `f[65][64]`), where the first index is `n`, and the second `m-1`. I decided that supporting `n=65` was too much trouble, so abandoned it...

Here is C code that calculates this table:

```
#define MAX_M 64
int f[(MAX_M + 1) * MAX_M];
int* f2;
int c; // accumulates the numbers needed to calculate f(n, m)
int m;
int k; // f(k, m), for various values of k, are accumulated
int n1;

for (n1 = 0; n1 <= n; ++n1)
{
    f2 = f;
    f2[n1 * MAX_M] = 1;
    for (m = 2; m <= n; ++m)
    {
        c = 0;
        k = n1;
        while (k >= 0)
        {
            c += f2[k * MAX_M];
            k -= m;
        }
        ++f2;
        f2[n1 * MAX_M] = c;
    }
}

```

This code has some obfuscated style, so it can be converted to assembly language easily. It calculates the elements up to `f(n, n)`, which is the number of partitionings of `n` elements. When this code is finished, the temporary variable `c` contains the needed number, which can be used to select a random partitioning:

```
int index = rand() % c;

```

Later, this `index` is converted to the required format (list of numbers) using the generated table.

```
do {
    if (index == 0)
        break;

    m = 0;
    f2 = &f[n * MAX_M];
    while (f2[m] <= index)
    {
        ++m;
    }

    index -= f2[m-1];
    ++m;
    *result++ = m;
    n -= m;
} while (n > 0);

do {
    *result++ = 1;
    --n;
} while (n > 0);

```

This code is also optimized for conversion to assembly language. There is a small "bug": if the partitioning doesn't contain any `1` number at the end, the last loop encounters `n = 0`, and outputs an unneeded `1` element. It doesn't hurt, however, because the printing code tracks the sum of the number, and doesn't print this extraneous number.

When converted to inline assembly, this code looks like this:

```
__declspec(naked) void _fastcall random_partition_asm(int n, int result[])
{
    _asm {
        pushad;

        // ecx = n
        // edx = m
        // bh = k; ebx = k * MAX_M * sizeof(int)
        // ah = n1; eax = n1 * MAX_M * sizeof(int)
        // esp = f
        // ebp = c
        // esi = f2
        // edi = result

        mov edi, edx;
        sub esp, (MAX_M + 1) * MAX_M * 4; // allocate space for table
        xor eax, eax;
    row_loop:
        mov esi, esp;
        xor edx, edx;
        inc edx;
        mov dword ptr [esi + eax], edx;
        inc edx;

    col_loop:
        xor ebp, ebp;
        mov ebx, eax;

    sum_loop:
        add ebp, [esi + ebx];
        sub bh, dl;
        jae sum_loop;

        add esi, 4;
        mov [esi + eax], ebp;
        inc edx;
        cmp edx, ecx;
        jbe col_loop;

        inc ah;
        cmp ah, cl;
        jbe row_loop;

        // Done calculating the table

        // ch = n; ecx = n * MAX_M * sizeof(int)
        // eax = m
        // ebx =
        // edx = index
        // esp = f
        // esi = f2
        // ebp = c
        // edi = result

        xor edx, edx;
        rdrand eax; // generate a random number
        div ebp; // generate a random index in the needed range
        xchg ch, cl; // multiply by 256

    n_loop:
        test edx, edx;
        jz out_trailing;
        xor eax, eax;
        lea esi, [esp + ecx];

    m_loop:
        cmp [esi + eax * 4], edx;
        ja m_loop_done;
        inc eax;
        jmp m_loop;
    m_loop_done:

        sub edx, [esi + eax * 4 - 4];
        inc eax;
        mov [edi], eax;
        add edi, 4;
        sub ch, al;
        ja n_loop;

    out_trailing:
        inc edx;
    out_trailing_loop:
        mov dword ptr [edi], edx;
        add edi, 4;
        dec ch;
        jg out_trailing_loop;

        dec edx;
        mov dh, (MAX_M + 1) * MAX_M * 4 / 256;
        add esp, edx;
        popad;
        ret;
    }
}

```

Some fun things to note:

* Generating a random number takes just 3 bytes of machine code (`rdrand` instruction)
* By a coincidence, the size of the table is 64, so the size of one row is 256 bytes. I use this to hold row indices in "high-byte" registers like `ah`, which gives me automatic multiplication by 256. To take advantage of this, I sacrificed the support for `n = 65`. I hope I can be excused for this sin...
* Allocating space on stack is performed by subtracting 0x4100 from the stack pointer register `esp`. This is a 6-byte instruction! When adding this number back, I managed to do it in 5 bytes:

```
    dec edx; // here edx = 1 from earlier calculations
    mov dh, (MAX_M + 1) * MAX_M * 4 / 256; // now edx = 0x4100
    add esp, edx; // this deallocates space on stack

```
* When debugging this function in MS Visual Studio, I found out that it crashes when it writes data to the space that it allocated on stack! After some digging around, I discovered some sort of stack overrun protection: OS seems to allocate only a very limited range of virtual addresses for stack; if a function accesses an address too far away, OS assumes it's an overrun and kills the program. However, if a function has many local variables, OS does some extra "magic" to make it work. So I have to call an empty function that has a large array allocated on stack. After this function returns, extra stack VM pages are allocated and can be used.

```
    void make_stack()
    {
        volatile int temp[65 * 64];
        temp[0] = 999; // have to "use" the array to prevent optimizing it out
    }

```
> 1 votes

---
Tags: code-golf, combinatorics, random, restricted-complexity, integer-partitions
---


title: List the Cases of Two Finnish Nouns

text:
# Question
Title: List the Cases of Two Finnish Nouns
# Introduction

In this challenge, your task is to correctly list the cases of two Finnish nouns. The twist is that you may use one of the listings as a guide to produce the other.

### The Nouns

We use the following two declination tables as our data. They list the cases of two nouns, one case per line in the same order as in the Wikipedia article linked above, in the form *singular : plural* where applicable.

**Table 1: Cases of *ovi* ("door")**

```
ovi : ovet
oven : ovien
oven : ovet
ovea : ovia
ovessa : ovissa
ovesta : ovista
oveen : oviin
ovella : ovilla
ovelta : ovilta
ovelle : oville
ovena : ovina
oveksi : oviksi
ovin
ovetta : ovitta
ovine

```

**Table 2: Cases of *jalka* ("foot")**

```
jalka : jalat
jalan : jalkojen
jalan : jalat
jalkaa : jalkoja
jalassa : jaloissa
jalasta : jaloista
jalkaan : jalkoihin
jalalla : jaloilla
jalalta : jaloilta
jalalle : jaloille
jalkana : jalkoina
jalaksi : jaloiksi
jaloin
jalatta : jaloitta
jalkoine

```

# The Task

Your task is to write two programs `f` and `g` (possibly with different names) that take one string as input, give one string as output, and have the following property. If Table 1 is given to `f` as input, it outputs Table 2, and if Table 2 is given to `g`, it outputs Table 1. All other inputs result in undefined behavior. The tables must appear *exactly* as above in both input and output. You may optionally assume that there is a trailing newline, but then it must be used in both tables, and in both input and output. There is no preceding newline.

# Rules and Bonuses

You can write `f` and `g` as either functions or full programs, but they must be of the same type, and they must be completely separate (if you write a helper function for `f`, you must re-write it in `g` if you want to use it there). The lowest total byte count wins, and standard loopholes are disallowed.

There is a **bonus of -25 %** for not using regular expressions.

### Some Clarifications

It is perfectly fine to write a function/program `f` that ignores its input and always returns Table 2, and a function/program `g` that always returns Table 1. It is only required that `f(*Table 1*) == *Table 2*` and `g(*Table 2*) == *Table 1*`; the behavior of `f` and `g` on all other inputs is irrelevant.

The "completely separate" part means the following. Your answer provides two pieces of code, one for `f` and one for `g`, preferably in different code boxes. If I put the code for `f` in a file and run it, it works, and the same for `g`. Your score is the sum of the byte counts of the two pieces of code. Any duplicated code is counted twice.

# Answer
> 6 votes
# Perl, 105 + 54 = 159

Program `f` (try me):

```
#!perl -p
s/vi /vka /;s/ve/va/g;s/en/an/;s/vi/voi/;s/ov/1&34960>>$.?jalk:jal/eg;s/ii/ihi/;s/loia/lkoje/;s/oia/oja/

```

Program `g` (try me):

```
#!perl -p
s/jalk?o?/ov/g;s/va /vi /;s/va/ve/g;s/an/en/;y/jh/i/d

```

An alternative version of `f`, only 2 bytes longer (this method can be also applied to `g` but it would be too long):

```
#!perl -p0
ka1a1a1koj1a1a1ka1koj1a1o0a1o0kaa2koih1a1o0a1o0a1o0ka1ko0a1o0o0a1o0ko=~s!\D+!"s/ov".'.'x$'."/jal$&/"!gree

```

Technically this still uses a regexp (to decode the substitution string and then to apply them) so I cannot claim the bonus here.

# Answer
> 5 votes
# Perl, 131 + 74 = 205

### Table 1 to Table 2

```
$_=join"",<>;s/ee/kaa/;s/ii/koihi/;s/i(e|a)/koj$1/g;s/i(na|ne)/koi$1/g;s/v[ie](.?a| )/vka$1/g;s/vi/voi/g;s/ve/va/g;s/ov/jal/g;print

```

**Expanded:**

```
$_=join"",<>;
s/ee/kaa/;
s/ii/koihi/;
s/i(e|a)/koj$1/g;
s/i(na|ne)/koi$1/g;
s/v[ie](.?a| )/vka$1/g;
s/vi/voi/g;
s/ve/va/g;
s/ov/jal/g;
print

```

### Table 2 to Table 1

```
$_=join"",<>;s/aan/aen/;s/jal(ka\b|oi|ko[ij]h?)/ovi/g;s/jalk?a/ove/g;print

```

**Expanded:**

```
$_=join"",<>;
s/aan/aen/;
s/jal(ka\b|oi|ko[ij]h?)/ovi/g;
s/jalk?a/ove/g;
print

```

*(Thanks to @nutki for some Perl tips)*

Despite the penalty on regexes, I decided to tackle it anyway and learn Perl while I was at it. I'm assuming there's some Perl tricks which might let me chain replacements, but I couldn't find any in my quick search online.

It's much harder to go from the *ovi* table to *jalka* table, which I'm guessing is because the *jalka* table has additional nuances to make words easier to pronounce.

---

Here's the replacement table I was working off:

```
i <-> ka
--------
ov i               jal ka

e <-> ka
--------
ov e a             jal ka a
ov e na            jal ka na

e <-> a
-------
ov e t             jal a t
ov e n             jal a n
ov e ssa           jal a ssa
ov e sta           jal a sta
ov e lla           jal a lla
ov e lta           jal a lta
ov e lle           jal a lle
ov e ksi           jal a ksi
ov e tta           jal a tta

i <-> oi
--------
ov i ssa           jal oi ssa
ov i sta           jal oi sta
ov i lla           jal oi lla
ov i lta           jal oi lta
ov i lle           jal oi lle
ov i ksi           jal oi ksi
ov i n             jal oi n
ov i tta           jal oi tta

i <-> koi
---------
ov i na            jal koi na
ov i ne            jal koi ne

i <-> koj
---------
ov i en            jal koj en
ov i a             jal koj a

i <-> koih
------------
ov i in            jal koih in

ee <-> kaa
----------
ov ee n            jal kaa n

```

# Answer
> 2 votes
# Python 2, 371 - 25% = 278

When table 1 is the input to function f, it returns table 2. If the input is not table 1, it's output is undefined (however likely but not guaranteed to return table 2). For example, calling `f(9**9**9**9)` will probably not return table 2.

```
f=lambda a:'jalkaBatAanBkojenAanBatAkaaBkojaAassaBoissaAastaBoistaAkaanBkoihinAallaBoillaAaltaBoiltaAalleBoilleAkanaBkoinaAaksiBoiksiAoinAattaBoittaAkoine'.replace('A','\njal').replace('B',' : jal')

```

The same logic is used with function g:

```
g=lambda a:'oviBetAenBienAenBetAeaBiaAessaBissaAestaBistaAeenBiinAellaBillaAeltaBiltaAelleBilleAenaBinaAeksiBiksiAinAettaBittaAine'.replace('A','\nov').replace('B',' : ov')

```

The functions are independent.

# Answer
> 0 votes
# VBA ~~1204 (1605 - 25%)~~ 1191 (1587 - 25%)

The direct approach.

### Edit: Corrected bug and used replace trick from @Maltysen

```
Function f(s)
    If Replace(s, " : ", ":") = "ovi:ovet" & vbLf & "oven:ovien" & vbLf & "oven:ovet" & vbLf & "ovea:ovia" & vbLf & "ovessa:ovissa" & vbLf & "ovesta:ovista" & vbLf & "oveen:oviin" & vbLf & "ovella:ovilla" & vbLf & "ovelta:ovilta" & vbLf & "ovelle:oville" & vbLf & "ovena:ovina" & vbLf & "oveksi:oviksi" & vbLf & "ovin" & vbLf & "ovetta:ovitta" & vbLf & "ovine" Then f = Replace("jalka:jalat" & vbLf & "jalan:jalkojen" & vbLf & "jalan:jalat" & vbLf & "jalkaa:jalkoja" & vbLf & "jalassa:jaloissa" & vbLf & "jalasta:jaloista" & vbLf & "jalkaan:jalkoihin" & vbLf & "jalalla:jaloilla" & vbLf & "jalalta:jaloilta" & vbLf & "jalalle:jaloille" & vbLf & "jalkana:jalkoina" & vbLf & "jalaksi:jaloiksi" & vbLf & "jaloin" & vbLf & "jalatta:jaloitta" & vbLf & "jalkoine", ":", " : ")
End Function

Function g(s)
    If Replace(s, " : ", ":") = "jalka:jalat" & vbLf & "jalan:jalkojen" & vbLf & "jalan:jalat" & vbLf & "jalkaa:jalkoja" & vbLf & "jalassa:jaloissa" & vbLf & "jalasta:jaloista" & vbLf & "jalkaan:jalkoihin" & vbLf & "jalalla:jaloilla" & vbLf & "jalalta:jaloilta" & vbLf & "jalalle:jaloille" & vbLf & "jalkana:jalkoina" & vbLf & "jalaksi:jaloiksi" & vbLf & "jaloin" & vbLf & "jalatta:jaloitta" & vbLf & "jalkoine" Then f = Replace("ovi:ovet" & vbLf & "oven:ovien" & vbLf & "oven:ovet" & vbLf & "ovea:ovia" & vbLf & "ovessa:ovissa" & vbLf & "ovesta:ovista" & vbLf & "oveen:oviin" & vbLf & "ovella:ovilla" & vbLf & "ovelta:ovilta" & vbLf & "ovelle:oville" & vbLf & "ovena:ovina" & vbLf & "oveksi:oviksi" & vbLf & "ovin" & vbLf & "ovetta:ovitta" & vbLf & "ovine", ":", " : ")
End Function

```

Run from the Immediate window:

```
msgbox f("ovi : ovet" & vbLf & "oven : ovien" & vbLf & "oven : ovet" & vbLf & "ovea : ovia" & vbLf & "ovessa : ovissa" & vbLf & "ovesta : ovista" & vbLf & "oveen : oviin" & vbLf & "ovella : ovilla" & vbLf & "ovelta : ovilta" & vbLf & "ovelle : oville" & vbLf & "ovena : ovina" & vbLf & "oveksi : oviksi" & vbLf & "ovin" & vbLf & "ovetta : ovitta" & vbLf & "ovine")

```

# Answer
> 0 votes
# Python - 462 - 25% = 346.5

This program does the obvious, direct approach except for a few data golfing tricks. For the undefined behavior it print the table just like the defined behavior. What an amazing "coincidence"! :)

```
x,y="""ovi:ovet
oven:ovien
oven:ovet
ovea:ovia
ovessa:ovissa
ovesta:ovista
oveen:oviin
ovella:ovilla
ovelta:ovilta
ovelle:oville
ovena:ovina
oveksi:oviksi
ovin
ovetta:ovitta
ovineXjalka:jalat
jalan:jalkojen
jalan:jalat
jalkaa:jalkoja
jalassa:jaloissa
jalasta:jaloista
jalkaan:jalkoihin
jalalla:jaloilla
jalalta:jaloilta
jalalle:jaloille
jalkana:jalkoina
jalaksi:jaloiksi
jaloin
jalatta:jaloitta
jalkoine""".replace(':',' : ').split('X')
f=lambda n:y
g=lambda n:x

```

Now, if one would consider this cheating (yeah right), I can follow the spirit of the rules for 20 more characters **= 482 - 25%=361.5**. Just replace the last two lines with:

```
f=lambda n:[x,y][n==x]
g=lambda n:[y,x][n==y]

```

This would make the undefined behavior return not the correct table but the input table.

# Answer
> 0 votes
# JavaScript (ES6) 271 (165 + 196 -25%)

Starting simple. The functions ignore input parameter at all.
Using split/join instead of replace to avoid regular expressions.

```
g=_=>'ovi1et0n1ien0n1et0a1ia0ssa1issa0sta1ista0en1iin0lla1illa0lta1ilta0lle1ille0na1ina0ksi1iksi\novin0tta1itta\novine'
.split(0).join('\nove').split(1).join(' : ov')
f=_=>'jalka1at0an1kojen0an1at0kaa1koja0assa1oissa0asta1oista0kaan1koihin0alla1oilla0alta1oilta0alle1oille0kana1koina0aksi1oiksi0oin0atta1oitta0koine'
.split(0).join('\njal').split(1).join(' : jal')

```

**Test** in Firefox/FireBug console

```
console.log(f('ovi : ovet\noven : ovien\noven : ovet\novea : ovia\novessa : ovissa\novesta : ovista\noveen : oviin\novella : ovilla\novelta : ovilta\novelle : oville\novena : ovina\noveksi : oviksi\novin\novetta : ovitta\novine'))

```

> jalka : jalat
> jalan : jalkojen
> jalan : jalat
> jalkaa : jalkoja
> jalassa : jaloissa
> jalasta : jaloista
> jalkaan : jalkoihin
> jalalla : jaloilla
> jalalta : jaloilta
> jalalle : jaloille
> jalkana : jalkoina
> jalaksi : jaloiksi
> jaloin
> jalatta : jaloitta
> jalkoine

```
console.log(g("jalka : jalat\njalan : jalkojen\njalan : jalat\njalkaa : jalkoja\njalassa : jaloissa\njalasta : jaloista\njalkaan : jalkoihin\njalalla : jaloilla\njalalta : jaloilta\njalalle : jaloille\njalkana : jalkoina\njalaksi : jaloiksi\njaloin\njalatta : jaloitta\njalkoine"))

```

> ovi : ovet
> oven : ovien
> oven : ovet
> ovea : ovia
> ovessa : ovissa
> ovesta : ovista
> oveen : oviin
> ovella : ovilla
> ovelta : ovilta
> ovelle : oville
> ovena : ovina
> oveksi : oviksi
> ovin
> ovetta : ovitta
> ovine

---
Tags: code-golf, kolmogorov-complexity, natural-language
---


# Question
Title: StackExchange Mustafa can't stand to be asked the same question three times
> **Austin:** "Who sent you?"
>
> **Mustafa:** "You have to kill me!"
>
> **Austin:** "Who sent you?"
>
> **Mustafa:** "Kiss my ass, Powers!"
>
> **Austin:** "Who sent you?"
>
> **Mustafa:** "Dr. Evil."
>
> (...)
>
> **Mustafa:** "I can't stand to be asked the same question three times. It just irritates me."

You are to simulate a short dialogue in the spirit of Austin Powers and Mustafa. But the data source for the entire conversation will be a StackOverflow question (provided as input from a URL).

# Rules

The question asker's username will be used in place of "Austin". The question they will ask three times comes from the last sentence in the question title, (which has been forced to end in a question mark if it did not already).

StackExchange will be playing the part of "Mustafa". The answer ultimately given comes from the first sentence in the answer that does not end in a question mark, and will be attributed to the name of the user who answered.

For a question to qualify for the game, it must (a) have an answer, and (b) there must be a sequence of comments on the original question that goes:

* comment from someone other than questioner
* (any number of skipped comments)
* comment from questioner
* comment from someone other than questioner
* (any number of skippable comments)
* comment from questioner

If this sequence is not satisfied *prior to the date of the top ranked answer*, the program should simply output `"Oh, behave!"`

StackExchange Mustafa's angry retorts come from the first sentence of the comments from someone other than the questioner that *don't* end with a question mark--and ensuring it ends with an exclamation mark. If no sentence exists in the comment that doesn't end in a question mark, it is skipped as a candidate for the retort. Comment retorts are attributed to the user name of the author.

# Clarifications

* Strip any leading "@XXX" response data from a comment.
* Because StackOverflow summarizes the comments if there are many of them, you will probably have to use a second request to get the full list. That request is of the form `https://stackoverflow.com/posts/NNN/comments?_=MMM` with the post ID in N and question ID in M. See for instance: https://stackoverflow.com/posts/11227809/comments?\_=211160
* URLs should be stripped to anchor text only.
* We'll define a "sentence" as anything outside of a code block that ends in a period, question mark, or exclamation point. If a run of text has no ending punctuation of this form, then the end of the text is the end of the sentence; as if it were written with a period.
* If you're looking for funny test cases that are likely to qualify, you might try using StackExchange Data Explorer, such as Posts with the Most Comments.
* *... more to come, I'll wager...*

# Samples

### Sample One

**Input:**

`https://stackoverflow.com/questions/2283937/how-should-i-ethically-approach-user-password-storage-for-later-plaintext-retrie/`

**Output:**

> **shanee:** "How should I ethically approach user password storage for later plaintext retrieval?"
>
> **stefanw:** "I think he knows that it is not good!"
>
> **shanee:** "How should I ethically approach user password storage for later plaintext retrieval?"
>
> **Rook:** "Perhaps you should ask how you can implement a Buffer Overflow Vulnerability in a Secure way!"
>
> **shanee:** "How should I ethically approach user password storage for later plaintext retrieval?"
>
> **Michael Burr:** "Ask why the password is required to be in plaintext: if it's so that the user can retrieve the password, then strictly speaking you don't really need to retrieve the password they set (they don't remember what it is anyway), you need to be able to give them a password they can use."

### Sample Two

**Input:**

`http://scifi.stackexchange.com/questions/2611/why-dont-muggle-born-wizards-use-muggle-technology-to-fight-death-eaters`

**Output:**

> **DVK:** "Why don't muggle-born wizards use Muggle technology to fight Death Eaters?"
>
> **DampeS8N:** "This dances on the edge again!"
>
> **DVK:** "Why don't muggle-born wizards use Muggle technology to fight Death Eaters?"
>
> **DampeS8N:** "Right, but this site isn't about pointing out plot holes!"
>
> **DVK:** "Why don't muggle-born wizards use Muggle technology to fight Death Eaters?"
>
> **Jeff:** "I believe, though I've been unable to find a reference, that JK Rowling actually mentioned this at one point."

### Sample Three

**Input:**

`https://stackoverflow.com/questions/11227809/why-is-processing-a-sorted-array-faster-than-an-unsorted-array`

**Output:**

> "Oh, behave!"

*(The top rated answer time is `Jun 27 '12 at 13:56`, while the second follow-up comment on the question by the questioner is at time `Jun 27 '12 at 14:52`. Hence, there isn't a causal link between the second follow-up and the answer. :-P)*

## Winning Criteria

Code Golf - shortest code wins.

# Answer
> 3 votes
# PHP, 1282 chars

While 1282 quite huge for a code golf challenge, the challenge is quite complex. (And I am not very good at golf.)

```
<?php function a($a,$b='q'){$a=strip_tags(htmlspecialchars_decode($a,ENT_QUOTES));$a=preg_replace('/^@[^ ]+\s+/','',$a);$a=mb_split('(?<=(?:\.|!|\?))\s+',$a);if($b=='q'){return preg_replace('/(?:\.|!|\?)$/','',$a[0]).'?';}else{foreach($a as$s){if(!preg_match('/\?$/',$s)){if($b=='c'){return preg_replace('/(?:\.|!)$/','',$s).'!';}else{return preg_replace('/(?<!(?:\.|!))$/','.',$s);}}}}return 0;}function b($a){return json_decode(gzdecode(file_get_contents('http://api.stackexchange.com/2.2/questions/'.$a)));}function c($a){return $a->owner->display_name;}$n="\n";$x="Oh, behave!\n";$r=parse_url($argv[1]);$b=explode('/',$r['path']);$b=$b[2];$u=b($b.'?site='.$r['host']);$u=$u->items[0];$c=b($b.'/comments?filter=withbody&order=asc&sort=creation&site='.$r['host']);$a=b($b.'/answers?filter=withbody&order=desc&sort=votes&site='.$r['host']);if(!count($a->items)||!count($c->items))die($x);$a=$a->items[0];$s=array();$d=1;foreach($c->items as$e){if($e->creation_date>$a->creation_date)break;if($e->owner->user_id==$u->owner->user_id){$d=1;}elseif($d){$e->body=a($e->body,'c');if($e->body){$s[]=$e;}$d=0;}}if(count($s)<2)die($x);$q=c($u).': "'.a($u->title,'q').'"'.$n;echo$q.c($s[0]).': "'.$s[0]->body.'"'.$n.$q.c($s[1]).': "'.$s[1]->body.'"'.$n.$q.c($a).': "'.a($a->body,'a').'"'.$n;

```

## Ungolfed version

```
<?php

    function firstSentence($string, $type = 'q') {
        $string = strip_tags(htmlspecialchars_decode($string, ENT_QUOTES));
        $string = preg_replace('/^@[^ ]+\s+/', '', $string);
        $string = mb_split('(?<=(?:\.|!|\?))\s+', $string);
        if($type === 'q') {
            return preg_replace('/(?:\.|!|\?)$/', '', $string[0]) . '?';
        } else {
            foreach($string as $s) {
                if(!preg_match('/\?$/', $s)) {
                    if($type === 'c') {
                        return preg_replace('/(?:\.|!)$/', '', $s) . '!';
                    } else {
                        return preg_replace('/(?<!(?:\.|!))$/', '.', $s);
                    }
                }
            }
        }
        return false;
    }

    $x = "Oh, behave!\n";

    $url = parse_url($argv[1]);
    $api = 'http://api.stackexchange.com/2.2/';

    $id = explode('/', $url['path']);
    $id = $id[2];

    $question = json_decode(gzdecode(file_get_contents($api . 'questions/' . $id . '?site=' . $url['host'])));
    $question = $question->items[0];
    $comments = json_decode(gzdecode(file_get_contents($api . 'questions/' . $id . '/comments?filter=withbody&order=asc&sort=creation&site=' . $url['host'])));
    $answer = json_decode(gzdecode(file_get_contents($api . 'questions/' . $id . '/answers?filter=withbody&order=desc&sort=votes&site=' . $url['host'])));
    if(!count($answer->items) || !count($comments->items))
        die($x);

    $answer = $answer->items[0];

    $selected = array();
    $usable = true;
    foreach($comments->items as $comment) {
        if($comment->creation_date > $answer->creation_date)
            break;
        if($comment->owner->user_id === $question->owner->user_id) {
            $usable = true;
        } elseif($usable) {
            $comment->body = firstSentence($comment->body, 'c');
            if($comment->body !== false) {
                $selected[] = $comment;
            }
            $usable = false;
        }
    }

    if(count($selected) < 2)
        die($x);

    $q = $question->owner->display_name . ': "' . firstSentence($question->title, 'q') . '"' . "\n";
    echo $q;
    echo $selected[0]->owner->display_name . ': "' . $selected[0]->body . '"' . "\n";
    echo $q;
    echo $selected[1]->owner->display_name . ': "' . $selected[1]->body . '"' . "\n";
    echo $q;
    echo $answer->owner->display_name . ': "' . firstSentence($answer->body, 'a') . '"' . "\n";

?>

```

---
Tags: code-golf, stack-exchange-api
---


title: Topping the Charts

text:
# Question
Title: Topping the Charts
# Topping the Charts

You are a record label company. Your goal is to get 4 of your signed bands in the top 4 positions in the charts. However, its recently been noted that bands currently in the charts influence who is going to be in the charts the next day.

In this challenge, each player will control 5 bands (instances of your code), each of them placed in alternating order in one of the 11 spots of the scoreboard, with the 11th spot open. Each band will have a unique, hidden ID (from 0-9), and a unique, visible name (a randomly generated integer).

Each turn, the band with the open spot below them in the charts will call an ID. The bot instance with that ID will move to that spot, creating a new open spot. If spot #1 is open, then the 11th bot will be the one to name an ID.

The game is over when spots 1-4 are all held by your bands, giving you 3 points. If a particular band ordering is created more than 3 times, then both labels will tie and be given 1 point. The player with the most points after facing each other player twice (to ensure both labels start with a band in the #1 position) wins.

# I/O

Bots will be stay alive between turns. Information will be passed back and forth via STDIO. When multiple pieces of information is passed, it will be comma separated. Each instance of your bot **MUST NOT** communicate with each other (nor with the other team).

At the beginning of the game, your will be passed three integers, your ID, position, and name, and then you will be passed a list of names of the current positions, with 0 being the open position.

On your turn, you will be passed a list of names of the current positions, with 0 being the open position. You must return the ID you wish to place in the spot below you.

If you get switched, you will be be passed two integers, the name of the person that switched you, and your new position (from 0-10).

If you win, you will be passed 0, at which, you must end your program

The controller can be found here: https://github.com/nathanmerrill/ScoreboardKoTH

# Answer
> 2 votes
# Random Bot

If you couldn't guess, this bot picks a number randomly. Run with `python random_bot.py`

```
import sys
import random

def get_data():
    data = sys.stdin.readline().strip()
    if data == "0":
        exit()
    return [int(x) for x in data.split(",")]

def startup():
    global _id, position, name
    all_data = get_data()
    player_names = all_data[3:]
    _id, position, name = all_data[:3]

def switched(switcher, new_position):
    global position
    position = new_position

def call_id(player_names):
    return random.randrange(10)

_id = -1
position = -1
name = -1
startup()
while True:
    data = get_data()
    if len(data) == 1:
        break
    elif len(data) == 2:
        switched(*data)
    else:
        print str(call_id(player_names=data))
        sys.stdout.flush()

```

# Answer
> 2 votes
# Self Mover Bot

This bot always moves itself. Run with:

```
javac SelfMover.java
java SelfMover

```

Code:

```
import java.util.Scanner;

public class SelfMover {

    private Scanner stdIn;
    private final int id, name;
    private int position;

    public static void main(String[] args) {
        new SelfMover();
    }

    public SelfMover() {
        stdIn = new Scanner(System.in);
        Integer[] data = getData();
        id = data[0];
        position = data[1];
        name = data[2];
        mainLoop();
    }
    private void mainLoop() {
        while(true){
            Integer[] data = getData();
            if (data.length == 1){
                return;
            } else if (data.length == 2){
                switched(data[0], data[1]);
            } else {
                System.out.println(callID(data));
            }
        }
    }
    private Integer[] getData(){
        String data = stdIn.nextLine().trim();
        if (data.equals("0")){
            System.exit(0);
        }
        String[] strData = data.split(",");
        Integer[] intData = new Integer[strData.length];
        for (int i = 0; i < strData.length; i++){
            intData[i] = Integer.parseInt(strData[i]);
        }
        return intData;
    }
    private void switched(int switcher, int newPosition){
        position = newPosition;
    }
    private int callID(Integer[] players){
        return id;
    }

}

```

# Answer
> 1 votes
# Unswitcher bot

This bot mistakenly assumes that its new position is the ID of the bot that switched it, and tries to unswitch.

Run with `python unswitcher_bot.py`

```
import sys

last_switched = -1

def get_data():
    data = sys.stdin.readline().strip()
    if data == "0":
        exit()
    return [int(x) for x in data.split(",")]

def startup():
    global _id, position, name
    try:
        all_data = get_data()
    except:
        raise NameError
    player_names = all_data[3:]
    _id, position, name = all_data[:3]

def switched(switcher, new_position):
    global position, last_switched
    position = new_position
    last_switched = switcher

def call_id(player_names):
    return min(position, 9)

_id = -1
position = -1
name = -1
startup()
while True:
    data = get_data()
    if len(data) == 1:
        break
    elif len(data) == 2:
        switched(*data)
    else:
        print call_id(player_names=data)
        sys.stdout.flush()

```

---
Tags: king-of-the-hill
---