# Question
Title: The Rule of Thumb for Title Capitalization
According to this site a general rule recommended by *The U.S. Government Printing Office Style Manual* is

> Capitalize all words in titles of publications and documents, except a, an, the, at, by, for, in, of, on, to, up, and, as, but, or, and nor.

This might not be true as I'm unable to find such a recommendation in the Style Manual, but let's use this rule anyway.

---

**The Challenge**

Given an input string consisting of lower case words delimited by spaces, output the capitalization of the string according to the following rules

* The first and last word is capitalized.
* All other words are capitalized, except *a*, *an*, *the*, *at*, *by*, *for*, *in*, *of*, *on*, *to*, *up*, *and*, *as*, *but*, *or*, and *nor*.

The input string will contain at least one word and each word contains at least one letter and only characters from `a` to `z`.

This is a code golf challenge, so try to use as few bytes as possible in the language of your choice. You may write a full program or a function to accomplish the task.

**Testcases**

```
"the rule of thumb for title capitalization" -> "The Rule of Thumb for Title Capitalization"
"programming puzzles and code golf" -> "Programming Puzzles and Code Golf"
"the many uses of the letter a" -> "The Many Uses of the Letter A"
"title" -> "Title"
"and and and" -> "And and And"
"a an and as at but by for in nor of on or the to up" -> "A an and as at but by for in nor of on or the to Up"
"on computable numbers with an application to the entscheidungsproblem" -> "On Computable Numbers With an Application to the Entscheidungsproblem"

```

# Answer
## Python 2, 118 bytes

Look ma, no regex!

```
for w in`input()`.split():print[w.title(),w][`w`in"'a'an'and'as'at'the'by'but'for'nor'in'of'on'or'to'up'"].strip("'"),

```

Input must be wrapped in quotes. Output has a trailing space and no trailing newline (I assume that's okay). Verify all test cases on Ideone.

### Explanation

Let's take the input `a or an` as our example.

Using Python 2's ``x`` shortcut for `repr`, we wrap the input in single quotes: `'a or an'`. Then we split on whitespace and iterate over the words.

Inside the loop, we take the `repr` *again*. For the first and last words, this gives `"'a"` and `"an'"`. For other words, it gives `'or'`. We want to avoid capitalizing words if they fit the latter pattern and are in the short-words list. So we can represent the word list as the string `"'a'an'...'up'"` and know that the `repr` of any short word will be a substring.

``w` in "..."` gives a boolean value, which we can treat as `0` or `1` for the purposes of indexing into the list `[w.title(), w]`. In short, we title-case the word if it is at the beginning, at the end, or not in the list of short words. Otherwise, we leave it alone. Fortunately, `title()` still works as expected with input like `'a`.

Finally, we strip any single quotes from the word and print it with a trailing space.
> 11 votes

# Answer
# 05AB1E, ~~68~~ 61 bytes

Saved 7 bytes thanks to *Adnan*

```
™ð¡Dg<UvyN__NXQ_“a€¤€€€›€‹€‡€†€‚€‰€„€¾€ƒ€œ€³€—š¯“#™yå&&il})ðý

```

Try it online!

**Explanation**

`“a€¤€€€›€‹€‡€†€‚€‰€„€¾€ƒ€œ€³€—š¯“` is a dictionary string translated as `a an the at by for in of on to up and as but or nor`.

```
™                          # title case input string
ð¡                         # split on spaces
Dg<U                       # store index of last word in X

vy                         # for each word
  N__                      # is it not first index?
     NXQ_                  # is it not last index
         “...“             # the compressed string
              #            # split on spaces
               ™           # convert to title case
                yå         # is current word in this list?
                  &&       # and the 3 previous conditions together
                    il     # if all are true, convert to lower case
                      }    # end loop
)ðý                        # wrap stack in list and join by spaces

```
> 8 votes

# Answer
# GNU sed ~~81 74~~ 73 Bytes

Includes +1 for -r

```
s/\b./\u&/g
:;s/.(And?|A[st]?|The|By|But|[FN]or|In|O[fnr]|To|Up) /\L&/;t

```

The first line capitalizes the first letter of every word. The second switches all of the required words back to lowercase.

Try it Online!
> 7 votes

# Answer
# Retina, ~~69~~ 66 bytes

Capitalize the first letter of every word, then change the selected words to lowercase if they're not the first or last word. There's a space at the end of the last line.

```
T`l`L`\b.
+T`L`l` (And?|A[st]?|The|By|But|[FN]or|In|O[fnr]|To|Up)

```

**Try it online**

This also works with a `.` instead of the first space.

There are a lot of regexes with the same length, but I can't find a way to trim it anymore...
> 6 votes

# Answer
## JavaScript (ES6), ~~141~~ ~~138~~ ~~135~~ 133 bytes

*Saved 3 bytes thanks to mbomb007*

```
s=>s.replace(/(\w+)( ?)/g,(a,w,n,i)=>i&&n&&/^(a[nst]?|the|by|in|of|on|to|up|and|but|[fn]?or)$/.exec(w)?a:a[0].toUpperCase()+a.slice(1))

```

### Test cases

```
let f =

s=>s.replace(/(\w)(\w*)( ?)/g,(a,l,w,n,i)=>i&&n&&/^(a[nst]?|the|by|in|of|on|to|up|and|but|[fn]?or)$/.exec(l+w)?a:l.toUpperCase()+w+n)

console.log(f("the rule of thumb for title capitalization"));
console.log(f("programming puzzles and code golf"));
console.log(f("the many uses of the letter a"));
console.log(f("title"));
console.log(f("and and and"));
console.log(f("a an and as at but by for in nor of on or the to up"));
console.log(f("on computable numbers with an application to the entscheidungsproblem"));
```
> 3 votes

# Answer
# Jelly, 58 bytes

```
“Ð/ṃƇ¬þṄẊƙ€,⁽ṙƬ®OṪJ"ɦ3×kf3Ṙç%ġu’b26ịØaṣ”z
e€¢¬T;2Ḷ¤
ḲŒtÇ¦K

```

**TryItOnline!** or run all tests

### How?

A compressed string with spaces separating the words would be `47` bytes, splitting it costs `1` byte, for `48` bytes.

Two unseparated compressed strings of the words of length `2` and `3` (with an 'a' on the end of one) respectively would be `40` bytes plus `2` to split each and `1` to join them, for `45` bytes.

One base 250 number as described below is `32` bytes, then `3` to convert to base 26, `3` to index into the lowercase alphabet and `3` to split it on the unused character, `'z'`, for `41` bytes.

So, the lookup for the words not to capitalise:
`“Ð/ṃƇ¬þṄẊƙ€,⁽ṙƬ®OṪJ"ɦ3×kf3Ṙç%ġu’`
was formed like so:

Take those words and join them with a separator:
`s="a an the at by for in of on to up and as but or nor"`

Next label `'a'` as `1`, `'b'` as `2` with the separator as `0`:

```
alpha = ' abcdefghijklmnopqrstuvwxyz'
x = [alpha.index(v) for v in s]
x
[1,0,1,14,0,20,8,5,0,1,20,0,2,25,0,6,15,18,0,9,14,0,15,6,0,15,14,0,20,15,0,21,16,0,1,14,4,0,1,19,0,2,21,20,0,15,18,0,14,15,18]

```

Convert this into a base `26` number (the last letter used is `'y'` plus a digit for the separator, Python code for this is:
`n=sum(v*26**i for i,v in enumerate(x[::-1]))`

Convert that into a base `250` number (using a list for the digits):

```
b=[]
while n:
    n,d = divmod(n,250)
    b=[d]+b
b
[16,48,220,145,8,32,202,209,162,13,45,142,244,153,9,80,207,75,35,161,52,18,108,103,52,205,24,38,237,118]

```

Lookup the characters at those indexes in jelly's codepage:

```
codepage = '''¡¢£¤¥¦©¬®µ½¿€ÆÇÐÑ×ØŒÞßæçðıȷñ÷øœþ !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQR TUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~¶°¹²³⁴⁵⁶⁷⁸⁹⁺⁻⁼⁽⁾ƁƇƊƑƓƘⱮƝƤƬƲȤɓƈɗƒɠɦƙɱɲƥʠɼʂƭʋȥẠḄḌẸḤỊḲḶṂṆỌṚṢṬỤṾẈỴẒȦḂĊḊĖḞĠḢİĿṀṄȮṖṘṠṪẆẊẎŻạḅḍẹḥịḳḷṃṇọṛṣṭụṿẉỵẓȧḃċḋėḟġḣŀṁṅȯṗṙṡṫẇẋẏż«»‘’“”'''
r=''.join(codepage[i-1] for i in b)
r
'Ð/ṃƇ¬þṄẊƙ€,⁽ṙƬ®OṪJ"ɦ3×kf3Ṙç%ġu'

```

(note: since the actual implementation is bijective, if `b` had any `0` digits one would need to carry down first)

The rest:

```
ḲŒtÇ¦K - Main link: title string
Ḳ      - split on spaces
    ¦  - apply to indexes
   Ç   -     given by calling the last link (1) as a monad (with the split title string)
 Œt    -     title case (first letter of each (only) word to upper case)
     K - join on spaces

e€¢¬T;2Ḷ¤ - Link 1, find indexes to capitalise: split title string
e€        - is an element of, for €ach
  ¢       - the result of calling the last link (2) as a nilad
   ¬      - logical not
    T     - get the truthy indexes (indexes of words that are not in the list)
     ;    - concatenate with
        ¤ - nilad followed by link(s) as a nilad
      2Ḷ  - range(2) -> [0,1]
                (we always want to capitalise the first index, 1, and the last index, 0)

“Ð/ṃƇ¬þṄẊƙ€,⁽ṙƬ®OṪJ"ɦ3×kf3Ṙç%ġu’b26ịØaṣ”z - Link 2, make the word list: no arguments
“Ð/ṃƇ¬þṄẊƙ€,⁽ṙƬ®OṪJ"ɦ3×kf3Ṙç%ġu’          - the base 250 number
                                b26       - convert to base 26
                                   ị      - index into
                                    Øa    - lowercase alphabet
                                      ṣ   - split on
                                       ”z - literal 'z' (the separator 0 indexes into `z`)

```
> 3 votes

# Answer
# PHP, 158 Bytes

10 Bytes saved by @Titus

```
foreach($w=explode(" ",$argv[1])as$k=>$v)echo" "[!$k],$k&&$k+1<count($w)&&preg_match("#^(a[snt]?|and|[fn]or|up|by|but|the|to|in|o[rnf])$#",$v)?$v:ucfirst($v);

```

Previous version PHP, 174 Bytes

```
foreach($w=explode(" ",$argv[1])as$k=>$v)$k&&$k+1<count($w)&&in_array($v,[a,an,the,at,by,"for",in,of,on,to,up,"and","as",but,"or",nor])?:$w[$k]=ucfirst($v);echo join(" ",$w);

```
> 2 votes

# Answer
# Java 7, ~~271~~ ~~259~~ 258 bytes

```
String c(String x){String a[]=x.split(" "),s=" ",r=w(a[0])+s;for(int i=0,l=a.length-1;i<l;r+=(!s.matches("^(a[nst]?|the|by|in|of|on|to|up|and|but|[fn]?or)$")|i==l?w(s):s)+" ")s=a[++i];return r;}String w(String w){return(char)(w.charAt(0)-32)+w.substring(1);}

```

**Ungolfed & test code:**

Try it here.

```
class M{
  static String c(String x){
    String a[] = x.split(" "),
           s = " ",
           r = w(a[0]) + s;
    for(int i = 0, l = a.length-1; i < l; r += (!s.matches("^(a[nst]?|the|by|in|of|on|to|up|and|but|[fn]?or)$") | i == l
                                                 ? w(s)
                                                 : s)   + " "){
      s = a[++i];
    }
    return r;
  }

  static String w(String w) {
    return (char)(w.charAt(0) - 32) + w.substring(1);
  }

  public static void main(String[] a){
    System.out.println(c("the rule of thumb for title capitalization"));
    System.out.println(c("programming puzzles and code golf"));
    System.out.println(c("the many uses of the letter a"));
    System.out.println(c("title"));
    System.out.println(c("and and and"));
    System.out.println(c("a an and as at but by for in nor of on or the to up"));
    System.out.println(c("on computable numbers with an application to the entscheidungsproblem"));
  }
}

```

**Output:**

```
The Rule of Thumb for Title Capitalization
Programming Puzzles and Code Golf
The Many Uses of the Letter A
Title
And and And
A an and as at but by for in nor of on or the to Up
On Computable Numbers With an Application to the Entscheidungsproblem

```
> 2 votes

# Answer
# TI-Basic, 295 + 59 + 148 = 502 bytes

*Now you can capitalize on your calculator. Great for school :)*

**Main Program, 295 bytes**

Basically, the trick to matching words so all `A` don't become `a` is to enclose with spaces, such as replace `" A "` with `" a "`. This also automatically makes it so that the first and last words stay capitalized, because they do not have a space on both sides and will thus not match any of the words. (Genius, right? And super long because lowercase letters are two bytes each...)

```
"("+Ans+")→Str1
"@A ~ a@An ~ an@The ~ the@At ~ at@By ~ by@For ~ for@In ~ in@Of ~ of@On ~ on@To ~ to@Up ~ up@And ~ and@As ~ as@But ~ but@Or ~ or@Nor ~ nor@→Str2
For(I,2,length(Ans
If "@"=sub(Str2,I-1,1
Then
" "+Str1+"~"+sub(Str2,I,inString(Str2,"@",I)-I)+" "
prgmQ
Ans→Str1
End
End

```

**Subprogram (`prgmQ`), 59 bytes:**

```
Ans→Str9
inString(Ans,"~
sub(Str9,Ans,length(Str9)-Ans+1→Str8
Str9
prgmR
Repeat Str9=Ans+Str8
Ans+Str8→Str9
prgmR
End

```

**Subprogram (`prgmR`), 148 bytes:**

```
Ans→Str0
inString(Ans,"~→Z
inString(Str0,"~",Ans+1→Y
inString(sub(Str0,1,Z-1),sub(Str0,Z+1,Ans-Z-1→X
sub(Str0,1,-1+inString(Str0,"~
If X
sub(Str0,1,X-1)+sub(Str0,Y+1,length(Str0)-Y)+sub(Str0,X+length(sub(Str0,Z+1,Y-Z-1)),Z-X-length(sub(Str0,Z+1,Y-Z-1

```

P.S. `~` represents token `0x81` and `@` represents token `0x7F`, learn more here.
> 2 votes

# Answer
# Groovy, 131 129

Two bytes saved thanks to carusocomputing

```
{it.split()*.with{a->a in "a an the at by for in of on to up and as but or nor".split()?a:a.capitalize()}.join(" ").capitalize()}

```
> 1 votes

# Answer
# Java 7, ~~431 317~~ 311 bytes

*Thanks to @KevinCruijssen for **114** bytes.*
*Thanks to @RosLup for saving **6** bytes.*

```
String c(String s){String v="",x,l[]=s.split(" "),b[]={"a","an","the","at","but,"by","for","in","of","on","to","up","as","or","and","nor"};int i=0,f=0,z=0;for(String c:l){for(f=0;f<b.length;z=c.equals(b[f++])|z>0?1:0);x=(char)(c.charAt(0)-32)+c.substring(1);v+=(z>0?i<1|i>l.length-2?x:c:x)+" ";i++;}return v;}

```

# ungolfed

first answer above 250 bytes

```
 static String c(String s) {
      String v = "", x, l[] = s.split(" "),
b[]={"a","an","the","at","by","for","in","of","on","to",
                                         "up","and","as","or","nor","but"};
    int i , f , z = i = f = 0;
    for (String c : l) {

   for (f = 0; f < b.length; z = c.equals( b[f++] ) | z > 0 ? 1 : 0);
        x = (char)(c.charAt(0) - 32) + c.substring(1);

        v += (z > 0 ? i < 1 | i > l.length - 2 ? x : c : x) + " ";
        i++;
   }
    return v;
    }

```
> 1 votes

# Answer
# PHP, ~~117~~ ~~118~~ 112 bytes

```
<?=strtr(ucwords(preg_replace("# (?=(a[snt]?|and|[fn]or|up|by|but|the|to|in|o[rnf]) )#","!",$argv[1])),'!',' ');

```

Uses the behaviour of `ucwords()` and escapes the relevant words that are surrounded by spaces then deletes the escape characters.

I copied the `(a[snt]?|and|[fn]or|up|by|but|the|to|in|o[rnf])` from Jörg Hülsermann's answer but as the approach is completely different I'm posting it as a separate answer.

edit: bug noticed by Titus, fixing it cost 1 byte. also: 6 bytes saved thanks to his helpful comment about strtr
> 1 votes

# Answer
## C#, 305 bytes

Lots of room for improvement still but here you go:

```
s=>{;var b=s.Split(' ');b[0]=((char)(b[0][0]-32))+b[0].Substring(1);int i=0,n=b.Length;for(;++i<n;)if(!"a,an,the,at,by,for,in,of,on,to,up,and,as,but,or,nor".Split(',').Contains(b[i]))b[i]=((char)(b[i][0]-32))+b[i].Substring(1);b[n-1]=((char)(b[n-1][0]-32))+b[n-1].Substring(1);return string.Join(" ",b);};

```
> 1 votes

# Answer
# PHP, ~~109~~ 142 bytes

```
<?=preg_replace_callback("# (A[snt]?|And|[FN]or|Up|By|But|The|To|In|O[rnf])(?= )#",function($m){return strtolower($m[0]);},ucwords($argv[1]));

```

A merger of user59178´s and mbomb007´s answer.

uppercases the first letter of every word, then lowercases all words from the list surrounded by spaces.
Unfortunately, the callback has to operate on the complete set; this costs 29 bytes.
> 1 votes

# Answer
# Ruby, ~~123~~ ~~117~~ ~~111~~ 102 bytes

```
->s{s.gsub(/ .|^./,&:upcase).gsub(/ (A[nts]?|The|By|In|To|Up|And|But|[NF]or|O[rnf])(?= )/,&:downcase)}

```

Sorry for all the edits - this should be the last one.
> 1 votes

# Answer
# Python, 177 bytes

Delivered in function format for byte saving purposes. This is not an especially competitive answer, but it is one that doesn't require `repr()` or `regex` trickery. It is also version-agnostic; it works with Python 2 or 3.

Though it is perhaps a very by-the-rules solution.

```
def t(s):
 w="a an the the at by for in of on to up and as but or nor".split()
 l=[(s.title(),s)[s in w]for s in s.split()]
 for x in(0,-1):l[x]=l[x].title()
 return' '.join(l)

```
> 1 votes

# Answer
## Racket 353 bytes

```
(define(cap i)(set! i(string-append i))(define c(string-ref i 0))(string-set! i 0(if(char-upper-case? c)c(integer->char(-(char->integer c)32))))i)
(let*((ex(list"a""an""the""at""by""for""in""of""on""to""up""and""as""but""or""and""nor"))(sl(string-split s)))
(string-join(for/list((i sl)(n(in-naturals)))(cond[(= n 0)(cap i)][(member i ex)i][(cap i)]))))

```

Ungolfed:

```
(define (f s)

  (define (cap i)                 ; sub-fn to capitalize first letter of a word
    (set! i (string-append i))
    (define c (string-ref i 0))
    (string-set! i 0
                 (if (char-upper-case? c)
                     c
                     (integer->char (-(char->integer c)32))))
    i)

  (let* ((ex (list "a""an""the""at""by""for""in""of""on""to""up""and""as""but""or""and""nor"))
         (sl (string-split s)))
    (string-join
     (for/list
         ((i sl)
          (n (in-naturals)))
       (cond
         [(= n 0) (cap i)]
         [(member i ex) i]
         [(cap i)]
         )))))

```

Testing:

```
(f "the rule of thumb for title capitalization")

```

Output:

```
"The Rule of Thumb for Title Capitalization"

```
> 1 votes

# Answer
## *Pure* `bash` \- 253

(no external programs called) - needs bash v4

```
declare -A b;for x in A An The At By For In Of On To Up And As But Or Nor;do b[$x]=1;done
while read -a w;do
n=${#w[@]};o[0]=${w[0]^}
for((i=1;i<n-1;i++)){
g=${w[$i]^};((${b[$g]}))&&o+=(${g,,})||o+=($g);}
((n>1))&&o[$n]=${w[-1]^}
echo ${o[@]};o=()
done

```

normal view with comments

```
#create the "blacklist"
declare -A b
for w in A An The At By For In Of On To Up And As But Or Nor
do
    b[$x]=1
done

# logic:
# read each line (split by words) into array
# and each word is assigned capitalized to the new output array
# but the blacklisted ones

#read each line to array w (split on spaces)
while read -a w
do
    n=${#w[@]}         # get the number of words
    o[0]=${w[0]^}          # copy the capitalized word1
    for((i=1 ; i<n-1 ; i++)) { # loop over 2 up to last -1 words

        g=${w[$i]^}    # for the given word
        # check if it is in the blacklisted ones
        # if yes - convert to lowercase, if not leave as it is
        # and append to the output array
        (( ${b[$g]} )) && o+=(${g,,}) || o+=($g)
    }
    # capitalize the last word if here is more words
    (( n>1 )) && o[$n]=${w[-1]^}
    # make a line from the words
    echo ${o[@]}
    o=() #cleanup
done

```

output

```
Title
And and And
The Rule of Thumb for Title Capitalization
Programming Puzzles and Code Golf
The Many Uses of the Letter A
A an and as at but by for in nor of on or the to Up
On Computable Numbers With an Application to the Entscheidungsproblem

```
> 1 votes

# Answer
# Japt, 71 bytes

```
£`a  e  by f     up d  ¿t  n`¸aX >0©Y¦0©YÄ¦Zl ?X:Xg u +XÅ}S

```

Try it online!

### Explanation:

```
£`a  e  by f     up d  ¿t  n`¸aX >0©Y¦0©YÄ¦Zl ?X:Xg u +XÅ}S
£`...`qS aX >0&&Y!=0&&Y!=UqS l -1?X:Xg u +Xs1}S

£                                            }S   // Split at spaces and map each item X by this function:
 `...`                                            //  Backticks are used to decompress strings
      qS                                          //  Split the decompressed string at spaces.
         aX >J                                    //  If this contains X
              &&Y!=0                              //  and the index is non-zero (it's not the first word)
                    &&Y!=UqS l -1                 //  and the index is not the length of the input -1 (it's not the last word),
                                 ?X               //  return X.
                                   :Xg u +Xs1     //  Else, return X capitalized. (Literally X[0].toUpperCase() + X.slice(1))
                                             }S   // Rejoin with spaces

```

One of my favorite Japt features is its string compression, which uses the shoco library.

You can compress a string by wrapping it in `Oc"{string}"``Oc"a an the at by for in of on to up and as but or nor"`

Then decompressing it with backticks or `Od"{compressed string}"``Od"a e by f up d ¿t n"`
> 1 votes

# Answer
## *Pure* `bash` \- ~~205~~ ~~192~~ 181 bytes

```
tc(){
while read -a x
do x=(${x[@]^})
for ((i=1;i<${#x[@]}-1;i++))
do
case "${x[i]}" in
A|A[nts]|The|By|[FN]or|In|O[fnr]|To|Up|And|But)x[i]=${x[i],};;
esac
done
echo ${x[@]}
done
}

```

Like jm66's answer `tc` accepts standard input.
> 1 votes

# Answer
# Actually, 79 bytes

```
' ,ÿsd@p@`;0"A0An0The0At0By0For0In0Of0On0To0Up0And0As0But0Or0Nor"síu'ù*ƒ`Moq' j

```

Try it online!

Explanation:

```
' ,ÿsd@p@`;0"longstring"síu'ù*ƒ`Moq' j
' ,ÿs                                   title case input, split on spaces
     d@p@                               pop first and last words to stack
         `;0"longstring"síu'ù*ƒ`M       for every word except the first and last:
          ;0"longstring"s                 duplicate word, split the long string on 0s
                         íu               1-based index of word in list (0 if not found)
                           'ù*            "ù"*(index)
                              ƒ           execute the resulting string as a function (lowercases word if it's in the list)
                                 oq' j  put the first and last word back in the list, join with spaces

```
> 0 votes

# Answer
## Batch, 323 bytes

```
@echo off
set s=
for %%w in (@%*@)do call:w %%w
echo%s%
exit/b
:w
for %%s in (a an the at by for in of on to up and as but or nor)do if %%s==%1 set s=%s% %1&exit/b
set w=%1
set w=%w:@=%
set f=%w:~0,1%
for %%c in (A B C D E F G H I J K L M N O P Q R S T U V W X Y Z)do call set f=%%f:%%c=%%c%%
set s=%s% %f%%w:~1%

```

With comments:

```
@echo off
rem Start with an empty output string
set s=
rem Wrap the parameters in @ signs to identify the first and last words
for %%w in (@%*@) do call :w %%w
rem Ignore the leading space when printing the result
echo%s%
exit/b
:w
rem Check whether this is a word that we don't change
for %%s in (a an the at by for in of on to up and as but or nor) do if %%s==%1 set s=%s% %1&exit/b
set w=%1
rem Delete any @ signs from the first and last words
set w=%w:@=%
rem Get the first character
set f=%w:~0,1%
rem Case insensitively replace each upper case letter with itself
for %%c in (A B C D E F G H I J K L M N O P Q R S T U V W X Y Z) do call set f=%%f:%%c=%%c%%
rem Concatenate with the rest of the word
set s=%s% %f%%w:~1%

```
> 0 votes

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


title: Shh... Can You Split a Secret?

text:
# Question
Title: Shh... Can You Split a Secret?
In *Applied Cryptography* by Bruce Schneier (which I have been reading quite a lot recently), a protocol for splitting secrets is discussed. Here is a brief description:

> 1. Trent generates a random byte string, *R*, the same length as the message, *M*.
> 2. Trent XORS *M* with *R* to make *S*.
> 3. He gives *R* to Alice and *S* to Bob.

---

Your task is to, given an input, split the input into two output files or print the split secret to STDOUT. One output/part of output should contain the random string; the other should contain the original input XOR'd with the random string. Input and output may be to/from files or to/from STDIN/STDOUT. Outputting to STDERR is also allowed.
There are a few restrictions, however:

1. Your program must take 1 input (1 input filename & 2 outputs if doing file I/O), and output the random string and the original string XOR'd with that random string into the other.
2. Your program must be cryptographically secure. All random number generators must be cryptographically secure. For example, `/dev/random` is fine, but the Mersenne Twister (usually `randint(number,number)` is *not*. Any random number generator must be *explicitly* cryptographically secure.
    * If you want to know anything more about what "cryptographically secure" means, check here.
3. Standard rules and loopholes apply.

---

This is , so the code with the fewest bytes will win.
May the best coder prosper...

# Answer
> 3 votes
# Bash + coreutils + openssl, 91 bytes

```
0000000: 63 3d 22 6f 70 65 6e 73 73 6c 20 65 6e 63 20 2d  c="openssl enc -
0000010: 61 65 73 2d 31 32 38 2d 63 74 72 20 2d 4b 20 24  aes-128-ctr -K $
0000020: 28 78 78 64 20 2d 70 73 20 2d 6c 20 31 36 20 2f  (xxd -ps -l 16 /
0000030: 64 65 76 2f 72 61 6e 64 6f 6d 29 20 2d 69 76 20  dev/random) -iv
0000040: 30 22 0a 24 63 3c 24 31 0a 74 72 20 01 2d ff 20  0".$c<$1.tr .-.
0000050: 5c 30 3c 24 31 7c 24 63 3e 26 32                 \0<$1|$c>&2

```

Takes a filename as argument and splits the secret to STDOUT and STDERR. Input and output are in raw binary format.

### Sample run

```
$ cat input.txt
Bruce
$ bash split input.txt 2> >(xxd -ps >& 2) | xxd -ps
d5725c26aa3b
97002945cf31
$ printf %02x $[0xd5725c26aa3b ^ 0x97002945cf31] | xxd -r -ps
Bruce

```

# Answer
> 2 votes
# JavaScript (ES6), ~~77~~ 76 bytes

```
let f =
M=>[R=crypto.getRandomValues(new Uint8Array(M.length)),M.map((c,i)=>c^R[i])]

let g = m => console.log(f([...m].map(c=>c.charCodeAt())).map(x=>`[${x.join(", ")}]`).join(",\n"))
g("Secret message")
g("\0\0\0\0\0\0\0\0")
```

I think this is what's being asked for. It takes in an array of bytes and outputs `[random bytes, XORed message]`. I'm assuming that `crypto.getRandomValues` is cryptographically secure (else I don't know why it exists), and that `Math.random` isn't. Otherwise I could save 28 bytes.

# Answer
> 2 votes
## Haskell, 178 Bytes

```
import System.Entropy
import qualified Data.ByteString as B
import Data.Bits
main|f<-B.init=do b<-B.getLine;r<-getEntropy.B.length$f b;B.putStrLn.pack.B.zipWith xor r$f b;print r

```

Unfortunately, I can't quite think of a way to do this without three big imports.

More readable version:

```
main=do b<-B.getLine
        r<-getEntropy . B.length $ B.init b
        B.putStrLn . pack . B.zipWith xor r $ f b
        print r

```

Basically, it reads a line from stdin, makes a random number with that length and then prints the xor'd version and the random number

# Answer
> 1 votes
# Python 3, 85 bytes

```
import os
s=input()
k=os.urandom(len(s))
print(list(k),[j^ord(i)for i,j in zip(k,s)])

```

The only part that might need explaining is the list comprehension (`[j^ord...]`)

It combines the input with the random key (`zip([1,2,3],[4,5,6])==[(1,4),(2,5),(3,6)]`) and xors them together.

# Answer
> 1 votes
# Ruby, ~~88~~ 76 bytes

Edit: I guess the outputs don't have to be *strings* strings?

```
m=gets.bytes
p r=`head -c#{m.size}</dev/random`.bytes,m.zip(r).map{|a,b|a^b}

```

# Answer
> 0 votes
# Java, 292 bytes

Not sure if 100% correct

```
enum e{;public static void main(String[]a){java.security.SecureRandom r=new java.security.SecureRandom();byte[]b=a[0].getBytes(),c=new byte[b.length],d=new byte[c.length];int i=-1;r.nextBytes(c);while(++i<b.length)d[i]=(byte)(b[i]^c[i]);System.out.println(new String(c)+"\n"+new String(d));}}

```

Takes the input as first argument, outputs key and XOR'ed string to STDOUT separated by newlines.

Ungolfed with comments:

```
enum e {
    ;

    public static void main(String[] a) {
        java.security.SecureRandom r = new java.security.SecureRandom();            // Secure random
        byte[] b = a[0].getBytes(), c = new byte[b.length], d = new byte[c.length]; // 3 arrays
        int i = -1;                                                                 // Index
        r.nextBytes(c);                                                             // Key
        while (++i < b.length) d[i] = (byte) (b[i] ^ c[i]);                         // XOR the input with key
        System.out.println(new String(c) + "\n" + new String(d));                   // Output key and XORed string
    }
}

```

---
Tags: code-golf, random, cryptography
---


title: Convert Input to Direction

text:
# Question
Title: Convert Input to Direction
# Challenge

Given input in the form `<n1>, <n2>` where number can be -1, 0, or 1, return the corresponding cardinal direction. Positive numbers move East in the x-axis and South in the y-axis, Negative numbers move West in the x-axis and North in the y-axis.

Output must be in the form `South East`, `North East`, `North`. It is case-sensitive.

If the input is 0, 0, your program must return `That goes nowhere, silly!`.

# Sample Input/Outpot:

`1, 1` -\> `South East`

`0, 1` -\> `South`

`1, -1` -\> `North East`

`0, 0` -\> `That goes nowhere, silly!`

This is , the shortest answer in bytes wins.

# Answer
> 11 votes
# Japt, ~~55~~ 51 bytes

```
`
SÆ
NÆ° `·gV +`
E†t
Wƒt`·gU ª`T•t goƒ Í2€e, Ðéy!

```

### Explanation

```
                      // Implicit: U, V = inputs
`\nSÆ \nNÆ° `       // Take the string "\nSouth \nNorth ".
·                     // Split it at newlines, giving ["", "South ", "North "].
gV                    // Get the item at index V. -1 corresponds to the last item.
+                     // Concatenate this with
`\nE†t\nWƒt`·gU       // the item at index U in ["", "East", "West"].
ª`T•t goƒ Í2€e, Ðéy!  // If the result is empty, instead take "That goes nowhere, silly!".
                      // Implicit: output result of last expression

```

Try it online!

# Answer
> 8 votes
# Python, ~~101~~ 87 bytes

Really naive solution.

```
lambda x,y:['','South ','North '][y]+['','West','East'][x]or'That goes nowhere, silly!'

```

Thanks to @Lynn for saving 14 bytes! Changes: Using the string.split method actually makes it longer ;\_; And also, negative indexes exist in python.

# Answer
> 5 votes
# PHP, 101 Bytes

```
[,$b,$a]=$argv;echo$a|$b?[North,"",South][1+$a]." ".[West,"",East][1+$b]:"That goes nowhere, silly!";

```

# Answer
> 5 votes
# Perl 6, 79 bytes

```
{<<'' East South North West>>[$^y*2%5,$^x%5].trim||'That goes nowhere, silly!'}

```

Try it

## Expanded:

```
{ # bare block lambda with placeholder parameters ｢$x｣ and ｢$y｣

  << '' East South North West >>\ # list of 5 strings
  [                               # index into that with:

    # use a calculation so that the results only match on 0
    $^y * 2 % 5, # (-1,0,1) => (3,0,2) # second parameter
    $^x % 5      # (-1,0,1) => (4,0,1) # first parameter

  ]
  .trim  # turn that list into a space separated string implicitly
         # and remove leading and trailing whitespace

  ||     # if that string is empty, use this instead
  'That goes nowhere, silly!'
}

```

# Answer
> 5 votes
# JavaScript (ES6), 106 100 97 93 bytes

It's a very simple approach. It consists of a few ternary operators nested together -

```
f=a=>b=>a|b?(a?a>0?"South ":"North ":"")+(b?b>0?"East":"West":""):"That goes nowhere, silly!"

```

**Test Cases**

```
f=a=>b=>a|b?(a?a>0?"South ":"North ":"")+(b?b>0?"East":"West":""):"That goes nowhere, silly!"

console.log(f(1729)(1458));
console.log(f(1729)(-1458));
console.log(f(-1729)(1458));
console.log(f(-1729)(-1458));
console.log(f(0)(1729));
console.log(f(0)(-1729));
console.log(f(1729)(0));
console.log(f(-1729)(0));
```

# Answer
> 4 votes
# JavaScript (ES6), 86 bytes

```
a=>b=>["North ","","South "][b+1]+["West","","East"][a+1]||"That goes nowhere, silly!"

```

# Explanation

Call it with currying syntax (`f(a)(b)`). This uses array indices. If both `a` and `b` are 0, the result is a falsy empty string. In that case, the string after the `||` is returned.

# Try it

Try all test cases here:

```
let f=
a=>b=>["North ","","South "][b+1]+["West","","East"][a+1]||"That goes nowhere, silly!"

for (let i = -1; i < 2; i++) {
    for (let j = -1; j < 2; j++) {
        console.log(`${i}, ${j}: ${f(i)(j)}`);
    }
}
```

# Answer
> 3 votes
## Batch, 156 bytes

```
@set s=
@for %%w in (North.%2 South.-%2 West.%1 East.-%1)do @if %%~xw==.-1 call set s=%%s%% %%~nw
@if "%s%"=="" set s= That goes nowhere, silly!
@echo%s%

```

The `for` loop acts as a lookup table to filter when the (possibly negated) parameter equals -1, and concatenating the matching words. If nothing is selected then the silly message is printed instead.

# Answer
> 2 votes
# Japt, 56 bytes

```
N¬¥0?`T•t goƒ Í2€e, Ðéy!`:` SÆ NÆ°`¸gV +S+` E†t Wƒt`¸gU

```

Try it online! | Test Suite

### Explanation:

```
N¬¥0?`Tt go Í2e, Ðéy!`:` SÆ NÆ°`¸gV +S+` Et Wt`¸gU
Implicit U = First input
         V = Second input

N¬¥0?`...`:` ...`qS gV +S+` ...`qS gU
N¬                                                     Join the input (0,0 → "00")
  ¥0                                                   check if input is roughly equal to 0. In JS, "00" == 0
    ?                                                  If yes:
      ...                                               Output "That goes nowhere, silly!". This is a compressed string
     `   `                                              Backticks are used to decompress strings
          :                                            Else:
           ` ...`                                       " South North" compressed
                 qS                                     Split on " " (" South North" → ["","South","North"])
                   gV                                   Return the string at index V
                     +S+                                +" "+
                        ` ...`                          " East West" compressed
                              qS gU                     Split on spaces and yield string at index U

```

# Answer
> 2 votes
## GNU sed, 100 + 1(r flag) = 101 bytes

```
s:^-1:We:
s:^1:Ea:
s:-1:Nor:
s:1:Sou:
s:(.*),(.*):\2th \1st:
s:0...?::
/0/cThat goes nowhere, silly!

```

By design, sed executes the script as many times as there are input lines, so one can do all the test cases in one run, if needed. The TIO link below does just that.

**Try it online!**

**Explanation:**

```
s:^-1:We:                         # replace '-1' (n1) to 'We'
s:^1:Ea:                          # replace '1' (n1) to 'Ea'
s:-1:Nor:                         # replace '-1' (n2) to 'Nor'
s:1:Sou:                          # replace '1' (n2) to 'Sou'
s:(.*),(.*):\2th \1st:            # swap the two fields, add corresponding suffixes
s:0...?::                         # delete first field found that starts with '0'
/0/cThat goes nowhere, silly!     # if another field is found starting with '0',
                                  #print that text, delete pattern, end cycle now

```

The remaining pattern space at the end of a cycle is printed implicitly.

# Answer
> 1 votes
# Retina, ~~84~~ ~~82~~ 81 bytes

*1 byte saved thanks to @seshoumara for suggesting `0...?` instead of `0\w* ?`*

```
(.+) (.+)
$2th $1st
^-1
Nor
^1
Sou
-1
We
1
Ea
0...?

^$
That goes nowhere, silly!

```

Try it online!

# Answer
> 1 votes
# 05AB1E, ~~48~~ ~~45~~ 43 bytes

```
õ'†Ô'…´)èUõ„ƒÞ „„¡ )èXJ™Dg_i“§µ—±æÙ,Ú¿!“'Tì

```

Try it online!

**Explanation**

```
õ'†Ô'…´)                                       # push the list ['','east','west']
        èU                                     # index into this with first input
                                               # and store the result in X
          õ„ƒÞ „„¡ )                           # push the list ['','south ','north ']
                    èXJ                        # index into this with 2nd input
                                               # and join with the content of X
                       ™                       # convert to title-case
                        Dg_i                   # if the length is 0
                            “§µ—±æÙ,Ú¿!“       # push the string "hat goes nowhere, silly!"
                                        'Tì    # prepend "T"

```

# Answer
> 1 votes
## C#, ~~95~~ 102 bytes

---

**Golfed**

```
(a,b)=>(a|b)==0?"That goes nowhere, silly!":(b<0?"North ":b>0?"South ":"")+(a<0?"West":a>0?"East":"");

```

---

**Ungolfed**

```
( a, b ) => ( a | b ) == 0
    ? "That goes nowhere, silly!"
    : ( b < 0 ? "North " : b > 0 ? "South " : "" ) +
      ( a < 0 ? "West" : a > 0 ? "East" : "" );

```

---

**Ungolfed readable**

```
// A bitwise OR is perfomed
( a, b ) => ( a | b ) == 0

    // If the result is 0, then the 0,0 text is returned
    ? "That goes nowhere, silly!"

    // Otherwise, checks against 'a' and 'b' to decide the cardinal direction.
    : ( b < 0 ? "North " : b > 0 ? "South " : "" ) +
      ( a < 0 ? "West" : a > 0 ? "East" : "" );

```

---

**Full code**

```
using System;

namespace Namespace {
    class Program {
        static void Main( string[] args ) {
            Func<Int32, Int32, String> f = ( a, b ) =>
                ( a | b ) == 0
                    ? "That goes nowhere, silly!"
                    : ( b < 0 ? "North " : b > 0 ? "South " : "" ) +
                      ( a < 0 ? "West" : a > 0 ? "East" : "" );

            for( Int32 a = -1; a <= 1; a++ ) {
                for( Int32 b = -1; b <= 1; b++ ) {
                    Console.WriteLine( $"{a}, {b} = {f( a, b )}" );
                }
            }

            Console.ReadLine();
        }
    }
}

```

---

**Releases**

* **v1.1** \- `+ 7 bytes` \- Wrapped snippet into a function.
* **v1.0** \- `95 bytes` \- Initial solution.

---

**Notes**

*I'm a ghost, boo!*

# Answer
> 1 votes
# Jelly, 40 bytes

```
Ṛị"“¡ƘƓ“¡+9“»,“wµ“¡ḳ]“»Kt⁶ȯ“¬ɼ¬<¬O÷ƝḤẎ6»

```

Try it online!

# Answer
> 1 votes
# Swift 151 bytes

```
func d(x:Int,y:Int){x==0&&y==0 ? print("That goes nowhere, silly!") : print((y<0 ? "North " : y>0 ? "South " : "")+(x<0 ? "West" : x>0 ? "East" : ""))}

```

# Answer
> 1 votes
# PHP, 95 bytes.

This simply displays the element of the array, and if there's nothing, just displays the "default" message.

```
echo['North ','','South '][$argv[1]+1].[East,'',West][$argv[2]+1]?:'That goes nowhere, silly!';

```

This is meant to run with the `-r` flag, receiving the coordenates as the 1st and 2nd arguments.

# Answer
> 1 votes
# Scala, 107 bytes

```
a=>b=>if((a|b)==0)"That goes nowhere, silly!"else Seq("North ","","South ")(b+1)+Seq("West","","East")(a+1)

```

### Try it online

To use this, declare this as a function and call it:

```
val f:(Int=>Int=>String)=...
println(f(0)(0))

```

### How it works

```
a =>                                // create an lambda with a parameter a that returns
  b =>                              // a lambda with a parameter b
    if ( (a | b) == 0)                // if a and b are both 0
      "That goes nowhere, silly!"       // return this string
    else                              // else return
      Seq("North ","","South ")(b+1)    // index into this sequence
      +                                 // concat
      Seq("West","","East")(a+1)        // index into this sequence

```

# Answer
> 1 votes
# C, 103 bytes

```
f(a,b){printf("%s%s",b?b+1?"South ":"North ":"",a?a+1?"East":"West":b?"":"That goes nowhere, silly!");}

```

# Answer
> 0 votes
# Java 7, 130 bytes

```
String c(int x,int y){return x==0&y==0?"That goes nowhere, silly!":"North xxSouth ".split("x")[y+1]+"WestxxEast".split("x")[x+1];}

```

**Explanation:**

```
String c(int x, int y){               // Method with x and y integer parameters and String return-type
  return x==0&y==0 ?                  //  If both x and y are 0:
     "That goes nowhere, silly!"      //   Return "That goes nowhere, silly!"
    :                                 //  Else:
     "North xxSouth ".split("x"[y+1]  //   Get index y+1 from array ["North ","","South "] (0-indexed)
     + "WestxxEast".split("x")[x+1];  //   Plus index x+1 from array ["West","","East"] (0-indexed)
}                                     // End of method

```

**Test code:**

Try it here.

```
class M{
  static String c(int x,int y){return x==0&y==0?"That goes nowhere, silly!":"North xxSouth ".split("x")[y+1]+"WestxxEast".split("x")[x+1];}

  public static void main(String[] a){
    System.out.println(c(1, 1));
    System.out.println(c(0, 1));
    System.out.println(c(1, -1));
    System.out.println(c(0, 0));
  }
}

```

**Output:**

```
South East
South
North East
That goes nowhere, silly!

```

# Answer
> 0 votes
# CJam, 68 bytes

```
"
South
North

East
West"N/3/l~W%.=s_Q"That goes nowhere, silly!"?

```

Try it online! or verify all test cases

Prints one trailing space on `[0 -1]` or `[0 1]` (`North` or `South`).

**Explanation**

```
"\nSouth \nNorth \n\nEast\nWest"  e# Push this string
N/                                e# Split it by newlines
3/                                e# Split the result into 3-length subarrays,
                                  e#  gives [["" "South " "North "]["" "East" "West"]]
l~                                e# Read and eval a line of input
W%                                e# Reverse the co-ordinates
.=                                e# Vectorized get-element-at-index: accesses the element
                                  e#  from the first array at the index given by the
                                  e#  y co-ordinate. Arrays are modular, so -1 is the last
                                  e#  element. Does the same with x on the other array.
s                                 e# Cast to string (joins the array with no separator)
_                                 e# Duplicate the string
Q"That goes nowhere, silly!"?     e# If it's non-empty, push an empty string. If its empty,
                                  e#  push "That goes nowhere, silly!"

```

# Answer
> 0 votes
# Röda, 100 bytes

```
f a,b{["That goes nowhere, silly!"]if[a=b,a=0]else[["","South ","North "][b],["","East","West"][a]]}

```

Try it online!

This is a trivial solution, similar to some other answers.

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


title: Visualize nested array

text:
# Question
Title: Visualize nested array
You will be given a nested array. Your program has to visualize the array.

---

# But.. How?

For example, let's assume we have a nested array, like `[["1","2"],[["1","2"],"3"],"4",[[[["5"]]]],"6"]`.

This nested array can be visualised as:

```
->1
->2
-->1
-->2
->3
>4
---->5
>6

```

---

# Examples

```
Input 1:
["Atom",["Proton",["Up Quark", "Up Quark", "Down Quark"], "Neutron", ["Up Quark", "Down Quark", "Down Quark"], "Electron"]]
Output 1:
>Atom
->Proton
-->Up Quark
-->Up Quark
-->Down Quark
->Neutron
-->Up Quark
-->Down Quark
-->Down Quark
->Electron

Input 2:
[["1","2"],["3","4"]]
Output 2:
->1
->2
->3
->4

```

---

# Rules

* You may use string (or other types which work like a nested array) as input.
* The maximum level of "layers" is 2^32-1.

# Answer
# APL, 32 bytes

```
{1=≡⍺:⎕←⍺,⍨⍵↑1↓⍵/'->'⋄⍺∇¨⍵+1}∘0

```

Test:

```
      r
┌────┬─────────────────────────────────────────────────────────────────────────────────────────┐
│Atom│┌──────┬──────────────────────────────┬───────┬────────────────────────────────┬────────┐│
│    ││Proton│┌────────┬────────┬──────────┐│Neutron│┌────────┬──────────┬──────────┐│Electron││
│    ││      ││Up Quark│Up Quark│Down Quark││       ││Up Quark│Down Quark│Down Quark││        ││
│    ││      │└────────┴────────┴──────────┘│       │└────────┴──────────┴──────────┘│        ││
│    │└──────┴──────────────────────────────┴───────┴────────────────────────────────┴────────┘│
└────┴─────────────────────────────────────────────────────────────────────────────────────────┘
      {1=≡⍺:⎕←⍺,⍨⍵↑1↓⍵/'->'⋄⍺∇¨⍵+1}∘0 ⊢ r
>Atom
->Proton
-->Up Quark
-->Up Quark
-->Down Quark
->Neutron
-->Up Quark
-->Down Quark
-->Down Quark
->Electron

```

Explanation:

* `{`...`}∘0`: run the following function with `0` bound to :
    + `1=≡⍺:`: if the input has depth 1 (i.e. an array that does not contain other arrays):
        - `⍵/'->'`: create a string containing  `-`s and  `>`s,
        - `1↓`: drop the first element,
        - `⍵↑`: and take the first  elements. This results in a string containing `⍵-1` dashes and one `>`.
        - `⍺,⍨`: append the input to it,
        - `⎕←`: and output that to the screen
    + : otherwise,
        - `⍺∇¨⍵+1`: add 1 to  and apply the function to each nested array
> 12 votes

# Answer
## Mathematica, ~~58~~ ~~57~~ 56 bytes

*Thanks to Greg Martin for saving 1 byte.*

*Thanks to ngenisis for saving 1 byte.*

```
MapIndexed[Print[Table["-",Tr[1^#2]-1]<>">",#]&,#,{-1}]&

```
> 7 votes

# Answer
# Java 7, ~~153~~ ~~141~~ 114 bytes

```
String r="";<T,S>S c(S s,T o){for(T x:(T[])o)if(x instanceof Object[])c("-"+s,x);else r+=s+">"+x+"\n";return(S)r;}

```

-39 bytes thanks to *@Barteks2x*

**Explanation:**

```
String r="";                         // Result String outside the method / on class-level
<T,S> S c(S s, T o){                 // Recursive Method with generic String and Object parameters and String return-type
  for(T x : (T[])o)                  //  Loop over the input-array
    if(x instanceof Object[])        //   If the current item is an array itself:
      c("-"+s, x);                   //    Recursive method-call with this array
    else                             //   Else:
      r += s+">"+x+"\n";             //    Append return-String with stripes String-input, ">", current item, and a new-line
                                     //  End of loop (implicit / single-line body)
  return (S)r;                       //  Return the result-String
}                                    // End of method

```

**Test code:**

Try it here.

```
class M{
  String r="";<T,S>S c(S s,T o){for(T x:(T[])o)if(x instanceof Object[])c("-"+s,x);else r+=s+">"+x+"\n";return(S)r;}

  public static void main(String[] a){
    M m = new M();
    System.out.println(m.c("", new Object[]{new Object[]{1,2},new Object[]{new Object[]{1,2},3},4,new Object[]{new Object[]{new Object[]{new Object[]{5}}}},6}));
    m.r = "";
    System.out.println(m.c("", new Object[]{"Atom",new Object[]{"Proton",new Object[]{"Up Quark","Up Quark","Down Quark"}},new Object[]{"Neutron",new Object[]{"Up Quark","Up Quark","Down Quark"}},"Electron"}));
  }
}

```

**Output:**

```
->1
->2
-->1
-->2
->3
>4
---->5
>6

>Atom
->Proton
-->Up Quark
-->Up Quark
-->Down Quark
->Neutron
-->Up Quark
-->Up Quark
-->Down Quark
>Electron

```
> 6 votes

# Answer
# PHP, ~~77 74~~ 73 bytes

4 bytes saved thanks @manatwork.

```
function f($a,$p=">"){foreach($a as$e)"$e"!=$e?f($e,"-$p"):print"$p$e
";}

```

recursive function, requires PHP 7.1 or newer for the negative string index.
<sup>`"$e"` is `Array` for arrays; so `"$e"!=$e` is the same as `is_array($e)`.</sup>

* start with prefix `>`
* prepend a `-` to the prefix for each level
* print prefix+element+newline for atoms
> 6 votes

# Answer
# C99 (GCC), 201 187 140 112 109

```
f(char*a){for(long d=1,j;j=d+=*++a>90?92-*a:0;)if(*a<35){for(;j||*++a^34;)putchar(j?"->"[!--j]:*a);puts("");}}

```

expanded form:

```
f(char*a){
    for(long d=1,j;j=d+=*++a>90?92-*a:0;)
        if(*a<35){
            for(;j||*++a^34;)putchar(j?--j?45:62:*a);
            puts("");
        }
}

```

This takes a string in the correct format and terminates when finding the last matching `]`.

It doesn't use recursion and uses long types to **actually achieve the second rule: 2^32-1 levels**. Most scripting languages have a limited recursion depth or simply crash on stack overflow.

I'm not used to golf in C any help is appreciated :)

Thanks at bolov for his tips ! Specially thanks to Titus who's always up for a good round of golfing (even in C) !

Another two bytes saved by the fact that we can finish once we match the last `]` and don't need to match a null char.

It can be tested at Wandbox.
> 5 votes

# Answer
# Python 2, 65 64 bytes

```
f=lambda o,d=0:o<''and'\n'.join(f(e,d+1)for e in o)or'-'*d+'>'+o

```

Right now my answer consistently starts with no dashes, so `["foo", "bar"]` is:

```
>foo
>bar

```
> 4 votes

# Answer
## JavaScript (ES6), ~~58~~ 51 bytes

```
f=(a,s='>')=>a.map(e=>e.map?f(e,'-'+s):s+e).join`
`

```

Edit: Saved 7 bytes when @Arnauld pointed out that I could combine my two approaches.
> 4 votes

# Answer
# PHP, ~~129 123 112 109 95 93~~ 91 bytes

```
for(;a&$c=$argn[++$i];)$c<A?$c<"-"?a&$s?$s=!print"$p>$s
":0:$s.=$c:$p=substr("---$p",$c^i);

```

iterative solution takes string from STDIN:
Run with `echo '<input>' | php -nR '<code>'` or test it online.

**breakdown**

```
for(;a&$c=$argn[++$i];)     // loop $c through input characters
    $c<A                        // not brackets?
        ?$c<"-"                     // comma or quote?
            ?a&$s?$s=!print"$p>$s\n":0  // if $s not empty, print and clear $s
            :$s.=$c                     // digit: append to $s
        :$p=substr("---$p",$c^i)    // prefix plus or minus one "-"
;

```

Happy that the numbers are in quotes; so I only need one action at a time.

**ASCII fiddling**

```
char    ascii   binary/comment
 "       34
 ,       44
 [       91     0101 1011
 ]       93     0101 1101

 A       65     $c<A    true for comma, quote and digits
 -       45     $c<"-"  true for comma and quote

                =0011 1010 -> 50 -> "2"
i^"["   105^91  ^0101 1011
 i      105      0110 1001
i^"]"   105^93  ^0101 1101
                =0011 0100 -> 52 -> "4"

```

Adding 3 dashes to `$p` and removing 2 for `[`, 4 for `]` adds one for `[` and removes one for `]`.
> 4 votes

# Answer
# Ruby, ~~49 45~~ 46 bytes

```
f=->c,p=?>{c.map{|x|x==[*x]?f[x,?-+p]:p+x}*$/}

```

Example:

```
puts f[["Atom",["Proton",["Up Quark", "Up Quark", "Down Quark"], "Neutron", ["Up Quark", "Down Quark", "Down Quark"], "Electron"]]]

>Atom
->Proton
-->Up Quark
-->Up Quark
-->Down Quark
->Neutron
-->Up Quark
-->Down Quark
-->Down Quark
->Electron

```

### Explanation:

Recursive function: if `x==[*x]` then x is an array, and we iterate over it. If not, indent it.
> 3 votes

# Answer
# Perl 5, 55 bytes

53 bytes of code + `-nl` flags.

```
/"/?print"-"x~-$v.">$_":/]/?$v--:$v++for/]|\[|".*?"/g

```

Try it online!

Not optimal for regex because of some edgy cases that could potentially occur (in particular, if an element of the array contains brackets inside).
A recursive anonymous function would be barely longer though (61 bytes):

```
sub f{my$v=pop;map{ref?f(@$_,$v+1):"-"x$v.">$_"}@_}sub{f@_,0}

```

Try it online!

But the way Perl deals with parameters isn't optimal for golfing functions: no optional parameters means I have to do a second function (anonymous) calling the first one, and I have to explicitly get the last parameter with that long `my$v=pop`.
> 3 votes

# Answer
## Haskell, 104 bytes

```
l@(x:y)#(a:m)|[(h,t)]<-reads$a:m=y++h++l#t|a<'#'=l#m|a<'-'='\n':l#m|a>'['=y#m|q<-'-':l=q#m
l#_=""
(">"#)

```

Haskell doesn't have nested lists with different depths, so I have to parse the input string on my own. Luckily the library function `reads` can parse Strings (i.e. `"`-enclosed char sequence), so I have a little help here.

Usage example:

```
*Main> putStrLn $ (">"#) "[[\"1\",\"2\"],[\"3\",\"4\"]]"
->1
->2
->3
->4

```

Try it online!.

How it works:

The function `#` goes through the string char by char and keeps the nesting level (the first parameter `l`) as a string of `-` with a final `>`. If the head of the list can be parsed as a String, take `l` and the String followed by recursive call with the String removed. If the first char is a Space, skip it. If it's a `,`, take a newline and go on, if it's `]`, lower the nesting level and go on and else (only `[` left) raise the nesting level and go on. Recursion ends with the empty input string. The main function `(">"#)` sets the nesting level to `">"` and calls `#`.
> 3 votes

# Answer
## SWI-Prolog, 115 bytes

```
p(L):-p(L,[>]).
p([],_):-!.
p([H|T],F):-p(H,[-|F]),p(T,F),!.
p(E,[_|F]):-w(F),w([E]),nl.
w([]).
w([H|T]):-write(H),w(T).

```

Line breaks added for readability only, not included in byte count.

`p` predicate recursively traverses the arrays, adding a '-' to the prefix `F` when moving a level deeper. `w` is used to write the prefix array as well as the actual element to the output.

Example:

```
?- p(["Atom",["Proton",["Up Quark", "Up Quark", "Down Quark"], "Neutron", ["Up Quark", "Down Quark", "Down Quark"], "Electron"]]).
>Atom
->Proton
-->Up Quark
-->Up Quark
-->Down Quark
->Neutron
-->Up Quark
-->Down Quark
-->Down Quark
->Electron

```
> 2 votes

# Answer
## Batch, 249 bytes

```
@echo off
set/ps=
set i=
:t
set t=
:l
set c=%s:~,1%
set s=%s:~1%
if "%c%"=="[" set i=-%i%&goto l
if not "%c%"=="]" if not "%c%"=="," set t=%t%%c%&goto l
if not "%t%"=="" echo %i:~1%^>%t%
if "%c%"=="]" set i=%i:~1%
if not "%s%"=="" goto t

```

Annoyingly Batch has trouble comparing commas. Sample run:

```
[Atom,[Proton,[Up Quark,Up Quark,Down Quark],Neutron,[Up Quark,Down Quark,Down Quark],Electron]]
>Atom
->Proton
-->Up Quark
-->Up Quark
-->Down Quark
->Neutron
-->Up Quark
-->Down Quark
-->Down Quark
->Electron

```
> 2 votes

# Answer
# Retina, ~~63~~ ~~54~~ 52 bytes

*Saved 2 bytes thanks to Martin Ender*

```
.*?".*?"
$`$&¶
T`[] -~`-]_`.(?=.*".*")
-]

-"
>
T`]"

```

Try it online!

**Explanation**

```
.*?".*?"
$`$&¶

```

First, the array is broken up by replacing each quoted string with everything that came before it, plus itself, plus a newline. By breaking it up like this, it's possible to find the unmatched opening brackets before each string.

```
T`[] -~`-]_`.(?=.*".*")

```

This transliteration will replace `[` with `-`, leave `]` unchanged, and delete every other character (`-~` is all printable ASCII). However, it only replaces characters appearing before the final string on each line.

```
-]

```

Next all instances of `-]` are removed. These correspond to matching bracket pairs, and we only want unmatched brackets. After these are removed, each line has a number of `-`s equal to how many unmatched opening brackets came before it.

```
-"
>

```

The last `-` before a `"` is replaced with `>`, to form the arrows.

```
T`]"

```

Finally, all remaining `]`s and `"`s are deleted.
> 2 votes

# Answer
# Röda, 54 bytes

```
f d=""{{|n|{n|f d=`$d-`}if[n is list]else[`$d>$n
`]}_}

```

Try it online!

It's a function that reads the input array from the stream. For each item, it either calls itself recursively or prints the item.
> 1 votes

# Answer
# Python 3, 80 Bytes

Python's lambdas support recursion it seems, who knew ?

```
p=lambda l,d=1:[p(i,d+1)if isinstance(i,list)else print("-"*d+">"+i)for i in l]

```

This is a counter/compliment to orlp's answer.
> 1 votes

# Answer
# Groovy, 92 bytes

```
x={a,b->if(a instanceof List){a.each{x(it,b+1)}}else{y(a,b)}};y={a,b->println("-"*b+">$a")};

```
> 0 votes

# Answer
# Stacked, 27 bytes

```
[@.1-'-'*\'>'\,,out]deepmap

```

Try it online!

Takes input from the top of the stack and leaves output on STDOUT. This is simple as doing a depth map, repeating `-` `d` times, concatenating with '\>' and the element itself.
> 0 votes

# Answer
# jq, ~~70~~ 67 characters

(~~67~~ 64 characters code + 3 characters command line option)

```
def f(i):if type=="array"then.[]|f("-"+i)else i+. end;.[]|f(">")

```

Sample run:

```
bash-4.3$ jq -r 'def f(i):if type=="array"then.[]|f("-"+i)else i+. end;.[]|f(">")' <<< '[["1","2"],[["1","2"],"3"],"4",[[[["5"]]]],"6"]'
->1
->2
-->1
-->2
->3
>4
---->5
>6

```

On-line test
> 0 votes

# Answer
# Gema, 63 characters

```
\A=@set{i;-1}
[=@incr{i}
]=@decr{i}
"*"=@repeat{$i;-}>*\n
,<s>=

```

Like the other parsing solutions, assumes there will be no escaped double quotes in the strings.

Sample run:

```
bash-4.3$ gema '\A=@set{i;-1};[=@incr{i};]=@decr{i};"*"=@repeat{$i;-}>*\n;,<s>=' <<< '[["1","2"],[["1","2"],"3"],"4",[[[["5"]]]],"6"]'
->1
->2
-->1
-->2
->3
>4
---->5
>6

```
> 0 votes

---
Tags: code-golf, printable-ascii
---


title: Symbolic matrix multiplication

text:
# Question
Title: Symbolic matrix multiplication
There are lots of different ways to explain matrix multiplication. I'll stick with a single figure since I believe most people here are familiar with it (and the figure is very descriptive). If you want more detailed information, I suggest you visit the Wikipedia-article, or the explanation on WolframMathWorld.

**Simple explanation:**

Suppose you have two matrices, **A** and **B**, where **A** is 3-by-2, and **B** is 2-by-3. If you perform matrix multiplication on these to matrices, either **AB**, or **BA** you'll get the results below:

## Challenge:

Implement *symbolic* matrix multiplication in you language. You shall take two matrices as input, where each element in the matrices are represented by an non-whitespace ASCII-character (code points 33-126). You must output the product of these matrices.

**Rules regarding output:**

A product of two entries shall not have any symbols in between. It's `ab`, not `a*b`, `a·b`, `times(a,b)` or something similar. It's `aa`, not `a^2`.

The sum of terms should have a space (ASCII code point 32) in between. It's `a b`, not `a+b`, `plus(a,b)` or something similar.

The rationale for those two rules is: All non white space characters are allowed as symbols in the matrices, thus using them as mathematical symbols would be messy. So, what you could normally write as `a*b+c*d` will be `ab cd`.

You may choose the order of the terms. `ab cd`, `dc ab` and `cd ba` are mathematically speaking the same, so you can choose the order here too. The order need not be consistent as long as it's mathematically correct.

**Rules regarding matrix formatting:**

A matrix can be entered in whatever format you like, except a single string with no delimiters between rows (this is because the output would be completely messed up). Both matrices must be inputted on the same format. All the examples below are valid ways of entering and outputting a matrix.

```
"ab;cd"     <- This will look awful, but it's still accepted.

"a,b\nc,d"

[[a,b],[c,d]]

[a, b]
[c, d]

```

I'm aware that this allows a lot of formats that will look messy, but the challenge is about multiplying matrices, not formatting the output.

**General rules:**

* You may assume valid input. Matrix multiplication will always be possible with the given dimensions.
* There will only be two matrices.
* You may assume that the matrices are non-empty
* Built-in functions are accepted (but probably a bit cumbersome due to the formatting requirements).
* You may of course use escape characters in the input if necessary (`\'` instead of `'`).
* Any standard input and output method is OK.

## Test cases:

The two input matrices are shown with an empty line in between. The output is shown after `Output:`. When there are two output matrices then it's just to show other outputs that would be accepted.

**Test case #1**

```
Inputs:
[a]

[b]

Output:
[ab]
[ba]      <- Also OK

```

**Test case #2**

```
Inputs:
[a, b]
[1, 4]
[y, {]

[%, 4, 1]
[a, b, c]

Output:
[a% ba, a4 bb, a1 bc]
[1% 4a, 14 4b, 11 4c]
[y% {a, y4 {b, y1 {c]

```

**Test case #3:**

```
Inputs:
[1, 2, 3, 4]
[5, 6, 7, 8]
[9, 1, 2, 3]
[4, 5, 6, 7]

[a]
[b]
[c]
[d]

Output:
[1a 2b 3c 4d]
[5a 6b 7c 8d]
[9a 1b 2c 3d]
[4a 5b 6c 7d]

[d4 c3 b2 a1]      <-- Also OK
[d8 c7 b6 a5]
[1b 9a c2 3d]
[a4 b5 d7 6c]

```

If your response to the rules about requiring `ab cd` instead of `a*b+c*d` is: you should avoid cumbersome input/output formats, then I'd like note that the input and output formats are very flexible. The fact that you can't use `*` and `+` for products and sums might make it harder to use a simple built-in, but I don't consider that negative thing.

# Answer
# Haskell, ~~62~~ ~~61~~ 59 bytes

```
e=[]:e
z=zipWith
a!b=[unwords.z(++)r<$>foldr(z(:))e b|r<-a]

```

Try it online!

Example usage:

```
Prelude> [["a","b"],["c","e"]] ! [["f","g"],["h","i"]]
[["af bh","ag bi"],["cf eh","cg ei"]]

```

I found a way to get a `transpose` function in one byte shorter than using the import.

```
import Data.List;transpose
e=[]:e;foldr(zipWith(:))e

```

As the code then uses `zipWith` twice, two more bytes can be saved with the abbreviation `z=zipWith`.

---

**Old version with import:** (62 bytes)

```
import Data.List
a!b=[unwords.zipWith(++)r<$>transpose b|r<-a]

```

Try it online!

This is quite similar to my answer to non-symbolic matrix multiplication: `a!b=[sum.zipWith(*)r<$>transpose b|r<-a]`, substituting the multiplication `(*)` with string concatenation `(++)` and `sum` with `unwords` which concatenates a list of strings with a space in between. The import is needed for the `transpose` function, so all in all the transposition of the second matrix uses up half of the bytes ...

---

**Old version without import:** (64 bytes)

```
a![]=[];a!b=(unwords.zipWith(++)[h|h:_<-b]<$>a):a![s:t|_:s:t<-b]

```

Try it online!

With the import and `transpose` function taking up so much bytes, I tried solving the task without import. So far this approach turned out being two bytes longer, but it might be more golfable. *Edit: The other approach at the top now beats the import!*

The list comprehension `[s:t|_:s:t<-b]` gets the non-empty tails of the lists in `b`, using just `[t|_:t<-b]` to get the tails would be 4 bytes shorter (even beating the import version) but append an empty row like `["","",""]` to the matrix which I suppose is not allowed.
> 9 votes

# Answer
## Ruby, 61 bytes

```
->a,b{a.map{|x|b.transpose.map{|y|x.zip(y).map(&:join)*' '}}}

```

Sample run:

```
main(0):007> ->a,b{a.map{|x|b.transpose.map{|y|x.zip(y).map(&:join)*' '}}}[[[?a, ?b], [?1, ?4], [?y, ?{]], [[?%, ?4, ?1], [?a, ?b, ?c]]]
=> [["a% ba", "a4 bb", "a1 bc"], ["1% 4a", "14 4b", "11 4c"], ["y% {a", "y4 {b", "y1 {c"]]

```

```
->a,b{
a.map{|x|            # for each row of a
b.transpose.map{|y|  # and for each column of b
x.zip(y)             # match up corresponding elements
.map(&:join)         # join each pair together
*' '                 # join the entire thing on space
}}}

```
> 6 votes

# Answer
## Mathematica, 36 bytes

```
Inner[#<>#2&,##,StringRiffle@*List]&

```

`Inner` is a generalisation of Mathematica's `Dot` (i.e. the usual matrix/vector product). It generalises the dot product by letting you provide two function `f` and `g`, which will be used in place of the usual multiplication and addition, respectively. We're replacing the multiplication with `#<>#2&` (which joins the the two characters into a single string) and the addition with `StringRiffle@*List`, which first wraps all the summands in a list, and then `StringRiffle` joins them together with spaces.

One could potentially use the `Dot` operator `.` and then transform the result, but the trouble is that things like `"a"*"a"` would immediately get transformed into `"a"^2` (same for sums), which would be annoying to pick apart again.
> 6 votes

# Answer
## Clojure, 53 bytes

```
#(for[a %](for[b(apply map vector %2)](map str a b)))

```

Running with arguments `[["a" "b"]["c" "e"]]` and `[["f" "g"]["h" "i"]]` returns `((("af" "bh") ("ag" "bi")) (("cf" "eh") ("cg" "ei")))`. This is actually shorter than the numeric version.
> 4 votes

# Answer
# Jelly, 7 bytes

```
Z;"þK€€

```

This is a dyadic link that takes **B** and **A** as arguments (in that order) and returns **AB**. Input and output are in the form of 2D arrays of strings, which are actually 3D arrays of characters. A further byte could be saved by taking 2D arrays of *characters* as input. I'm not sure if that's allowed.

Try it online!

It's a bit hard to determine what Jelly does under the hood when strings are involved, since it does a lot of splattening before printing. This is how Jelly represents input and output internally.

### How it works

```
Z;"þK€€  Dyadic link. Left argument: B. Right argument: A

Z        Zip/transpose B.
 ;"þ     Table vectorized concatenation; for each row in B' and each row in A,
         concatenate the corresponding strings.
    K€€  Join the arrays that correspond to the rows of A by spaces.

```
> 3 votes

# Answer
# Dyalog APL, 10 bytes

Takes matrices of characters as left and right arguments. Returns matrix of lists of characters. (APL represents strings as lists of characters.)

```
{∊⍺' '⍵}.,

```

TryAPL online!

Normal inner product is in APL `+.×`, but the addition and multiplication can be any functions, in particular:

Addition has been replaced by
`{` an anonymous function:
the flattened
`⍺ ' ' ⍵` list consisting of the left argument, a space, and the right argument
`}`

Multiplication has been replaced by concatenation, `,`
> 3 votes

# Answer
## Prolog, \>256 Bytes

I am using { _ | _ } which is a findall/3, _ \[ _ , _ \] which is some arg/3, and sum(\_) which is some aggregate. They can all be used inside is/2:

```
*(X, Y, Z) :- functor(Y, matrice, _), L is len(X[1]), L =:= len(Y), !,
   M is len(X), N is len(Y[1]),
   Z is { { sum({ X[J,K] * Y[K,I] | between(1,L,K) })
                                  | between(1,N,I) }
                                  | between(1,M,J) }.

```

Together with the extra definitions for the aforementioned predicates and the non-standard is/2 that can return more than numbers, its sure \>256 bytes.
> 2 votes

# Answer
## JavaScript (ES6), 65 bytes

```
(a,b)=>a.map(c=>b[0].map((_,j)=>c.map((e,i)=>e+b[i][j]).join` `))

```

Takes input as two 2D arrays of characters and returns a 2D array of strings. Add 10 bytes to support input as two 1D arrays of strings.
> 1 votes

# Answer
# Pyth, 14 bytes

```
clQmj;sMCd*QCE

```

A program that takes input of two newline-separated two-dimensional lists of characters and prints a two dimensional list of strings.

Test suite

**How it works**

*\[Explanation coming later\]*
> 1 votes

# Answer
# Pip, 17 bytes

```
{Y Zb{a._JsMy}Ma}

```

This is a function that takes two nested lists of (single-character) strings and returns a nested list of strings. Try it online! (with two test cases).

### Explanation

Arguments to a `{}`-delimited function are assigned to the local variables `a` to `e`. The first argument of a lambda function is represented by `_`.

```
{               }  Define a function:
   Zb              Zip rows of b, transposing it
 Y                 Yank into global variable y for access in nested function
     {       }Ma   To the rows of a, map this function:
           My       To the rows of y (i.e. columns of b), map this function:
      a._           Concatenate, itemwise, the current row of a and row of y
         Js         Join the resulting list on space
                   The result of the outer map operation is returned

```
> 1 votes

---
Tags: code-golf, math, matrix, linear-algebra
---


title: Divide and divide and conquer

text:
# Question
Title: Divide and divide and conquer
Sometimes, when I'm idly trying to factor whatever number pops up in front of me¹, after a while I realize it's easier than I thought. Take `2156` for example: it eventually occurs to me that both `21` and `56` are multiples of `7`, and so certainly `2156 = 21 x 100 + 56` is also a multiple of `7`.

Your task is to write some code that identifies numbers that are easier to factor because of a coincidence of this sort.

## More precisely:

Write a program or function that takes a positive integer `n` as input, and returns a truthy value if there exists a divisor `d` (greater than `1`) such that `n` can be chopped in two to yield two positive integers, each of which is a multiple of `d`; return a falsy value if not.

* "Chopped in two" means what you think: the usual base-10 representation of `n` partitioned at some point into a front half and a back half to yield two other base-10 integers. It's okay if the second integer has a leading zero (but note that it must be a positive integer, so splitting `1230` into `123` and `0` is not valid).
* The truthy and falsy values can depend on the input. For example, if any nonzero integer is truthy in your language of choice, then you are welcome to return the divisor `d` or one of the "pieces" of `n` (or `n` itself for that matter).
* For example, any even number with at least two digits in the set `{2, 4, 6, 8}` will yield a truthy value: just split it after the first even digit. Also for example, any prime number `n` will yield a falsy value, as will any one-digit number.
* Note that it suffices to consider prime divisors `d`.
* You may assume the input is valid (that is, a positive integer).

This is , so the shortest code in bytes wins. But solutions in all languages are welcome, so we can strive for the shortest code in each language, not just the shortest code overall.

## Test cases

(You only have to output a truthy or falsy value; the annotations below are just by way of explanation.) Some inputs that yield truthy values are:

```
39  (3 divides both 3 and 9)
64  (2 divides both 6 and 4)
497  (7 divides both 49 and 7)
990  (splitting into 99 and 0 is invalid; but 9 divides both 9 and 90)
2233  (11 divides both 22 and 33)
9156  (3 divides both 9 and 156; or, 7 divides both 91 and 56)
11791  (13 divides both 117 and 91)
91015  (5 divides both 910 and 15)
1912496621  (23 divides both 1912496 and 621; some splittings are multiples of 7 as well)
9372679892  (2473 divides both 937267 and 9892; some splittings are multiples of 2 as well)

```

Some inputs that yield falsy values are:

```
52
61
130  (note that 13 and 0 is not a valid splitting)
691
899
2397
9029
26315
77300  (neither 7730 and 0 nor 773 and 00 are valid splittings)
2242593803

```

¹ yes I really do this

# Answer
## Retina, ~~31~~ 29 bytes

```

,$';$`
\d+
$*
;(11+)\1*,\1+;

```

Try it online!

Outputs a positive integer for valid inputs and zero for invalid ones.

I wouldn't recommend waiting for the larger test cases...

### Explanation

```

,$';$`

```

At each position of the input insert a comma, then everything before that position, then a semicolon, then everything after this position. What does that do? It gives us all possible splittings of a number (split by `,`, separated by `;`), and then the input again at the end. So input `123` becomes

```
,123;1,23;12,3;123,;123
     ^     ^     ^

```

where I've marked the original input characters (the stuff that isn't marked is what we inserted). Note that this creates invalid splittings that aren't actual splittings and it also doesn't care whether the trailing component is all zeros, but we'll avoid accepting those later. The benefit of creating the invalid splittings is that we know that each *valid* splitting has a `;` in front and after it, so we can save two bytes on word boundaries.

```
\d+
$*

```

Convert each number to unary.

```
;(11+)\1*,\1+;

```

Match a splitting by matching both halves as multiples of some number that's at least 2.
> 7 votes

# Answer
# Brachylog (2), 8 bytes

```
~c₂ḋᵐ∋ᵐ=

```

Try it online!

## Explanation

```
~c₂ḋᵐ∋ᵐ=
~c₂       Split the input into two pieces
    ᵐ ᵐ   On each of those pieces:
   ḋ ∋      Choose a prime factor
       =  such that both the chosen factors are equal

```

Clearly, if the same number (greater than 1) divides both pieces, the same *prime* number will divide both. Requiring the factor to be prime neatly disallows 1 as a factor. It also prevents a literal `0` being chosen as a segment of a number (because `0` has no prime factorization, and will cause  to fail).

There's no need to check against matching internal zeroes; if a split of `x` and `0y` is valid, `x0` and `y` will work just as well (and going the other way, if `x0` and `y` works, then we have a working solution regardless of whether `x` and `0y` would work or not).

A Brachylog full program, like this one, returns a Boolean; `true.` if there's some way to run it without failure (i.e. to make choices such that no error occurs), `false.` if all paths lead to failure. That's exactly what we want here.
> 6 votes

# Answer
# Jelly, ~~14~~ ~~12~~ ~~11~~ 10 bytes

```
ŒṖḌo1g/€P>

```

*Thanks to @JonathanAllan for golfing off 1 byte!*

Try it online!

### How it works

```
ŒṖḌo1g/€P>  Main link. Argument: n

ŒṖ          Compute all partitions of n's decimal digits.
  Ḍ         Undecimal; convert each array in each partition back to integer.
   o1       OR 1; replace disallowed zeroes with ones.
     g/€    Reduce (/) each (€) partition by GCD (g).
            The last GCD corresponds to the singleton partition and will always be
            equal to n. For a falsy input, all other GCDs will be 1.
        P   Take the product of all GCDs.
         >  Compare the product with n.

```
> 4 votes

# Answer
## Mathematica, ~~63~~ 62 bytes

(1 byte thanks to Greg Martin)

```
1<Max@@GCD@@@Table[1~Max~#&/@Floor@{Mod[#,t=10^n],#/t},{n,#}]&

```

It's a function that takes an integer as input and returns `True` or `False`. If you test it on a big number, bring a book to read while you wait.

Explanation:

* `Floor@{Mod[#,t=10^n],#/t}` arithmetically splits the input into its last `n` digits and the remaining `m-n` digits (where `m` is the total number of digits).
* `Table[1~Max~#&/@...,{n,#}]` does this for every `n` up to the input number. (This is way too big. We only need to do this up to the number of *digits* of the input, but this way saves bytes and still gives the correct result.) The `1~Max~#&/@` bit gets rid of zeroes, so numbers like `130 -> {13,0}` don't count as `True`.
* `1<Max@@GCD@@@...` finds the greatest common divisor of each of these pairs, and checks if any of these divisors are more than 1. If they are, we've found a way to factor the number by splitting it.
> 3 votes

# Answer
# Haskell, 57 bytes

```
x#n|b<-mod x n=x>n&&(b>0&&gcd(div x n)b>1||x#(10*n))
(#1)

```

Try it online! Usage: `(#1) 2156`, returns `True` or `False`
> 3 votes

# Answer
# Python 3, ~~133~~ ~~118~~ 117 bytes

```
i,j=int,input()
from fractions import*
print(any(i(j[k:])*i(j[:k])*~-gcd(i(j[k:]),i(j[:k]))for k in range(1,len(j))))

```

Certainly not the shortest, probably could be shortened a bit. Works in `O(n)` time. Input is taken in format `\d+` and output is given in format `(True|False)` as per default Python boolean value
-3 bytes thanks to Dead Possum
-15 bytes thanks to ovs
-1 byte thanks to This Guy
> 2 votes

# Answer
## JavaScript (ES6), ~~74~~ ~~71~~ 70 bytes

```
f=(s,t='',u)=>u?s%t?f(t,s%t,1):t:s&&f(t+=s[0],s=s.slice(1),1)>1|f(s,t)
```

```
<input oninput=o.textContent=f(this.value)><span id=o>
```

Takes input as a string, which is handy for the snippet. Edit: Saved 3 bytes thanks to @user81655.
> 2 votes

# Answer
# C, ~~145~~ ~~142~~ ~~139~~ ~~138~~ 135 bytes

```
i,a,b;f(){char s[99];scanf("%s",s);for(char*p=s;*p++;)for(b=atoi(p),i=*p,*p=0,a=atoi(s),*p=i,i=1;i++<b;)*s=a%i-b%i|b%i?*s:0;return!*s;}

```
> 2 votes

# Answer
## QBIC, ~~91~~ 90 bytes

```
;_LA|[a-1|B=left$(A,b)┘C=right$(A,a-b)┘x=!B!┘y=!C![2,x|~(x>1)*(y>1)*(x%c=0)*(y%c=0)|_Xq}?0

```

Explanation:

```
;               Get A$ from the command prompt
_LA|            Get the length of A$ and place it in a% (num var)
[a-1|           for b%=1; b% <= a%-1; b%++
B=left$(A,b)    break A$ in two components on index b%
C=right$(A,a-b)
x=!B!┘y=!C!     Convert both parts from string to num, assign to x% and y%
[2,x|           FOR c% = 2; c% <= x%; c%++

This next IF (~ in QBIC) is a bit ... iffy. It consists of a set of comparators.
Each comparator yields a -1 or a 0. We take the product of these. At any failed
comparison this will yield 0. When successful, it yields 1, which is seen as true by QBasic.

~(x>1)*(y>1)        IF X>1 and Y>1 --> this stops '00' and '1' splits.
*(x%c=0)*(y%c=0)    Trial divide the splits on loop counter c%.

|_Xq            Success? THEN END, and PRINT q (which is set to 1 in QBIC)
}               Close all language constructs (2 FOR loops and an IF)
?0              We didn't quit on match, so print 0

```
> 1 votes

# Answer
# Python 3, ~~70~~ 69 bytes

```
import math
f=lambda n,d=1:n>d and n%d*~-math.gcd(n//d,n%d)+f(n,10*d)

```

Try it online!
> 1 votes

# Answer
# Perl 5, 46 bytes

43 bytes of code + 3 bytes for `-p` flag.

```
s~~$\|=grep!($`%$_|$'%$_),2..$`if$`*$'~ge}{

```

Try it online! or try this modified version allowing multiple inputs.
You probably don't want to try this on the largest input, as it might take a (very long) while.

**Explanations:**
We iterate through each position in the word with `s~~~g`, with `$`` containing the numbers before and `$'` the numbers after. If `$`*$'` is true (it means that none is empty, and none is `0`), then we check if a number between 2 and `$`` divides both of them (with the `grep!(...),2..$``). If so, `$\|=..` will set `$\` to a non-zero value, which is implicitly printed at the end thanks to `-p` flag.
> 1 votes

# Answer
# Python 2, 69 bytes

```
f=lambda n,d=10,k=2:k<d<n and(n/d%k+n%d%k<1<n%d)|f(n,d,k+1)|f(n,10*d)

```

Uses recursion instead of GCD built-ins.

Try it online!

### How it works

When **f** is called with one to three arguments (**d** defaults to **10**, **k** to **2**), it first checks the value of the expression `k<d<n`. If the inequalities **k \< d** and **d \< n** both hold, the expression following `and` gets executed and its value is returned; otherwise, **f** will simply return *False*.

In the former case, we start by evaluating the expression `n/d%k+n%d%k<1<n%d`.

**d** will always be a power of ten, so `n/d` and `n%d` effectively split the decimal digits on **n** into two slices. These slices are both divisible by **k** if and only if `n/d%k+n%d%k` evaluates to **0**, which is tested by comparing the result with **1**.

Since part of the requirements is that both slices must represent positive integers, the value of `n%d` is also compared with **1**. Note that **1** has no prime divisors, so the more expensive comparison with **0** is not required. Also, note that **d \< n** already ensures that `n/d` will evaluate to a positive integer.

Finally it recursively all `f(n,d,k+1)` (trying the next potential common divisor) and `f(n,10*d)` (trying the splitting) and returns the logical OR of all three results. This means **f** will return *True* if (and only if) **k** is a common divisor of **n/d** and **n%d** or the same is true for a larger value of **k** and/or a higher power of ten **d**.
> 0 votes

---
Tags: code-golf, number-theory
---


title: How Many Holes?

text:
# Question
Title: How Many Holes?
# Challenge

Given a graphical input of a shape, determine how many holes there are in it.

# Not Duplicate

This question was marked as a possible duplicate of Count Islands. I believe this challenge is different from the Count Island challenge because in this one, you have to figure out how to eliminate blocks that touch the border.

# Input

Input will be given as some 2D form of input, either a multiline string, an array of strings, or an array of character arrays. This represents the shape. The shape is guaranteed to be in only one piece, connected by edge. Please specify how you want input to be taken.

# Output

Output is a single integer stating how many holes there are in the shape. A trailing newline is permitted, but no other leading or trailing whitespace. In other words, the output must match the regular expression `^\d+\n?$`.

# What is a hole?

These are single holes:

```
####
#  #
#  #
####

####
#  #
# ##
###

#####
# # #
#   #
#####

```

These are not holes:

```
########
########
#   ####
#   ####
# ######
#
########

###
#
###

##########
#
# ########
# #      #
# # #### #
# #   ## #
# ###### #
#        #
##########

```

Pretty much, if it the gap joins the outside edge, it is not a hole.

# Test cases

```
#####
# # # -> 2
#####

#####
#
# ### -> 1
# # #
#####

####
## # -> 1 (things are connected by edges)
# ##
####

###
### -> 0 (You must handle shapes with no holes, but input will always contain at least one filled space)
###

```

You can use any character in place of the '#', and in place of the spaces.

# Objective Scoring Criteria

The score is given as the number of bytes in your program.

# Winning

The winner will be the submission with the lowest score, by April 4th.

# Answer
# MATLAB / Octave, 18 bytes

```
@(g)1-bweuler(g,4)

```

Try it online!

This is an anonymous function taking a logical matrix as input. The object is formed by the `true` entries (with the specified connectivity), the empty space are the `false` entries.

`bweuler` then calculates the euler number of the binary image represented by that matrix, that is the number of objects minus the number of holes.
> 14 votes

# Answer
## Mathematica, ~~59~~ 57 bytes

```
1/.ComponentMeasurements[#,"Holes",CornerNeighbors->0>1]&

```

There's a built-in for that. Takes input as a 2D matrix of `1`s (walls) and `0`s (holes). For convenience, here are all the test cases in this input format:

```
{{{1,1,1,1},{1,0,0,1},{1,0,0,1},{1,1,1,1}},
 {{1,1,1,1},{1,0,0,1},{1,0,1,1},{1,1,1,0}},
 {{1,1,1,1,1},{1,0,1,0,1},{1,0,0,0,1},{1,1,1,1,1}},
 {{1,1,1,1,1,1,1,1},{1,1,1,1,1,1,1,1},{1,0,0,0,1,1,1,1},{1,0,0,0,1,1,1,1},{1,0,1,1,1,1,1,1},{1,0,0,0,0,0,0,0},{1,1,1,1,1,1,1,1}},
 {{1,1,1},{1,0,0},{1,1,1}},
 {{1,1,1,1,1,1,1,1,1,1},{1,0,0,0,0,0,0,0,0,0},{1,0,1,1,1,1,1,1,1,1},{1,0,1,0,0,0,0,0,0,1},{1,0,1,0,1,1,1,1,0,1},{1,0,1,0,0,0,1,1,0,1},{1,0,1,1,1,1,1,1,0,1},{1,0,0,0,0,0,0,0,0,1},{1,1,1,1,1,1,1,1,1,1}},
 {{1,1,1,1,1},{1,0,1,0,1},{1,1,1,1,1}},
 {{1,1,1,1,1},{1,0,0,0,0},{1,0,1,1,1},{1,0,1,0,1},{1,1,1,1,1}},
 {{1,1,1,1},{1,1,0,1},{1,0,1,1},{1,1,1,1}}}

```

## Alternative solution, 59 bytes

This was my original approach. It's also based on the component-related built-ins, but doesn't count the holes directly (instead it treats the holes themselves as components).

```
Max@*MorphologicalComponents@*DeleteBorderComponents@*Image

```

Takes the same input format as above, but with the roles of `0`s and `1`s swapped.

The reason I need to convert this to an `Image` first is that, otherwise, Mathematica would consider all the `1`-cells as part of a single component (because it treats the matrix as a component-label matrix). Hence, if any `1`-cell borders the margin, it would delete all of them. When `DeleteBorderComponents` is used on an image instead, then it will do an implicit connectivity check to find the components.

Alternatively, I could call `MorphologicalComponents` *first*, which would turn the input into a suitable label matrix, but if I do `DeleteBorderComponents` second it's no longer guaranteed that the maximum component label corresponds to the number of components (because I might delete a smaller component).
> 9 votes

# Answer
## Python 2, 282 bytes

+100 to handle diagonal touches TT\_TT (do we really need that?)
-119 thanks to @Rod guidance :)

Try it online. Takes array of arrays of chars '#' and whitespace as input.

```
A=input()
c=0
X=len(A[0])-1
Y=len(A)-1
def C(T):
 x,y=T
 global g
 if A[y][x]<'#':
    if y<1or y==Y or x<1or x==X:g=0
    A[y][x]='#';map(C,zip([x]*3+[min(x+1,X)]*3+[max(x-1,0)]*3,[y,min(y+1,Y),max(y-1,0)]*3))
while' 'in sum(A,[]):i=sum(A,[]).index(' ');g=1;C((i%-~X,i/-~X));c+=g
print c

```

Searches for first whitespace and mark it as non-empty ('#'). Recursively check all of it's surrounding, while filling all empty cells. If any empty cell of current "hole" appears to be on border counter won't change, otherwise it would be increased by 1. Repeat process, until there is no more whitespaces.
> 4 votes

# Answer
# Perl 5, 154 bytes

152 bytes of code + 2 bytes for `-p0` flag.

```
s/^ | $/A/gm;s/^.*\K | (?=.*$)/A/&&redo;/.*/;$@="@+"-1;for$%(A,X){$~="(.?.?.{$@})?";(s/$%$~ /$%$1$%/s||s/ $~$%/$%$1$%/s)&&redo}s/ /X/&&++$\&&redo}{$\|=0

```

Try it online!

I think the code is quite self-explanatory.

---

If you need some explanations to understand, here are a few steps of the transformations done by the program on a simple input (coming from here), followed by some explanations bellow:

```
######
#
# ####
# #  #
#### #
######

######
#    A
# ####
# #  #
#### #
######

######
#AAAAA
#A####
#A#  #
#### #
######

######
#AAAAA
#A####
#A#X #
#### #
######

######
#AAAAA
#A####
#A#XX#
####X#
######

```

First, `s/^ | $/A/gm;s/^.*\K | (?=.*$)/A/&&redo` will replace the spaces in the border (1st regex for left/right, 2nd for bottom/top) with `A` (I choose that character quite arbitrary).
Then, we get the width the shape with `/.*/;$@="@+"-1;`.
Now, we want to replace every space that is connected to a `A` with a `A` (because if a space is connected to a `A`, it means it can't be part of a hole. That's done by `for$%(A,X){(s/$%(.?.?.{$@})? /$%$1$%/s||s/ (.?.?.{$@})?$%/$%$1$%/s)&&redo}`. (you'll notice that this is done once for the `A`s and one for the `X`s - explanations for the `X` are bellow). There are two regex here: `s/$%(.?.?.{$@})? /$%$1$%/s` deals with the spaces that are on the right or bottom of a `A`. And `s/ (.?.?.{$@})?$%/$%$1$%/s` with the spaces on top or left of a `A`.
At this point, the only spaces that are left in the string are part of holes.
While there are still spaces, we repeat:
\- To know how much holes there are, we replace a space with a `X` (`s/ /X/`) and increment the counter of holes (`$\++`), and redo the entire program (actually, we only want to redo the `for` loop, but it's less bytes to redo the whole program).
\- Then, the `for` loop will replace every space that is connected to a `X` with a `X`, as they are part of the same hole.
At the end, `$\|=0` ensures that if there are no holes, a `0` is printed instead of an empty string. And `$\` is implicitly printed thanks to `-p` flag.
> 4 votes

# Answer
## Python 2, 233 225 222 bytes

*math\_junkie: -8 bytes*

Takes 2d array of booleans/integers (0/1) as input

```
s=input()
o=[-1,0,1]
m=lambda x,y:0if x in[-1,len(s[0])]or y in[-1,len(s)]else 1if s[y][x]else(s[y].__setitem__(x,1),all([m(x+a,y+b)for a in o for b in o]))[1]
e=enumerate
print sum(m(x,y)-c for y,l in e(s)for x,c in e(l))

```

Try it online!

Formatted version:

```
s = input()
o = [-1, 0, 1]
m = lambda x,y:
    0 if x in [-1, len(s[0])] or y in [-1, len(s)]
      else
        1 if s[y][x]
          else
            (s[y].__setitem__(x, 1),
             all([m(x + a, y + b) for a in o for b in o]))[1]
e = enumerate
print sum(m(x, y) - c for y, l in e(s) for x, c in e(l))

```
> 3 votes

# Answer
# C# 7, 364 bytes

Less than happy with this... maybe someone else can sort it out... If I have the energy later I will invert the first loop, and see if that can help to trim the bounds checking.

```
using C=System.Console;class P{static void Main(){string D="",L;int W=0,H=0,z;for(;(L=C.ReadLine())!=null;H+=W=L.Length)D+=L;int[]S=new int[H*9];int Q(int p)=>S[p]<p?Q(S[p]):p;void R(int r)=>S[Q(r+=z)]=S[r]>0?z:0;for(z=H;z-->0;)if(D[z]<33){S[z]=z;R(1);R(W);R(W+1);R(W-1);}for(;++z<H;)S[Q(z)]*=z>H-W-2|z%W<1|z%W>W-2?0:1;for(;W<H;)z+=Q(W)<W++?0:1;C.WriteLine(z-H);}}

```

Try it online

Complete program, accepts input to standard in, output to standard out. Uses disjoint sets to determine provisional holes, and when kills any touch the borders (with some dodgyness for the top-edge).

Formatted and commented code:

```
using C=System.Console;

class P
{
    static void Main()
    {
        string D="", // the whole map
            L; // initally each line of the map, later each line of output

        // TODO: some of thse might be charable
        int W=0, // width, later position
            H=0, // length (width * height)
            z; // position, later counter

        // read map and width
        for(;(L=C.ReadLine())!=null; // read a line, while we can
                H+=W=L.Length) // record the width, and increment height
            D+=L; // add the line to the map

        // disjoint sets
        int[]S=new int[H*9]; // generousness (relieve some bounds checking)
        // note that S[x] <= x, because we call R with decending values of z

        // returns whatever p points to
        int Q(int p)=>S[p]<p?Q(S[p]):p;
        // points whatever r points to at z if r is empty
        void R(int r)=>S[Q(r+=z)]=S[r]>0?z:0; // note that is never called when z=0

        // fill out disjoint sets
        for(z=H;z-->0;)
            if(D[z]<33) // if cell is empty
            {
                S[z]=z; // point it at itself

                // point the things next  to z at z
                R(1);
                R(W);
                R(W+1);
                R(W-1);
            }

        // zero sets which are against the left, bottom, or right edges
        for(;++z<H;)
            S[Q(z)]*=z>H-W-2|z%W<1|z%W>W-2?0:1; // TODO?: this suggests inverting the first loop (NOTE: would break S[x]<=x)

        // starting from the second row, count all the sets that point to this cell (ignores any non-zeros pointing to first row)
        for(;W<H;)
            z+=Q(W)<W++?0:1;

        C.WriteLine(z-H);
    }
}

```
> 1 votes

# Answer
# Snails, 48 bytes

```
!{\ z`+~}\ {t\ z!.!~=((lu|u.+r)!(.,~},!{t\ z!.!~

```

Ungolfed:

```
!{
    (\   z)+
    ~
}
\
{
    t \
    z !.!~
    ={
        (lu|u.+r)
        !(.,~)
    }
},
!{
    t \
    z !.!~
}

```
> 1 votes

# Answer
## JavaScript (ES6), 192 bytes

```
v=a=>Math.min(...a=a.map(s=>s.length))==Math.max(...a);
f=(s,t=(u=` `.repeat(w=s.search`
`+1))+`
`+s.replace(/^|$/gm,` `)+`
`+u,v=t.replace(RegExp(`( |@)([^]{${w},${w+2}})?(?!\\1)[ @]`),`@$2@`))=>t!=v?f(s,v):/ /.test(t)?f(s,t.replace(` `,`@`))+1:-1
```

```
<textarea id=i rows=10 cols=10></textarea><input type=button value=Count onclick=o.textContent=/^[\s#]+$/.test(i.value)*v(i.value.split`\n`)?f(i.value):`Invalid_Entry`><span id=o>
```

Based on my answer to Detect Failing Castles. First the string is padded with spaces to make an area around the shape. The RegExp then looks for two adjacent squares, one containing an `@`, one containing a space, and replaces them both with an `@`. If it can't do this, it fills in a space with an `@` and counts this as a new hole. Finally one is subtracted to account for the surrounding area.
> 0 votes

---
Tags: code-golf, geometry, grid, counting
---