title: Latin Word Judgment

text:
# Question
Title: Latin Word Judgment
Because I can't concentrate on any task for more than about 5 seconds, I often find myself breaking up words into a sub-strings, each of which is a different length and doesn't contain any repeated characters. For example, the word "pasta" might be broken up in "past" & "a", "pas" & "ta", or "pa" & "sta" and you get the picture.

However, because remembering all the combinations is hard, I generally only select one, and I like to select the nicest one. We consider the nicest way to be that which has the lowest "score". Your task will be, given a word, to print its score, given the following complicated rules.

## Scoring

Description of how to score a word:

* A word is a string of Latin characters, capital letters should be replaced with 2 of the same lowercase letter (so "Box" becomes "bbox")
* A segment is a contiguous (strict) substring of a word, and must not contain any character twice ("her", "re", "h" are all valid segments of "Here" ("hhere"), but "hh" and "ere" are not)
* A segmentation is a set of segments of different lengths which, when joined, form the original word ("tre" and "e" makes "tree"), and that cannot be further segmented within the segmentation (i.e. "ba" has a single segmentation, "ba"; and "alp" & "habet" is not a valid segmentation of "alphabet", because either of these could be further segmented (e.g. into "a" & "lp" & "habet", which is now a valid segmentation ("habet" can't be segmented without forming a segment of length 2 or 1))).
* The score of a segmentation is the sum of the scores of each distinct character that appears in the original word (once capitals have been replaced)
* The scoring of characters is explained below
* The score of a word is the score of its nicest possible segmentation (that with the lowest score)

If no valid segmentations exist for a word (for example, "Brass" ("bbrass"), which can't be segmented because the first "b" and last "s" would have to be in their own segments, which would result in two segments of the same length), then you should output the text "evil", otherwise you should output the score of the word.

### Character scoring

The scoring of characters is based on how many times the character appears, and the weightings of the segments it appears in. The weightings of the segments depends on the lengths of the segment, and the lowest common multiple of the lengths of all the segments in the segmentation.

```
segment weighting = lowest common multiple of lengths segments / length of segment

```

Consider the word "olive", which could be segmented as "ol" & "ive", and visualised as 2 boxes of the same area, one of "ol" with weight 3, and one of "ive" with weight 2 (LCM of 6).

```
ol
ol ive
ol ive

```

This is meant to depict the two boxes, one made from 3 "ol"s, and one made from 2 "ive"s. Alternativly, it might be "o" & "live" (LCM of 4)

```
o
o
o
o live

```

The score of each character is then the sum of the weights of the segments in which it appears, multiplied by the number of times it appears after replacing capitals (so if it appears twice, you are charged double for each time you have to say it).

```
character score = character count * sum(segment weights in which character appears)

```

### Scoring example

We take the word "fall", it can only be segmented into "fal" and "l". The lowest common multiple of 3 and 1 is 3, so "fal" has weight 1, and "l" has weight 3.

```
    l
    l
fal l

```

Going through each character...

* "f" appears once, and is in the segment "fal" with weight 1, so has score 1\*1 = 1
* "a" also appears only once, has sum of weights of 1, so has score 1\*1 = 1
* "l" appears twice, and appears in "fal" (weight 1) and "l" (weight 3), so has score 2\*(1+3) = 8

The sum of these is 10 (the score of the segmentation, and of the word, as this is the nicest segmentation). Here is this in the same format as the examples below:

```
fall = fal l
2*1 [fa] + 2*(1+3) [ll] = 10

```

### Example Scorings

These examples of scorings may or may not help:

```
class -> clas s
3*1 [cla] + 2*(4+1) [ss] = 13

fish -> fis h
3*1 [fis] + 1*3 [h] = 6

eye -> e ye
1*1 [y] + 2*(1+2) [ee] = 7

treasure -> treas u re
3*2 [tas] + 2*2*(2+5) [rree] + 1*10 [u] = 44

Wolf -> w wolf
3*1 [olf] + 2*(1+4) = 13

book
evil

```

"book" is an evil word, so doesn't have a score.

Note that "treasure" can be segmented in a number of ways, but the segmentation shown benefits from having the more frequent letters ("r" and "e") in the longer segments, so they don't have as much weight. The segmentation "t" & "re" & "asure" would give the same result, while "treas" & "ur" & "e" would suffer, with "e" having a score of 2\*(1+10+2) = 24 on its own. This observation is really the spirit of the whole exercise. An example of an incorrect score of "treasure" (incorrect because it's not derived from the score of the nicest segmentation (that with the lowest score)):

```
treasure = treas ur e
3*2 [tas] + 2*(2+5) [rr] + 1*5 [u] + 2*[2+10] = 49

```

## Input

A single string containing only latin characters of either case ("horse", "Horse", and "hOrSe" are all valid inputs) which can be accepted either by STDIN, Command-line argument, function argument, or otherwise if your language of choice doesn't support any of the aforementioned.

## Output

You must output either the score of the word, which is a single positive integer greater than 0, or "evil" if no segmentation exists. Output should be to STDOUT or the return argument of a function, unless your language of choice supports neither of these, in which case do something sportsmanly.

## Examples

I do not expect you to print all this stuff, all I want is the score of the word, or the output "evil", for example (input followed by output)

```
eye
7

Eel
evil

a
1

Establishments
595

antidisestablishmentarianism
8557

```

I'm not concerned about performance, if you can score just about any 15letter word (after replacing capitals) in under a minute on a sensible (intentionally left vague) machine, that's good enough for me.

This is code-golf, may the shortest code win.

*Thanks to PeterTaylor, MartinBüttner, and SP3000 for their help with this challenge*

# Answer
> 5 votes
# Mathematica, 373 bytes

```
If[l=Length;a=Accumulate[l/@#]&;u=Unequal;e=Select;{}==(m=(g=#;Tr[#2Flatten[ConstantArray[#,LCM@@l/@g/l@#]&/@g]~Count~#&@@@Tally@c])&/@e[p=e[c~Internal`PartitionRagged~#&/@Join@@Permutations/@IntegerPartitions[l[c=Characters[s=StringReplace[#,c:"A"~CharacterRange~"Z":>(d=ToLowerCase@c)<>d]]]],u@@l/@#&&And@@u@@@#&],FreeQ[p,l_List/;#!=l&&SubsetQ[a@l,a@#]]&]),"evil",Min@m]&

```

This is quite long... and also rather naive. It defines an unnamed function that takes the string and returns score. It takes about 1 second to handle `"Establishments"`, so it's well within the time limit. I've got a slightly shorter version that uses `Combinatorica`SetPartitions`, but it already takes a minute for `"Establishme"`.

Here is a version with whitespace:

```
If[
  l = Length;
  a = Accumulate[l /@ #] &;
  u = Unequal;
  e = Select;
  {} == (
    m = (
      g = #;
      Tr[
        #2 Flatten[
          ConstantArray[
            #,
            LCM @@ l /@ g/l@#
          ] & /@ g
        ]~Count~# & @@@ Tally@c
      ]
    ) & /@ e[
      p = e[
        c~Internal`PartitionRagged~# & /@ Join @@ Permutations /@ IntegerPartitions[
          l[
            c = Characters[
              s = StringReplace[
                #,
                c : "A"~CharacterRange~"Z" :> (d = ToLowerCase@c) <> d
              ]
            ]
          ]
        ],
        u @@ l /@ # && And @@ u @@@ # &
      ],
      FreeQ[p, l_List /; # != l && SubsetQ[a@l, a@#]] &
    ]
  ),
  "evil",
  Min@m
] &

```

I might add a more detailed explanation later. This code uses the second solution from this answer to get all the partitions and this solution to make sure they are all maximally segmented.

# Answer
> 2 votes
# Java 8, ~~1510~~ 1485 bytes

This is **way** too long. Combinatorics are never easy in java. It definitely can be shortened quite a bit. Call with `a(string)`. This uses an exponential memory and time algorithm; so don't expect it to work for long inputs. It takes about half a second to process `Establishments`. It crashes with an out of memory error for `antidisestablishmentarianism`.

```
import java.util.*;import java.util.stream.*;void a(String a){a=a.replaceAll("\\p{Upper}","$0$0").toLowerCase();List<List<String>>b=b(a),c;b.removeIf(d->d.stream().anyMatch(e->e.matches(".*(.).*\\1.*")));b.removeIf(d->{for(String e:d)for(String f:d)if(e!=f&e.length()==f.length())return 1>0;return 1<0;});c=new ArrayList(b);for(List<String>d:b)for(List<String>e:b){if(d==e)continue;int f=0,g=0;List h=new ArrayList(),i=new ArrayList();for(String j:d)h.add(f+=j.length());for(String k:e)i.add(g+=k.length());if(i.containsAll(h))c.remove(d);else if(h.containsAll(i))c.remove(e);}b=c;int d=-1;for(List e:b)d=d<0?c(e):Math.min(c(e),d);System.out.println(d<0?"evil":d);}int c(List<String>a){List<Integer>b=a.stream().map(c->c.length()).collect(Collectors.toList()),d;int e=d(b.toArray(new Integer[0])),f=0,g=0,h;d=b.stream().map(A->e/A).collect(Collectors.toList());Map<Character,Integer>i=new HashMap(),j=new HashMap();for(;g<a.size();g++){h=d.get(g);String k=a.get(g);for(char l:k.toCharArray()){i.put(l,i.getOrDefault(l,0)+1);j.put(l,j.getOrDefault(l,0)+h);}}for(char k:i.keySet())f+=i.get(k)*j.get(k);return f;}int d(Integer...a){int b=a.length,c,d,e;if(b<2)return a[0];if(b>2)return d(a[b-1],d(Arrays.copyOf(a,b-1)));c=a[0];d=a[1];for(;d>0;d=c%d,c=e)e=d;return a[0]*a[1]/c;}List b(String a){List<List>b=new ArrayList(),c;for(int i=0;++i<a.length();b.addAll(c)){String d=a.substring(0,i),e=a.substring(i);c=b(e);for(List f:c)f.add(0,d);}b.add(new ArrayList(Arrays.asList(a)));return b;}

```

Try here

Indented with explanation:

```
void a(String a){
    a = a.replaceAll("\\p{Upper}", "$0$0").toLowerCase();                //Replace all uppercase letters with two lowercase letters

    List<List<String>> b = b(a), c;                                      //Generate partitions
    b.removeIf(d -> d.stream().anyMatch(e -> e.matches(".*(.).*\\1.*")));//Remove partitions that contains duplicate letters

    b.removeIf(d -> {                                                    //Remove partitions that have equal length parts
        for (String e : d)
            for (String f : d)
                if (e != f & e.length() == f.length())
                    return 1 > 0;
        return 1 < 0;
    });

    c = new ArrayList(b);                                                //Remove partitions that can be partitioned further
    for (List<String> d : b)                                             //Uses Martin's technique
        for (List<String> e : b){
            if (d == e)
                continue;
            int f = 0, g = 0;
            List h = new ArrayList(), i = new ArrayList();
            for (String j : d)
                h.add(f += j.length());
            for (String k : e)
                i.add(g += k.length());
            if (i.containsAll(h))
                c.remove(d);
            else if (h.containsAll(i))
                c.remove(e);
        }

    b = c;

    int d = -1;
    for (List e : b)
        d = d < 0 ? c(e) : Math.min(c(e), d);                            //Find nicest partition

    System.out.println(d < 0 ? "evil" : d);
}

int c(List<String> a) {                                                  //Grade a partition
    List<Integer> b = a.stream().map(c->c.length()).collect(Collectors.toList()), d; //Map to length of parts

    int e = d(b.toArray(new Integer[0])), f = 0, g = 0, h;

    d = b.stream().map(A -> e / A).collect(Collectors.toList());         //Figure out the weight of each part

    Map<Character, Integer> i = new HashMap(), j = new HashMap();

    for (; g < a.size(); g++){                                           //Count instances of each character and
        h = d.get(g);                                                    //weight of each character
        String k = a.get(g);
        for (char l : k.toCharArray()){
            i.put(l, i.getOrDefault(l, 0) + 1);
            j.put(l, j.getOrDefault(l, 0) + h);
        }
    }

    for (char k : i.keySet())
        f += i.get(k) * j.get(k);                                        //Sum cost of each character

    return f;
}

int d(Integer... a) {                                                    //Find lcm
    int b = a.length, c, d, e;
    if (b < 2)
        return a[0];
    if (b > 2)
        return d(a[b - 1], d(Arrays.copyOf(a, b - 1)));
    c = a[0];
    d = a[1];
    for (;d > 0;d = c % d, c = e)
        e = d;
    return a[0] * a[1] / c;
}

List b(String a) {                                                       //Find all partitions of a string
    List<List> b = new ArrayList(), c;                                   //Uses recursion
    for (int i = 0; ++i < a.length();b.addAll(c)){
        String d = a.substring(0, i), e = a.substring(i);
        c = b(e);
        for (List f : c)
            f.add(0, d);
    }
    b.add(new ArrayList(Arrays.asList(a)));
    return b;
}

```

This also abuses generics quite a bit to reduce the byte count. I'm pretty surprised I was able to get all of it to compile.

Thanks Ypnypn :)

# Answer
> 2 votes
# C# 679 Bytes

This solution is roughly based off my the structure of my original test implementation, and initially was just a golfed re-write, but then I inlined all the functions, and now it's horrifying. It's reasonably fast, solving Establishments in under a second. It's a complete program that takes the input word as a single paramater of ARGV.

```
using Q=System.String;class P{static void Main(Q[]A){Q s="";foreach(var c in A[0]){var z=(char)(c|32);if(c<z)s+=z;A[0]=s+=z;}int r=S(A);System.Console.WriteLine(r<1?"evil":""+r);}static int S(Q[]s){int r=0,t,j,k,L=1,Z=s.Length,i=Z,T=0,R=2;for(;i-->0;R=t<1?0:R){t=s[i].Length;k=L;for(j=2;t>1;)if(t%j++<1){t/=--j;if(k%j<1)k/=j;else L*=j;}}foreach(var C in Q.Join("",s))for(i=Z;i-->0;){for(k=s[j=i].Length;j-->0;)R=k==s[j].Length?0:R;j=s[i].IndexOf(C)+1;R=j*R*s[i].IndexOf(C,j)>1?1:R;T+=j>0?L/k:0;}i=R<1?0:Z;for(var U=new Q[Z+1];i-->0;)for(j=s[i].Length;j-->1;r=r<1|((t=S(U))>0&t<r)?t:r)for(U[k=Z]=s[i].Substring(j);k-->0;U[i]=s[i].Substring(0,j))U[k]=s[k];return r<1?R<2?R-1:T:r;}}

```

The `Main` method starts by creating a copy of the input with the capitals replaced. It then calls `S`, the "solver", which returns the score of a given segmentation (the first segmentation being that with a single segment which is the whole word). It then either prints "evil" or the score, depending on the score.

The "solver" (`S`) does all the interesting stuff, and was originally broken down down into 4 methods, which were rolled together. It works by first scoring the current segmentation, making a note of whether it is invalid (and crucially, whether it is so invalid we shouldn't try to further segment it (for performance), skipping the rest of the computation if it is). Then, if it hasn't been skipped, it splits each segment in the segmentation everywhere it can be split, and finds the best score of all of these (recursively calling `S`). Finally, it either returns the best score of the subordinate Segmentations, else it's own score, or invalid if it's own segmentation is invalid.

Code with comments:

```
using Q=System.String; // this saves no bytes now

class P
{
    // boring
    static void Main(Q[]A)
    {
        // this can surely be shorter
        // replace capitals
        // I refuse to put this in S (would give us a Q, but we'd have to pay for the Action=null)
        Q s="";

        foreach(var c in A[0])
        {
            var z=(char)(c|32); // ugly
            if(c<z)
                s+=z; // ugly
            A[0]=s+=z; // reuse the array
        }

        int r=S(A); // reuse the array
        System.Console.WriteLine(r<1?"evil":""+r);
    }

    // solve
    static int S(Q[]s) // s is current solution
    {
        int r=0,t,j,k,
        L=1,Z=s.Length,i=Z,
        T=0, // is score for this solution (segmentation)
        R=2; // R is current return value, as such, 0 -> return -1, 1 -> return 0, 2 -> return T

        // score first
        // factorise stuff, L is LCM
        for(;
            i-->0; // for each segment
            R=t<1?0:R) // segment too short (skip)
        {
            t=s[i].Length;

            k=L; // we cut up k as we cut up c, when we can't cut up k, we need to build up L
            for(j=2;t>1;)
                if(t%j++<1) // j goes into t
                {
                    t/=--j; // cut up t
                    if(k%j<1) // j goes into k
                        k/=j; // cut up k
                    else
                        L*=j; // j does not go into k, build up L
                }
        }

        // recycle i, j, k, (t)

        foreach(var C in Q.Join("",s)) // for each character
            for(i=Z;i-->0;) // for each segment
            {
                for(k=s[j=i].Length;
                    j-->0;) // for all the segments that follow
                    R=k==s[j].Length?0:R; // repeat length (skip)

                j=s[i].IndexOf(C)+1;

                // these both check if this segment contains the char (j > 0)
                R=j*R*s[i].IndexOf(C,j)>1?1:R; // duplicate char (allow)

                T+=j>0?L/k:0; // add on the segment weight
            }

        // R is whether we are invalid or not
        // T is our score

        i=R<1?0:Z; // if segmentation invalid and can't be segmented, skip everything (performance)

        // recycle i, j, k, t
        // first use of r=0

        for(var U=new Q[Z+1];
            i-->0;) // for each segment
            for(j=s[i].Length;
                j-->1; // for each place we can split it
                r=r<1|((t=S(U))>0&t<r)?t:r) // solve where we split thing at i at position j, if this score is better than r, replace r with it
                for(U[k=Z]=s[i].Substring(j); // put second half of s[i] in last position (order doesn't matter)
                    k-->0; // for each char in s[i]
                    U[i]=s[i].Substring(0,j)) // put first half of s[i] in p position
                    U[k]=s[k]; // copy across everything else

        return r<1?R<2?R-1:T:r; // if we didn't find a valid solution more segmented than this, return our score (unless we are invalid, in which case, return R-1), else the score for the more segmentation solution
    }
}

```

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


title: Encoding an URL in brainfuck

text:
# Question
Title: Encoding an URL in brainfuck
Inspired by this question, your goal today is to encode an URL in brainfuck.

My browser has been hacked! The location bar has been turned into a brainfuck interpreter. I need a program that turns an URL into a brainfuck program. My computer is also very slow, so if the brainfuck program is small it's better.

Oh and I only have one working tab left open, my twitter. So you can only send me the program in a tweet.

---

1. Write a program that fits in a tweet (140 characters) in any language that takes a string as input and outputs a brainfuck program.
2. This brainfuck program will be run without input and will generate an output.
3. This output will be inserted into the location bar of Google Chrome, and executed.
4. If the behaviour of Google Chrome is identical to the behaviour you would get by entering the input string from #1, then the solution is valid. *Redirection by URL shorteners is considered different behaviour - stay at least on the same domain.*

You may assume the brainfuck interpreter has infinite precision signed integers in each cell and an unlimited amount of cells.

Your score is determined by the sum of the lengths of the brainfuck programs generated to encode the following set of URLs:

```
https://www.google.com/
https://codegolf.stackexchange.com/questions/47895/
http://www.golfscript.com/golfscript/examples.html
http://en.wikipedia.org/wiki/Percent-encoding
ftp://ftp.freebsd.org/pub/FreeBSD/
https://github.com/isaacg1/pyth/blob/master/doc.txt#L92
http://ftp.gnu.org/non-gnu/nethack/nethack-3.4.0.tar.gz.back-RSN.README

```

Smallest score wins.

# Answer
> 7 votes
# Pyth - 118 bytes, score: 154 + 567 + 597 + 620 + 530 + 875 + 1092 = 6630 6623 4653 4435

Now using the factor multiplication algo!

This is a pretty simple algorithm, although slightly better than the above ones. I was planning to use Pyth, but with the current algorithm Python fits\<140 bytes.

```
=zecz"//"=z?>z4}"www."zz=z?Pzqez\/zFNzKCNJ/^K.5 1=d\+pk+holN[?*-KZd>KZ*-ZK\-+\>*dK+++++\>*Jd"[>"*Jd"<-]>"*-K*JJd)\.=ZK

```

It first strips out the `http://` by using `split("//")` and the `www.` and `/` at the end. Then it uses the min function to check which is the best of the the three options that is considered:

1. Use `+` or `-` to update current cell value to desired cell value
2. Go to new cell and just fill with `+`'s
3. Go to new cell and use multiplication to update by doing sqrt(n)\*sqrt(n)+remainder since square has minimum perimeter of constant area. http://cydathria.com/bf/bf\_ex3.html

I then always put a `.` to output each char.

A detailed explanation of the new code is coming soon. I kind of half-assed the golfing, especially the stripping of `www.` and the `/` at the end but I can't be bothered since I'm 20 bytes under the limit.

This surprisingly works on the `ftp://` urls since this is chrome and chrome automatically makes `ftp.freebsd.org/pub/FreeBSD/` into `ftp://ftp.freebsd.org/pub/FreeBSD/`

I plan to next use a dictionary to store the cell values and see if the character was already made in a cell.

---

## Brainfuck Omnibox Extension

That's right! After I saw @BrainSteel's comment, I knew I had to make it. This doesn't take over the entire omnibox, only when you do `bf`,`tab`. Also since the omnibox api is weird, it doesn't let me forward the code to the omnibox, I have to handle it myself. So I do my own `http://` checking and then set the tab's url.

Since I didn't feel like paying the $5 necessary to put your extension on the webstore, you guys will have to install it manually. Just download the zip from here: https://drive.google.com/file/d/0B0qkKIzGc0QiNzBzVUJjZkRIZ0k/view?usp=sharing, unzip, go into the extensions page in chrome, click dev mode option box on top-right, and load the unpacked extension.

Hope you guys enjoy! :)

# Answer
> 4 votes
# C, ~~140~~ ~~134~~ ~~132~~ ~~138~~ ~~128~~ 139 Bytes

# 263 + 816 + 911 + 955 + 827 + 1355 + 1779 = ~~7269~~ 6906 bytes

Update: 6 bytes less, thanks to nutki!

Update again, 128 bytes. Code is significantly less readable. It now attempts to strip the URL of `ftp://`, too.

Update the third, at 139 bytes. Code is a bit more readable, and got rid of some nasty undefined behavior. Now, if the site name is preceded by `www.`, it is stripped. I got under 7k, but I think I must concede to Maltysen with Pyth. Well done.

```
#define p putchar
a;main(int c,char**V){while(*V[1]++-47);*++V+=1;for(*V+=**V-'w'?0:4;c=**V;*V+=1,p(46))for(;c-a;a+=c>a?1:-1)p(c>a?43:45);}

```

Unraveled a bit:

```
#define p putchar
a;
main(int c,char**V){
    while(*V[1]++-47);
    *++V+=1;
    for(*V+=**V-'w'?0:4;c=**V;*V+=1,p(46))
        for(;c-a;a+=c>a?1:-1)
            p(c>a?43:45);
}

```

This code takes a URL at the command line, and converts it into BF using only `.`,`-`, and `+`. The code makes an attempt to strip the string of `ftp://`,`http://`,`https://`, and `www.` before converting to BF. Here is a list of outputs of the outputs:

```
google.com/
codegolf.stackexchange.com/questions/47895/
golfscript.com/golfscript/examples.html
en.wikipedia.org/wiki/Percent-encoding
ftp.freebsd.org/pub/FreeBSD/
github.com/isaacg1/pyth/blob/master/doc.txt#L92
ftp.gnu.org/non-gnu/nethack/nethack-3.4.0.tar.gz.back-RSN.README

```

# Answer
> 4 votes
# Brainfuck, 77 bytes, Score = 31647

Score is the sum of `codepoint+4` for every character.

```
+++++[>+++++++++<-]>+[>++>+>++>+>+<<<<<-]>+>->->>--->,[[<.>-]<<.<.<.<.>>>>>,]

```

(Uses BF implementation with EOF = 0.)

Example:

```
input:
!bar

output:
+++++++++++++++++++++++++++++++++.[-]++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++.[-]+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++.[-]++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++.[-]

```

# Answer
> 0 votes
# JavaScript (ES6) - 137 bytes, score - 7413

This uses only `.`, `+` and `-`. You can test it in Firefox console.

```
B=s=>[...s.replace(/^h.+\/\//,'')].map((c,i,a)=>(v=i?c[C]()-a[i-1][C]():c[C='charCodeAt']())?'-+'[v>0|0].repeat(v>0?v:-v):'').join('.')+'.'

```

This is my score counter:

```
[
    'https://www.google.com/',
    'http://codegolf.stackexchange.com/questions/47895/',
    'http://www.golfscript.com/golfscript/examples.html',
    'http://en.wikipedia.org/wiki/Percent-encoding',
    'ftp://ftp.freebsd.org/pub/FreeBSD/',
    'https://github.com/isaacg1/pyth/blob/master/doc.txt#L92',
    'http://ftp.gnu.org/non-gnu/nethack/nethack-3.4.0.tar.gz.back-RSN.README'
].map(B).join('').length

```

---
Tags: kolmogorov-complexity, restricted-source, brainfuck, metagolf, code-generation
---


title: How do I craft that?

text:
# Question
Title: How do I craft that?
There are 21 items in Minecraft that you can craft using only wood and items crafted from wood:

> axe
> boat
> bowl
> button
> chest
> crafting table
> door
> fence
> gate
> hoe
> ladder
> pickaxe
> planks
> pressure plate
> shovel
> sign
> slab
> stairs
> stick
> sword
> trapdoor

This list assumes that the 6 different types of wooden planks/slabs/doors/etc. all count as the same item. Another way to think of it is to assume you only have access to one type of wood.

Each of these 21 items has a different crafting recipe. We'll represent each of these recipes as a 2×2 or 3×3 grid of the characters `.WPS`. The `.` is an empty crafting slot, `W` is for wood, `P` is for wood planks, and `S` is for sticks. No other characters are needed for these particular items.

For example, this is the recipe for a chest:

```
PPP
P.P
PPP

```

**Challenge**

Write a program that takes in the name of one of our 21 items, exactly as it appears above, and prints a valid crafting recipe for that item.

Crafting recipes are translation invariant, so if the input is `fence`, both of these are valid:

```
PSP
PSP
...
```

```
...
PSP
PSP
```

If a recipe fits in a 2×2 grid, you can output it in a 2×2 or 3×3 grid. e.g. `stick`:

```
.P
.P
```

```
...
.P.
.P.
```

Recipes can also be mirrored horizontally (around a vertical line of symmetry), though this only makes a difference for the axe, hoe, and stairs. e.g. `hoe`:

```
.PP
.S.
.S.
```

```
PP.
.S.
.S.
```

So outputting any recipe that fits in the grid and has the correct shape (ignoring translation and mirroring) is what your program needs to do. These are all the recipes that the official game will recognize. (Note that recipes cannot be rotated or mirrored vertically.)

**Details**

* Take input from stdin or the command line. You can assume the input is always valid. Requiring quotes around input (e.g. `"chest"`) is fine.
* Output to stdout (or closest alternative) with an optional trailing newline.
* The shortest submission in bytes wins.

**Example**

Here's a list of all inputs and sample outputs:

```
axe
PP.
SP.
S..

boat
P.P
PPP
...

bowl
P.P
.P.
...

button
P.
..

chest
PPP
P.P
PPP

crafting table
PP
PP

door
PP.
PP.
PP.

fence
PSP
PSP
...

gate
SPS
SPS
...

hoe
PP.
S..
S..

ladder
S.S
SSS
S.S

pickaxe
PPP
.S.
.S.

planks
W.
..

pressure plate
PP
..

shovel
P..
S..
S..

sign
PPP
PPP
.S.

slab
PPP
...
...

stairs
P..
PP.
PPP

stick
P.
P.

sword
P..
P..
S..

trapdoor
PPP
PPP
...

```

# Answer
> 15 votes
# CJam, ~~100~~ ~~96~~ ~~94~~ 91 bytes

```
"+WcbKF AQH;_{GM8Lyf=_tmTn"141bDb3/l72b970%={Z"O>HVa=4a"98bZb+"P.SW"f=3/=}%N*

```

StackExchange mangles unprintables, so rather than copying and pasting here is the permalink. Additionally, here's the test program.

*(Thanks to @Optimizer for telling me about `f` and @MartinBüttner for telling me about CJam's modulo indexing.)*

Cygwin's `hexdump`:

```
0000000 0122 2b1e 571a 6308 621f 4b05 2046 5141
0000010 1608 1848 5f3b 1115 1d7b 4d47 4c38 6679
0000020 5f3d 6d74 0c54 226e 3431 6231 6244 2f33
0000030 376c 6232 3739 2530 7b3d 225a 1b4f 483e
0000040 6156 343d 2261 3839 5a62 2b62 5022 532e
0000050 2257 3d66 2f33 7d3d 4e25 002a
000005b

```

## Explanation

To construct the recipes, we use 13 different rows (also listed are explanations why this is minimal):

```
0    W..    (required by planks)
1    ...    (required by many)
2    .PP    (required by many)
3    PPP    (required by chest)
4    .P.    (required by bowl)
5    ..P    (required by stairs)
6    S.S    (required by ladder)
7    SSS    (required by ladder)
8    .S.    (required by sign)
9    .SP    (required by axe)
10   P.P    (required by bowl)
11   PSP    (required by fence)
12   SPS    (required by gate)

```

We encode the rows via `Z"O>HVa=4a"98bZb+"P.SW"f=3/`, which gives

```
["W.." "..." ".PP" "PPP" ".P." "..P" "S.S" "SSS" ".S." ".SP" "P.P" "PSP" "SPS"]

```

The first bit `"+WcbKF AQH;_{GM8Lyf=_tmTn"141bDb3/` encodes the recipes, giving

```
[[3 3 8] [1 0 0] [1 0 0] [3 8 8] [1 3 3] [2 8 8] [6 7 6] [1 0 0] [1 10 3] [1 1 2] [2 2 2] [1 11 11] [1 1 4] [1 0 1] [1 10 4] [2 9 8] [3 10 3] [1 2 2] [4 8 8] [1 4 4] [1 1 3] [1 12 12] [4 4 8] [5 2 3]]

```

Note how the first entry is `[3 3 8]`, which is the recipe for `sign`.

`l72b970%=` reads in the input, then applies some magic to work out which recipe to take from the list. Even though we only have 21 recipes there are 24 in the list — the extra few spots correspond to the `[1 0 0]`s.

After reading the input, picking the recipe and converting the recipe to rows, we put in some newlines `N*` and auto-print.

---

# CJam, ~~89~~ ~~86~~ 83 bytes

```
'W"9=!%)S@*m:@DQzk?V$%qyR55AmVEpPNW}"132b3b"P.S"f=+3/3/l57b5342%24%(=N*

```

... it turns out that hardcoding all the outputs does a bit better in CJam. I'm pretty disappointed.

Once again we have some unprintables so here's the permalink and test program.

Cygwin's `hexdump`:

```
0000000 5727 0222 3d39 1021 2925 531e 2a40 6d0b
0000010 403a 1844 7a51 3f6b 2456 7125 5279 3506
0000020 4135 046d 1a56 7045 1550 164e 1057 7d01
0000030 3122 3233 3362 2262 2e50 2253 3d66 332b
0000040 332f 6c2f 3735 3562 3433 2532 3432 2825
0000050 4e3d 002a
0000053

```

## Explanation

The outputs are encoded using base 3, with the lone `W` being tacked onto the front before the string is split into 3s to give rows, and the rows are split into groups of 3s to give recipes.

Like above, base converting and modulo magic is used to select the recipe. There are 22 recipes (one unused) but we need to take modulo 24, so we actually need to explicitly specify `24%` this time rather than relying on modulo indexing.

# Answer
> 6 votes
# JavaScript (ES6), 235 ~~241 262~~

**Edit** Abusing even more of the rule that input is always valid: there is just 1 item that requires W, and that can be special cased. So the output grid is encoded as 9 digit base 3 numbers.

235 bytes with I/O via popup.

```
w=prompt();
"926a722boa182bo2b19520ch224c6056d644f448g764h7651l2294pi8pr758sh2915si26sl19172sta56st785s728t"
.replace(/(\d+)(\D+)/g,(c,p,m)=>w.search(m+z)||[for(c of'11\n11\n111')z+='.SP'[~~p%3]+(p/=3,-c?'':c)],z='');
alert(&&z||'W.\n..')

```

221 bytes as a testable function.

```
F=w=>"926a722boa182bo2b19520ch224c6056d644f448g764h7651l2294pi8pr758sh2915si26sl19172sta56st785s728t"
.replace(/(\d+)(\D+)/g,(c,p,m)=>w.search(m+z)||[for(c of'11\n11\n111')z+='.SP'[~~p%3]+(p/=3,-c?'':c)],z='')&&z||'W.\n..'

```

Output always as 3x3 grid. With 4 available output symobols, the grid is encoded as a 3x3x2 (18) bit number. And as the input have to be always valid, the string are stored truncated to the bare minimum.

**Test** In Firefox/FireBug console

```
;["axe", "boat", "bowl", "button", "chest", "crafting table", "door",
 "fence", "gate", "hoe", "ladder", "pickaxe", "planks", "pressure plate",
 "shovel", "sign", "slab", "stairs", "stick", "sword", "trapdoor"]
.forEach(v=>console.log(v+'\n'+F(v)))

```

*Output*

```
axe
PP.
SP.
S..

boat
P.P
PPP
...

bowl
P.P
.P.
...

button
P..
...
...

chest
PPP
P.P
PPP

crafting table
PP.
PP.
...

door
PP.
PP.
PP.

fence
PSP
PSP
...

gate
SPS
SPS
...

hoe
PP.
S..
S..

ladder
S.S
SSS
S.S

pickaxe
PPP
.S.
.S.

planks
W.
..

pressure plate
PP.
...
...

shovel
P..
S..
S..

sign
PPP
PPP
.S.

slab
PPP
...
...

stairs
P..
PP.
PPP

stick
P..
P..
...

sword
P..
P..
S..

trapdoor
PPP
PPP
...

```

# Answer
> 2 votes
# Python, 305 bytes

```
n=2**(23-hash(raw_input())/535366%24);print "W..\n...\n..." if n==1024 else "\n".join(["".join(['P' if [16706041,9740732,7635081,7399784,5267501,7372808,57344,57344,49152][j+i*3]&n==n else 'S' if [6,2097152,6,131078,10748162,6,131138,9699584,2][j+i*3]&n==n else '.' for j in range(3)]) for i in range(3)])

```

## Explanation

```
# Compute a unique number for each item.
# 535366 and 24 are precalculated values that were bruteforced.
n = 23 - hash(raw_input()) / 535366 % 24

# Use precalculated tables that represent which ingredient in this recipe of
# an item. The nth bit of p[0] will be set if the first ingredient of the item
# associated with the unique number n is some planks. It works the same for s.
p = [16706041,9740732,7635081,7399784,5267501,7372808,57344,57344,49152]
s = [6,2097152,6,131078,10748162,6,131138,9699584,2]

# Handle planks differently, as it is the only one using wood.
if n == 10:
    print "W..\n...\n..."
else:
    for i in xrange(3):
        line = ""
        for j in xrange(3):
            # Now we can check if the ingredient is some planks...
            if p[j + i * 3] & 1 << n == 1 << n:
                line += 'P'
            # ...or if it is some sticks...
            elif s[j + i * 3] & 1 << n == 1 << n:
                line += 'S'
            # ...or if it is simply empty.
            else:
                line += '.'
        print line

```

## Comment

This code surely isn't the tiniest but it works just fine. I'm satisfied. :)

# Python, 282 bytes

```
n=hash(raw_input())/808789215%21;print "\n".join(["P.PPPP...P..S..S..PP.......PP.PP....P........SPSSPS...PPPPPP.S.PP.PS..S.W........PPPPPP...PP..S..S.P..PP.PPPS.SSSSS.SPPP.S..S.PPP......P..P..S..PPPP.PPPPPSPPSP...PP.PP.PP.P..P.....P.P.P...."[9*n+i*3:9*n+(i+1)*3] for i in range(3)])

```

Using the same technique to generate an unique identifier but directly looking up the recipe in an array. It is a lot simpler and a little more compact than my first code.

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


title: The Urinal Protocol

text:
# Question
Title: The Urinal Protocol
## Background

The so-called "Urinal Protocol", describing the order in which individual urinals are picked in a men's bathroom, has been discussed in multiple places. One version is given in this xkcd blog post. This question concerns a slight variation:

> **Arrangement**: n urinals in a line.
> **Protocol**: each new person selects one of the urinals most distant from those already in use.

Note that this places *no* restrictions on which urinal is picked by the first person.

**Update**: The sequence of the number of different ways in which n people can select n urinals starts with 1, 2, 4, 8, 20... Note that this *not* the same as OEIS A095236, which describes slightly stricter restrictions than in this question.

## Task

Given an integer n between 0 and 10, output (in any order) all the possible orderings in which n people can occupy n urinals. Each ordering should be printed as the final arrangement: a sequence of digits representing the people (1-9 for the first 9 people, 0 for the tenth), starting from the leftmost urinal, with *optional* non-alphanumeric separators between (but not before or after) the digits. For example, the following outputs are both valid:

```
>> 3
132
213
312
231

>> 4
1|3|4|2
1|4|3|2
3|1|4|2
4|1|3|2
2|3|1|4
2|4|1|3
2|3|4|1
2|4|3|1

```

You may write a program or function, taking input via STDIN (or closest alternative), command-line argument or function argument. Results should be printed to STDOUT (or closest alternative).

## Scoring

Shortest code wins. Standard terms & conditions apply.

# Answer
# Pyth, ~~53~~ 51

```
MhSm^-dG2HjbmjdmehxkbQusmm+dkfqgTdeSmgbdQUQGUtQm]dQ

```

This is an iterative approach. Given a possible partially filled in ordered sets of locations, we find all the optimal further locations, then generate the corresponding location list, and repeat.

Results are generated in the form `[<first person's location>, <second person's location> ...]`, then this is transformed into the desired format. `MhSm^-dG2H` defines a helper function which finds the minimum distances from a given stall to an occupied stall (squared). Amusingly, the separator is free.

Example run.

Explanation:

First, the helper function `g`, which finds the minimum squared distance between G and any value in H.

```
MhSm^-dG2H
M             def g(G,H): return
 hS           min(                         )
   m     H        map(lambda d:        , H)
    ^-dG2                      (d-G)**2

```

Next, we find the maximum over urinal locations of the minimum squared distance between that urinal and any occupied urinal:

(`Q` is the input.)

```
eSmgbdQ
eS          max(                                   )
  m   Q         map(lambda b:      , range(len(Q)))
   gbd                       g(b,d)

```

`d` in this case is the list of occupied urinals, while `b` iterates over urinal locations.

Next, we find all urinal locations whose minimum squared distance from the nearest occupied urinal is equal to the maximum value found above.

```
fqgTdeSmgbdQUQ
f           UQ    filter(lambda T:                             , range(len(Q)))
 qgTd                             g(T,d) ==
     eSmgbdQ                                <value found above>

```

Next, we will generate the urinal location lists created by adding the urinal locations found above to `d`. We will do this for each previous list of urinal locations, thus extending the lists from length `N` to `N+1`. `G` is the list of legal lists of occupied urinal locations of a given length.

```
smm+dkfqgTdeSmgbdQUQG
sm                  G    sum(map(lambda d:                               ,G)
  m+dk                                   map(lambda k:d+[k],            )
      fqgTdeSmgbdQUQ                                        <above list>

```

Next, we will apply the above expression repeatedly, to generate the complete list of lists of occupied urinal locations. `u`, the reduce function, does exactly this, as many times as there are elements in its second argument.

```
usmm+dkfqgTdeSmgbdQUQGUtQm]dQ
usmm+dkfqgTdeSmgbdQUQG           reduce(lambda G,H: <the above expression)
                      UtQ        repeat Q-1 times
                         m]dQ    starting with [[0], [1], ... [Q-1]].

```

Convert from the above representation, which goes `[<1st location>, <2nd location>, ... ]`, to the desired output form, `[<person in slot 1>, <person in slot 2>, ... ]`. Then, the output form is joined into the output string and printed. Printing is implicit.

```
jbmjdmehxkbQ
jbm             '\n'.join(map(λ k:                                    ,<above>)
   jdm     Q                      ' '.join(map(λ b:                ,Q)
        xkb                                        b.index(k)
      eh                                                     +1 %10

```
> 11 votes

# Answer
# Pyth, 75 71 67

```
DcGHFk_UQJf!s:GeS,0-TkhS,h+TklGUQIJRsmcX>G0dhHhHJ)R]Gjbmjdmebkcm0Q0

```

Recursive combinatorial solution.

It's a fairly direct translation from this Python solution:

```
N = int(input())

def gen(l, p):
    for d in reversed(range(N)):
        s = []
        for i in range(N):
            if not sum(l[max(0,i-d):min(i+d+1, len(l))]):
                s.append(i)

        if s:
            r = []
            for possib in s:
                j = l[:]
                j[possib] = p+1
                r += gen(j, p+1)

            return r

    return [l]

print("\n".join(" ".join(str(x % 10) for x in sol) for sol in gen([0] * N, 0)))

```
> 8 votes

# Answer
# C, ~~929~~ 878 bytes

This one's a monster, guys. Sorry.

```
typedef unsigned long U;typedef unsigned char C;U f(int*u,n){C c[8],a[8];*(U*)(&c)=-1;int i,b=0,l=-9,s=-2,f=0,d;for (i=0; i<n; i++) {if (!u[i]&&s<0)s=i,l=0;if(!u[i])l++;if(u[i]&&s>=0){if(!s)l=2*l-1;d=(l-1)/2;if(b<d)*(U*)(a)=0,*(U*)(c)=-1,*c=s,*a=l,f=1,b=d;else if(b==d)c[f]=s,a[f++]=l;s=-1;}}if(s>=0&&l){l=2*l-1;d=(l-1)/2;if(b<d)*(U*)(c)=-1,*c=s,*a=l,f=1,b=d;else if(b==d)c[f]=s,a[f++]=l;}d=f;for(i=0;i<d;i++){if((c[i]+1)&&c[i]){if(c[i]+a[i]==n)c[i]=n-1;else{if(!(a[i]%2))c[f++]=b+c[i]+1;c[i]+=b;}}}return*(U*)c;}void P(int*u,n,i,c,m){for(i=0;i<n;i++){if(!u[i])c++;if(u[i]>m)m=u[i];}if(!c){for(i=0;i<n;i++)printf("%d",u[i]==10?0:u[i]);printf("\n");}else{int s[8][n];for(i=0;i<8;i++)for(c=0;c<n;c++)s[i][c]=u[c];U t=f(u,n);C*H=&t;for(i=0;i<8;i++)if((C)(H[i]+1))s[i][H[i]]=m+1,P(s[i],n,0,0,0);}}void L(n){int u[n],i,j;for(i=0;i<n;i++){for(j=0;j<n;j++)u[j]=j==i?1:0;P(u,n,0,0,0);}}

```

Defines 3 functions, `f(int*,int)`,`P(int*,int,int,int,int)`, and `L(int)`. Call `L(n)`, and it outputs to STDOUT.

Output for `n=5`:

```
14352
15342
31452
31542
41352
51342
41532
51432
24153
25143
34152
35142
23415
23514
24513
25413
24315
25314
24351
25341

```

**Update:** I removed separators and fixed up the code. The old code not only failed for n=7+, but failed to output anything at all for n=10 (oops!). I've more thoroughly tested this bunch. It now supports input of up to n=13 (though the `"%d"` should be changed to `"%x"`so it prints in hexadecimal). The size of input depends on `sizeof(long)` and it is assumed to be `8` in practice.

Here's some explanation of how it works, and why such an odd restriction exists:

These were used a lot, so we define them to save a couple bytes:

`typedef unsigned long U; typedef unsigned char C;`

Here is `f`:

```
U f(int*u,n){
    C c[8],a[8];
    *(U*)(&c)=-1;
    int i,b=0,l=-9,s=-2,f=0,d;
    for (i=0; i<n; i++) {
        if (!u[i]&&s<0)
            s=i,l=0;
        if(!u[i])
            l++;
        if(u[i]&&s>=0){
            if(!s)
                l=2*l-1;
            d=(l-1)/2;
            if(b<d)
                *(U*)(a)=0,
                *(U*)(c)=-1,
                *c=s,
                *a=l,
                f=1,
                b=d;
            else if(b==d)
                c[f]=s,a[f++]=l;
            s=-1;
        }
    }
    if(s>=0&&l){
        l=2*l-1;
        d=(l-1)/2;
        if(b<d)
            *(U*)(c)=-1,
            *c=s,
            *a=l,
            f=1,
            b=d;
        else if(b==d)
            c[f]=s,a[f++]=l;
    }
    d=f;
    for(i=0;i<d;i++){
        if((c[i]+1)&&c[i]){
            if(c[i]+a[i]==n)
                c[i]=n-1;
            else{
                if(!(a[i]%2))
                    c[f++]=b+c[i]+1;
                c[i]+=b;
            }
        }
    }
    return*(U*)c;
}

```

`f` takes an array of integers of size `n`, and `n` itself. The only clever bit here is that it returns an `unsigned long`, which is converted into a `char[8]` by the calling function. Each character in the array is thus set either to `0xFF` or to an index pointing to a valid urinal for the next person. For `n<10`, we never need more than 5 bytes to hold every valid urinal the next person can use.

Here is `P`:

```
void P(int*u,n,i,c,m){
    for(i=0;i<n;i++){
        if(!u[i])c++;
        if(u[i]>m)m=u[i];
    }
    if(!c){
        for(i=0;i<n;i++)
            printf("%d",u[i]==10?0:u[i]);
        printf("\n");
    }
    else{
        int s[8][n];
        for(i=0;i<8;i++)
            for(c=0;c<n;c++)
                s[i][c]=u[c];
        U t=f(u,n);
        C*H=&t;
        for(i=0;i<8;i++)
            if((C)(H[i]+1))
                s[i][H[i]]=m+1,P(s[i],n,0,0,0);
    }
}

```

`P` takes an array `u` of size `n` wherein exactly one element is set to `1`, and the rest are `0`. It then finds and prints every permutation possible recursively.

Here is `L`:

```
void L(n){
    int u[n],i,j;
    for(i=0;i<n;i++){
        for(j=0;j<n;j++)
            u[j]=j==i?1:0;
        P(u,n,0,0,0);
    }
}

```

`L` simply calls `P` `n` times with different starting positions each time.

For the interested, this (less golfed) `f` will generate the sequence in A095236.

```
U f(int*u,n) {
    C c[8];
    *(U*)(&c) = -1;
    int i,b=0,l=-10,s=-2,f=0,d;
    for (i=0; i<n; i++) {
        if (!u[i]&&s<0) {
            s=i,l=0;
        }
        if(!u[i]){
            l++;
        }
        if (u[i]&&s>=0) {
            if (!s) {
                l=2*l-1;
            }
            if (b<l) {
                *(U*)(&c)=-1;
                c[0]=s;
                f=1;
                b=l;
            }
            else if (b==l)
                c[f++]=s;
            s=-1;
        }
    }
    if (s>=0&&l) {
        l=2*l-1;
        if (b<l) {
            *(U*)(&c)=-1;
            c[0]=s;
            f=1;
            b=l;
        }
        else if (b==l)
            c[f++]=s;
    }
    d=f;
    for (i=0; i<d; i++) {
        if ((c[i]+1)&&c[i]) {
            if (c[i]+b==n) {
                c[i]=n-1;
            }
            else{
                if (!(b%2)) {
                    c[f++]=(b-1)/2+c[i]+1;
                }
                c[i]+=(b-1)/2;
            }
        }
    }
    return *(U*)c;
}

```
> 5 votes

# Answer
# Python 2, 208

```
n=input()
r=range(n)
l=[0]*n
def f(a,d=-1):
 if a>n:print''.join(l);return
 for i in r:
  t=min([n]+[abs(i-j)for j in r if l[j]])
  if t==d:p+=[i]
  if t>d:p=[i];d=t
 for i in p:l[i]=`a%10`;f(a+1);l[i]=0
f(1)

```

Recursive approach.
> 4 votes

# Answer
# JavaScript (ES6) 153 ~~160 169~~

**Edit** Using Math.min to find (of course) the max distance: streamlined code and 16 bytes saved.

Recursive search, can work with n \> 10, just remove % 10 (and be prepared to wait while the console unrolls all its output).

I use a single array to store the slot in use (positive numbers) or the current distance from the nearest slot (negative numbers so `<` and `>` are swapped in code).

```
F=n=>{(R=(m,d,t,x=Math.min(...d=m?
  d.map((v,i)=>(c=i<t?i-t:t-i)?v<c?c:v:m%10)
  :Array(n).fill(-n)))=>
x<0?d.map((v,i)=>v>x||R(-~m,d,i)):console.log(d+[]))()}

```

**Ungolfed**

```
F=n=>{
  var R=(m, // current 'man', undefined at first step
   d, // slot array
   t // current position to fill
  ) =>
  {
    if (m) // if not at first step
    {
      d[t] = m % 10; // mark slot in use, (10 stored as 0 )
      d = d.map((v,i) => { // update distances in d[]
        var c = i<t ? i-t : t-i; // distance from the current position (negated)
        return v < c ? c : v; // change if less than current distance
      });
    }
    else
    {
      d = Array(n).fill(-n) // fill distance array with max at first step
      // negative means slot free, value is the distance from nearest used slot
      // >= 0 means slot in use by man number 1..n
    }
    var x = Math.min(...d);
    if ( x < 0 ) // if there is still any free slot
    {
      d.forEach((v,i) => { // check distance for each slot
        if (v <= x) // if slot is at max distance, call recursive search
          R(-~m, [...d], i) // ~- is like '+1', but works on undefined too
      });
    }
    else
    {
      console.log(d+[]); // no free slot, output current solution
    }
  }

  R() // first step call
}

```

**Test** In Firefox/FireBug console

```
F(5)

```

> 1,4,3,5,2
> 1,5,3,4,2
> 3,1,4,5,2
> 3,1,5,4,2
> 4,1,3,5,2
> 5,1,3,4,2
> 4,1,5,3,2
> 5,1,4,3,2
> 2,4,1,5,3
> 2,5,1,4,3
> 3,4,1,5,2
> 3,5,1,4,2
> 2,3,4,1,5
> 2,3,5,1,4
> 2,4,3,1,5
> 2,5,3,1,4
> 2,4,5,1,3
> 2,5,4,1,3
> 2,4,3,5,1
> 2,5,3,4,1
> 4 votes

# Answer
# Mathematica, ~~123~~ 104

```
f[n_,s_:{}]:=If[Length@s<n,f[n,s~Join~{#}]&/@MaximalBy[Range@n,Min@Abs[#-s]&];,Print@@Ordering@s~Mod~10]

```
> 2 votes

# Answer
## MATLAB, 164

```
function o=t(n),o=mod(r(zeros(1,n)),10);function o=r(s),o=[];d=bwdist(s);m=max(d);J=find(d==m);if~d,o=s;J=[];end,n=max(s)+1;for j=J,o=[o;r(s+n*(1:numel(s)==j))];end

```
> 1 votes

# Answer
# Perl, 174

Not very short, but fun. I'm not counting `use feature 'say';` towards the byte total.

```
$n=pop;@u="_"x$n." "x$n."_"x$n;for$p(1..$n){@u=map{my@r;for$x(reverse 0..$n){
s/(?<=\D{$x}) (?=\D{$x})/push@r,$_;substr $r[-1],pos,1,$p%10/eg and last;
}@r}@u}y/_//d&&say for@u

```

De-golfed:

```
$n = pop; # Get number of urinals from commandline
@state = ( "_" x $n . " " x $n . "_" x $n );

for my $person (1 .. $n) {
  # Replace each state with its list of possible next states.
  @state = map {
    my @results;
    for my $distance (reverse 0 .. $n) {
      # If there are any spots with at least $distance empty on
      # both sides, then add an entry to @results with the current
      # $person number in that spot, for each spot. Note that this
      # is only used for its side-effect on @results; the modified $_
      # is never used.
      s{
        (?<=\D{$distance})
        [ ]
        (?=\D{$distance})
      }{
        push @results, $_;
        substr $results[-1], pos(), 1, $person % 10;
      }xeg
      # If we found any spots, move on, otherwise try
      # with $distance one lower.
      and last;
    }
    # New state is the array we built up.
    @results;
  } @state;
}

# After adding all the people, remove underscores and print the results
for my $result (@state) {
  $result =~ tr/_//d;
  say $result;
}

```
> 1 votes

# Answer
# Bash, 744 674 bytes

This is still way too long :). I use a string to represent the row of urinals and a flooding algorithm to find the most distant urinals in each phase of recursion. The ungolfed code is almost self-explanatory. The number of urinals is read from keyboard.

Code (golfed):

```
read l;u=----------;u=-${u::$l}-
s(){ u=${u:0:$1}$2${u:$((1+$1))};}
m(){ local u=$1;a=();while :;do [ 0 -ne `expr index - ${u:1:$l}` ]||break;t=$u;y=$u;for i in `seq $l`;do [ ${y:$i:1} = - ]||{ s $(($i-1)) X;s $(($i+1)) X;};done;done;while :;do k=`expr index $t -`;[ 0 != $k ]||break;t=${t:0:$(($k-1))}X${t:$k};if [ 1 -ne $k ]&&[ $(($l+2)) -ne $k ];then a+=($(($k-1)));fi;done;}
e(){ local u f b v;u=$1;f=$2;if [ 1 -eq $l ];then echo 1;return;fi;if [ 1 = $f ];then for i in `seq $l`;do v=$u;s $i 1;e $u 2;u=$v;done;else m $u;b=(${a[@]});if [ 0 -eq ${#b} ];then echo ${u:1:$l};else for i in ${b[@]};do v=$u;s $i $(($f%10));e $u $(($f+1));u=$v;a=(${b[@]});done;fi;fi;}
e $u 1

```

Use:

```
$ source ./script.sh
input number of urinals from keyboard

```

And ungolfed it goes:

```
read l  # read number of urinals
u=----------
u=-${u:0:$l}- #row is two positions longer (it will be helpful when finding the most distant urinals)

# So, for the end, with 6 men, u might look like this:
# -143652-

# subu no fellow_no => set urinal [number] occupied by [fellow_no]
# this is just convenience for resetting a character inside a string
subu(){ u=${u:0:$1}$2${u:$((1+$1))};}

# this will be iterated in longest to find the remotest places:
# -1---3---2- => spreadstep => X1X-X3X-X2X => spreadstep => X1XXX3XXX2X
# see longest() to get more explanation.
spreadstep()
{
    y=$u
    for i in `seq 1 $l`
    do
    if [ "${y:$i:1}" != "-" ]
    then
        subu $(($i-1)) X
        subu $(($i+1)) X
    fi
    done
}

# Find the urinals with the longest distance. It uses spreadstep() - see above.
# -1---3---2- => spreadstep => X1X-X3X-X2X => spreadstep => X1XXX3XXX2X
# ---> last state with free ones was X1X-X3X-X2X ,
#                                     123456789
# free urinals are no. 3 and no. 7 => save them to arr
longest()
{
    local u=$1
    arr=()
    while true
    do
        if [ 0 -eq `expr index - ${u:1:$l}` ]
        then
            break
        fi
        save=$u
        spreadstep
    done

    while true
    do
        index=`expr index $save -`
        if [ 0 == $index ]
        then
            break
        fi

        save=${save:0:$(($index-1))}X${save:$index}
        if [ 1 -ne $index ] && [ $(($l+2)) -ne $index ]
        then
            arr+=($(($index-1)))
        fi
    done
}

# main function, recursively called
# the first fellow may take any of the urinals.
# the next fellows - only those with the longest distance.
placements_with_start()
{
    local u=$1
    local fellow=$2
    if [ 1 -eq $l ] # special case - there is no 2nd fellow, so below code would work incorrect
    then
        echo "1"
        return
    fi
    if [ 1 == $fellow ]       # may take any of urinals
    then
        for i in `seq 1 $l`
        do
            local _u=$u
            subu $i 1                     # take the urinal
            placements_with_start $u 2    # let the 2nd fellow choose :)
            u=$_u
        done
    else
        longest $u   # find the ones he can take
        local _arr=(${arr[@]})
        if [ 0 -eq ${#_arr} ]
        then
            echo ${u:1:$l}    # no more free urinals - everyone took one - print the result
        else
            for i in ${_arr[@]}
            do
                local _u=$u
                subu $i $(($fellow % 10))                # take urinal
                placements_with_start $u $(($fellow+1))  # find locations for for next fellow
                u=$_u
                arr=(${_arr[@]})
            done
        fi
    fi
}

placements_with_start $u 1

```
> 1 votes

# Answer
# C, 248 bytes

This code uses a recursive algoritm to generate the desired outcome.

```
void q(char*f,int l,int d,char*o){char*c=f;while(f<c+l){if(!*f){sprintf(o+4*d,"%03i,",f-c);*f=1;q(c,l,d+1,o);*f=0;}f++;}if(d+1==l){o[4*d+3]=0;printf("%s\n",o);}}int main(int i,char**v){int k=atoi(v[1]);char*c=calloc(k,5),*o=c+k;q(c,k,0,o);free(c);}

```

---

*Expanded:*

```
void printperms(char* memory,int length,int offset,char*output)
{
    char*temp_char=memory;
    while(memory<temp_char+length)
    {
        if(!*memory)
        {
            sprintf(output+4*offset,"%03i,",memory-temp_char);
            *memory=1;
            printperms(temp_char,length,offset+1,output);
            *memory=0;
        }
        memory++;
    }
    if(offset+1==length)
    {
        output[4*offset+3]=0;
        printf("%s\n",output);
    }
}

int main(int i,char**v)
{
    int argument=atoi(v[1]);
    char*t=calloc(argument,5),*output=t+argument;
    printperms(t,argument,0,output);
    free(t);
}

```
> 1 votes

---
Tags: code-golf, combinatorics
---


# Question
Title: Sort all the pixels of an image by the number of occurrences
## Input

The name of a file in the raster graphics format of your choice. The chosen format must support at least 8 bits per channel and 3 channels.

## Output

A file in the same format, with the same dimensions and pixels as the first, but whose pixels are grouped in descending order of the number of times they occur, sorted from left-to-right, top-to-bottom.

* If certain colours of pixels appear the same number of times, their order is unspecified.
* You must not overwrite the input file (use a different file name for the output).
* Any and all third-party image processing libraries are permitted.

## Example

Will give output similar to:

Especially in the lower parts of the image some variation may occur, due to different tie breaking between colours of equal frequency.

# Answer
> 4 votes
# J, ~~94~~ 81 bytes

A function taking the name of a PNG file (with no transparency channel) and writing the result in the input filename prepended by "o".

```
f=.3 :0
load'graphics/png'
(($a)$#/|:\:~(#,{.)/.~,a=.readpng y)writepng'o',y
)

```

## Method

* Create a list of every color-number and the number of it's appearances
* Sort list by number of it's appearances
* Multiplicate every color-number equal it's appearances
* Reshape the new list to the shape of the original image

# Answer
> 6 votes
# Mathematica, ~~125~~ 123 bytes

```
Export["a"<>#,i=ImageData@Import@#;Image@ArrayReshape[Join@@ConstantArray@@@SortBy[Tally[Join@@i],-Last@#&],Dimensions@i]]&

```

This defines an unnamed function which takes the file name in any common image format and writes the result to the a file with the same name but prepended with `a`. The result looks a bit different from the OP's, since Mathematica's `SortBy` breaks ties by default sort order, so the bottom bits where loads of ties occur look a bit neater:

The implementation itself is really straightforward:

* `ImageData` to get a grid of colour values.
* `Join` to flatten the array.
* `Tally` to count the occurrence of each colour.
* `SortBy[...,-Last@#&]` to sort by frequencies from highest to lowest.
* `ConstantArray` and `Join` to expand the tallies again.
* `ArrayReshape` to recover the original image shape (obtained with `Dimensions`).
* `Image` to convert the data back to an image object.

FYI, 22 bytes are used on file I/O. An equivalent version that takes and returns an image object comes in at 103 bytes:

```
(i=ImageData@#;Image@ArrayReshape[Join@@ConstantArray@@@SortBy[Tally[Join@@i],-Last@#&],Dimensions@i])&

```

# Answer
> 4 votes
# Python2/PIL, ~~244~~ ~~226~~ ~~225~~ ~~223~~ ~~222~~ ~~202~~ ~~186~~ ~~182~~ ~~170~~ 159

```
from PIL.Image import*
s=raw_input();i=open(s);g=list(i.getdata());i.putdata(sum([[c[1]]*-c[0]for c in sorted((-g.count(r),r)for r in set(g))],[]));i.save(2*s)

```

### Changelog

```
<p><b>Edit 1:</b> saved 18 bytes with new algorithm.</p>
<p><b>Edit 2:</b> saved 1 byte with remembering that Python 2 has int division without <code>from __future__ import division</code>. Whoops.</p>
<p><b>Edit 3:</b> saved 2 bytes by swapping <code>cmp</code> for <code>key</code>.</p>
<p><b>Edit 4:</b> saved 1 byte by clever unpacking. <code>w=i.size[0]</code> -> <code>w,h=i.size</code></p>
<p><b>Edit 5:</b> moved <code>list()</code> to an earlier position, drastically improving runtime. No length change.</p>
<p><b>Edit 6:</b> saved 20 bytes by remembering that there is also sequence sorting in Python. Probably slower, but also produces images more like the the Mathematica one.</p>
<p><b>Edit 7:</b> saved 16 bytes by changing <code>putpixel</code> to a list and <code>putdata</code>. Under 200!</p>
<p><b>Edit 8:</b> saved 4 bytes by changing <code>range(...)</code> to <code>...*[0]</code> since we don't need the values.</p>
<p><b>Edit 9:</b> saved 12 bytes by converting the <code>for</code> loop to a <code>sum</code>.</p>
<p><b>Edit 10:</b> saved 11 bytes by noticing that the image size doesn't matter anymore (since edit 7). Whoops v2.0.</p>
```

## Shorter version by stokastic, 123

```
from PIL.Image import*
s=raw_input();i=open(s);d=list(i.getdata());i.putdata(sorted(d,key=lambda D:d.count(D)));i.save(2*s)

```

Well, let's at least try, even though it's already beaten.

It's extremely slow, Panda processed for several minutes on my laptop.

Saves with a filename with the original filename repeated twice.

# Answer
> 2 votes
# Python, 1197 bytes

```
# -*- coding: utf-8 -*-
from __future__ import division
from collections import Counter
import png
from sys import argv,exit
script,file_name,output_file_name=argv
def group(s,n):
    return zip(*[iter(s)]*n)
def flatten(list_of_lists):
    result=[]
    for lst in list_of_lists:
        result.extend(lst)
    return result
def group_list(old_list,tuples_per_list):
    new_list=[]
    i=1
    appended_row=[]
    for item in old_list:
        appended_row.extend(flatten([item]))
        if i==tuples_per_list:
            new_list.append(appended_row)
            i=1
            appended_row=[]
        else:
            i+=1
    return new_list
input_image=png.Reader(file_name)
image_data=input_image.read()
width=image_data[0]
height=image_data[1]
pixels=list(image_data[2])
if image_data[3]["alpha"]:
    ints_per_colour=4
elif image_data[3]["greyscale"]:
    ints_per_colour=2
else:
    ints_per_colour=3
colours=Counter(colour for row in pixels for colour in group(row,ints_per_colour)).most_common()
pixel_list=flatten([element]*count for element,count in colours)
ordered_rows=group_list(pixel_list,width)
f=open(output_file_name,"wb")
png_object=png.Writer(width,height,greyscale=image_data[3]["greyscale"],alpha=image_data[3]["alpha"])
png_object.write(f,ordered_rows)
f.close()

```

The `png` module I used.

# Answer
> 1 votes
# C# 413

Complete program. Pass the file name on command line, the output is saved in the same format as file "o".

Not using some neat features of linq, like SelectMany and Enumerable.Range, as the program would be cleaner but longer.

```
using System.Collections.Generic;using System.Linq;using System.Drawing;
class P{
static void Main(string[]a){
var d=new Dictionary<Color,int>();var b=new Bitmap(a[0]);
int n,x,y,w=b.Width,h=b.Height;
for (x=w;x-->0;)for(y=h;y-->0;){var p=b.GetPixel(x,y);d[p]=d.ContainsKey(p)?d[p]+1:1;}
y=h;foreach(var q in d.OrderBy(v=>v.Value)){for(n=q.Value;n-->0;){
if(x<=0){x=w;--y;}b.SetPixel(--x, y, q.Key);}}b.Save("o");
}}

```

**Readable** formatting courtesy of VS2010

```
using System.Collections.Generic;
using System.Linq;
using System.Drawing;

class P
{
    static void Main(string[] a)
    {
        var d = new Dictionary<Color, int>();
        var b = new Bitmap(a[0]);
        int n,x,y,w = b.Width, h=b.Height;

        for (x = w; x-- > 0;)
            for (y = h; y-- > 0;)
            {
                var p = b.GetPixel(x, y);
                d[p] = d.ContainsKey(p) ? d[p]+1 : 1;
            }
        y = h;
        foreach (var q in d.OrderBy(v => v.Value))
        {
            for (n = q.Value; n-- > 0; )
            {
                if (x <= 0)
                {
                    x = w;
                    --y;
                 }
                 b.SetPixel(--x, y, q.Key);
            }
        }
        b.Save(a[0]+".");
    }
}

```

# Answer
> 1 votes
# Python 2 : 191 bytes

Here's my attempt. I figured I might be able to save some space by using `Counter`, but it didn't end up as small as Pietu1998's answer.

```
from collections import Counter
from PIL import Image
i=Image.open(raw_input())
s=reduce(lambda x,y:x+y,map(lambda(a,b):[a]*b,Counter(i.getdata()).most_common()))
i.putdata(s)
i.save("o.png")

```

## Output from Panda

---
Tags: code-golf, graphical-output, sorting, image-processing
---