title: Shell Glob Golfing

text:
# Question
Title: Shell Glob Golfing
This task is to output the shortest path to a file, after glob expansion.

What is shell globbing? In most shells, you can use the `*` character in a path to represent any characters at the position. For example, If directory `foo` contains files `bar` `baz` and `asdf`, then `foo/b*` will expand to `foo/bar foo/baz`.

Now, lets say that the current directory contains a file called `ihavealongname` and nothing else. If I want to reference this file, I might type `*`, which will represent only that one file, rather than typing out the full name.

If the directory also contains a file called `ialsohavealongname`, I can't do `*`, as it will match both files. The I would have to do, at least, `ih*`.

The `*` pattern also works for matching directories above the file I'm looking for. If there are only two directories `foo` and `bar`, but `foo` contains only a file `baz` and `bar` contains file `asdf`, I can match `foo/baz` with `*/baz`. Or, even more concisely, `*/b*`. If `bar` was empty, `*/*` would work.

Your task: Given a string array of paths that represent the "current directory" and a single target path, output the shortest possible string that would expand to only that target path after expanding \*s.

The target path can be taken as it's own string, as an index into the array of paths, as the first item on the array of paths passed in, or some other convenient way that isn't hard-coding. Ask in comments if unsure.

The target path is guaranteed to be present in the "current directory".

You can assume that all paths contain only alphanumeric ASCII (and `/`s). You may take as input paths that are rooted (start with `/`) or relative (don't start with `/`).

If there are multiple equally short possibilities, return any or all of them.

This is , fewest bytes wins!

Test cases, thanks to Kevin Cruijssen.

# Answer
# Perl 5, ~~136~~ ~~107~~ 102 bytes

Includes `+2` for `n0`

Give list of files on STDIN. The first one is assumed to be the target file

```
perl -n0E '@a="";for$a(@a){s%%s/(?=$a
)/;/g;$$_//=push@a,map$_.$a,/./g,"\\w*";/^;/>/
;/&&1/!say$a=~s/\\w//gr%e}'
foo/barber/test
foo/barber/testing
foo/barber/coding
foo/test
foo/bar/test
^D

```

Just the code without making the newlines literal:

```
@a="";for$a(@a){s%%s/(?=$a\n)/;/g;$$_//=push@a,map$_.$a,/./g,"\\w*";/^;/>/\n;/&&1/!say$a=~s/\\w//gr%e}

```

Crashes intentionally after printing the solution.

Still seems too long (the use of `$a` and `1/0` are very awkward), but it's a start and should be reasonably efficient.

Try it online!

# How it works

The program builds candidate globs by growing them from the back to the front starting with the empty string. It does this in a breadth first way, so first globs of length 0 are tried (only \`\`), then length 1 (like `t`, `i`, `*`), next length 2 (like `fb`, `i*`, `*g`, `**`), next length 3 and so on until a glob is found that only matches the first path. This will then be the shortest glob that solves the problem (others of the same length may exist).

The globs of length `n+1` are generated from the globs of length `n` by prepending each character from the list of paths and also `*` in front of each glob of length `n`. So e.g. length 3 glob `*i*` will contribute length 4 globs `f*i*`, `o*i*`, `o*i*`, `/*i*`, `b*i*` ... `s*i*`, `t*i*` and finally `**i*`. Notice that every character from the list of input paths is prepended even if it appears multiple times or makes no sense whatsoever because it leads to something that can never match.

Doing this naively would lead to a combinatorial explosion. That is why every candidate glob gets evaluated for how useful it is by determining at which points in the paths it could match if the glob was used at the end of a complete glob. I do this by inserting a `;` at each place where a match is possible. For example for the glob `t*` I will get the string:

```
foo/barber/;tes;t
foo/barber/;tes;ting
foo/barber/coding
foo/;tes;t
foo/bar/;tes;t

```

This represents the "distinguishing power" of the glob. Every glob that has exactly the same distinguishing power is equally good. If you replace them by each other at the end of a complete glob they will all match exactly the same paths. So you can just as well use the shortest one.

So when considering the length `n` globs I first look at its distinguishing power. If it has been seen before there was another glob of length `n` or shorter that was already considered and expanded, so this glob is pointless and gets pruned. This will for example get rid of candidates like `**i*` since the same distinguishing power will already have been seen as `*i*`. It also prunes impossible candidates like `f*i*` since the distinguishing string will have no `;` and just be the original list of paths. Only the very first impossible glob will be accepted, all the others will be seen as having the same distinguishing power and will be pruned. And even that first one won't really get expanded since all expansions are still impossible and will be pruned when they are considered. Simularly `in*` will be pruned by `i*` etc.

The above leads to very aggressive pruning and the program is therefore able to handle complex cases in a very short time. A major inefficiency though is that it prefixes the candidate globs with all possible characters, not only the ones just before a `;` in target path part of the distinguishing string. All added characters that are not in front of a `;` are no problem since they lead to an impossible glob which will be pruned when it gets considered, but that still leaves the characters just before `;` in the other paths. So in the end the program also builds globs that will be able match any combination of the given paths. It has no idea that it should be concentrating on the first path.

Now consider a solution to the problem. In the given example that could be `*/*er/t`. This gives the following distinguishing string:

```
;f;o;o;/barber/test
foo/barber/testing
foo/barber/coding
foo/test
foo/bar/test

```

I recognize a solution by having a `;` at the first position (so it matches the first path) and not having a `;` at the start of any other path (so the others don't match)

With the algorithm explained I now get to the actual program:

The candidate globs will be in array `@a` which I loop over using variable `$a` which contains the glob currently under consideration. Instead of `*` in the glob I will however use `\w*` so `$a` is actually a regex instead of a glob. I'm going to abuse a weirdness of the perl for loop that you can append elements to the array being looped while the loop is running and these new elements will get picked up in the loop. Since when generating the length `n+1` globs all length `n` globs are already on array `@a` this is breadth first.

Due to the `-n0` option (implicit loop over the whole input) the list of paths is in `$_` as one big string with each path terminated with a newline

```
@a="";                    Start everything with the length 0 glob
for$a(@a){    }           Loop over candidates in a breadth first way

```

Inside the `{ }` we have:

```
s/(?=$a\n)/;/g            Loop over the paths and insert a ; at every
                          position that the suffix glob can match by
                          looking ahead and checking that the regex
                          under consideration can match up to the end of
                          the path we are in. The distinguishing sting is
                          now in `$_`.

```

Oops, I just destroyed `$_` and I will need it for the next loop. So wrap the actual working code inside

```
s%%  ...code.. %e

```

This matches the empty string at the start of `$_` and allows you to run code to determine what it gets replaced with. If I make sure that that code evaluates to the empty string `$_` will at the end remain unchanged even if I change `$_` during `code`.

Going back to just after I replaced `$_` by the distinguishing string:

```
$$_//= expression

```

This is like:

```
$seen{$_} //= expression

```

`//` in perl is`'defined or`. It's like a short circuiting `or` where the second argument is only evaluated if the first one is `undef`. And it can be combined with an assignment just like `+=` in some other languages. So if they key `$_` in hash `%seen` is `undef` (which is is what you get when accessing a non-existing element) only then execute expression and assign it as value to key `$_`. So if I make sure `expression` does not return `undef` that basically means "evaluate expression if and only if this is the first time we see that particular distinguishing string". And because `$_` is guaranteed to contain a `\n` it is in fact safe to abuse the perl global hash to store the distinguishing strings, so `$$_` instead of `$seen{$_}`

For the `expression` I use:

```
push@a,map$_.$a,/./g,"\\w*"

```

Basically "For every character (except newline) in the distinguishing string and also `*` prepend it to the current glob and push that on the array of candidate globs". Execpt I use `\w*` for `*` to get a valid regex (I could use `''` instead of `""` to get rid of one backslash but then I couldn't run my code from the command line). Notice that this also picks up the `;` and adds them to the candidate globs but when later testing them to the restored `$_` which has no `;` that will again be an impossible glob and get pruned.

```
/^;/>/\n;/ &&      If the distinguishing string corresponds to a solution

say$a=~s/\\w//gr   Then replace all \w* back to * and print the solution

1/!                Say returns 1 so this becomes a division by 0.
                   The program exits by crashing after solving it

```

Notice that `/^;/>/\n;/` has a value equivalent to the empty string in case a solution was not yet found, so this will function as empty replacement string and `$_` gets restored
> 8 votes

# Answer
# Java 10, ~~854~~ ~~824~~ ~~796~~ ~~738~~ ~~728~~ ~~703~~ ~~688~~ ~~655~~ ~~652~~ ~~647~~ 624 bytes

```
import java.util.*;a->f->{var L=new Stack();List<String>s;int i=999,j,k;for(var t:f.split("/")){s=new java.util.concurrent.CopyOnWriteArrayList();s.add(t);for(k=1;k>0;){k=0;for(var x:s)for(j=0;j<x.length();)if(!s.contains(f=x.substring(0,j)+"~"+x.substring(++j))){s.add(f);k=1;}}for(var x:s)s.add(x.replaceAll("~+","\\*"));L.add(s);}p(L,s=new Stack(),0,f="");for(var y:s){k=0;for(var x:a)if(x.matches(y.replace("*",".*"))&x.split("/").length==y.split("/").length)k++;if(k==1&(j=y.length())<i){f=y;i=j;}}return f;};void p(List L,List r,int d,String c){if(d==L.size())r.add(c);else for(var o:(List)L.get(d))p(L,r,d+1,c+"/"+o);}

```

What a mess.. This is certainly not an easy challenge in Java. ~~Can definitely be golfed by a couple hundred bytes, but I'm just glad it's finally working now.~~ Told ya. :)
-5 bytes thanks to *@ceilingcat*.
-23 bytes switching from Java 8 to Java 10

Input as a String-array of file-paths (with directories as separated items, and all items containing a leading `/`), and a String with input file-path to grop.

**Explanation:**

Try it online. (The test cases with `ialsohavealongname`/`ihavealongnameaswell` are slightly reduced in length and `s.add(x.replaceAll("~+","\\*"));` has been replaced with `{s.remove(x);s.add(x.replaceAll("~+","\\*"));}` to work in 5-10 seconds on TIO, instead of timing out after 60+ sec.)

```
import java.util.*;   // Required import for List and Stack

// Method with String-array and String parameters and String return-type
a->f->{
  var L=new Stack();  //  Create a List of Lists
  List<String>s;      //  List of Strings (uninitialized)
  int i=999,j,k;      //  Three integers (`i` starting at 999,
                      //   because 260 is the maximum file-path length in Windows)
  for(var t:f.split("/")){
                      //  Loop over the input file-path split by "/":
    s=new java.util.concurrent.CopyOnWriteArrayList();
                      //  Create a List (which we can modify while iterating it)
    s.add(t);         //  Add the input to this List
    for(k=1;k>0;){    //  Loop as long as there are new items added to the List
      k=0;            //   Reset the newAdded-flag to false
      for(var x:s)    //   And inner loop over the List
        for(j=0;j<t.length();)
                      //    Inner loop `j` in range [0,length-of-item):
          if(!s.contains(f=x.substring(0,j)+"~"+x.substring(++j))){
                      //     Replace the character at index `j` with a '~'
                      //     And if it's a new item:
            s.add(f); //      Add it to the List
            k=1;}}    //      And set the newAdded-flag to true
    for(var x:s)      //  Loop over the List again
      s.add(x.replaceAll("~+","\\*")));
                      //   And replace all 1 or more '~' with a single asterisk
                      //   (NOTE: To reduce bytes it doesn't remove the existing items)
    L.add(s);}        //   Add this List to the List of Lists
  p(L,s=new Stack(),0,"");
                      //  Generate all permutations of the groppings
                      //  (List `s` now contains all groppings of the given file-path)
  for(var y:s){       //  Loop over the groppings in the String-List:
    k=0;              //   Reset integer `k` to 0
    for(var x:a)      //   Inner loop over the input file-paths:
      if(x.matches(y.replace("*",".*"))
                      //    If the current file-path matches the current gropping
         x.split("/").length==y.split("/").length)
                      //    and the amount of slashes are the same:
         k++;         //     Increase integer `k` by 1
    if(k==1           //   If only one of the file-paths matched,
       &(j=y.length())<i){
                      //   and the length is shorter than `i`:
      f=y;            //    Replace the result with this gropping file-path
      i=j;}}          //    And also replace `i` with this shorter `j`
  return f;}          //  Finally return this shortest gropping file-path

// Separated method to generate gropping file-path permutations given a List of Lists
void p(List L,List r,int d,String c){
  if(d==L.size())     //  If we've reached the final depth
    r.add(c);         //   Add the current gropping-file path to the result-List
  else                //  Else:
    for(var o:(List)L.get(d))
                      //   Loop over the List of the current depth:
      p(L,r,d+1,      //    Recursive call with depth+1,
        c+"/"+o);}    //    and current + "/" + item of loop

```

**Additional general explanation:**

Example: Let's take `/foo, /foo/bar, /foo/barber, /foo/bar/test, /foo/barber/test, /foo/barber/testing, /foo/barber/coding, /foo/test` as given file-paths, and `foo/bar/test` as input file-path to grop.

1) I start by splitting the file-path input by `/`, and generate all file-groppings of these separated words:

```
foo: [foo, *oo, f*o, fo*, *o, *o*, f*, *]
bar: [bar, *ar, b*r, ba*, *r, *a*, b*, *]
test: [test, *est, t*st, te*t, tes*, *st, *e*t, *es*, t*t, t*s*, te*, *t, *s*, *e*, t*, *]

```

2) I then generate all permutations with these words in the same order (reapplying the `/` in between and at the front):

```
[/foo/bar/test, /foo/bar/*est, /foo/bar/t*st, /foo/bar/te*t, /foo/bar/tes*, /foo/bar/*st, /foo/bar/*e*t, /foo/bar/*es*, /foo/bar/t*t, /foo/bar/t*s*, /foo/bar/te*, /foo/bar/*t, /foo/bar/*s*, /foo/bar/*e*, /foo/bar/t*, /foo/bar/*, /foo/*ar/test, /foo/*ar/*est, /foo/*ar/t*st, /foo/*ar/te*t, /foo/*ar/tes*, /foo/*ar/*st, /foo/*ar/*e*t, /foo/*ar/*es*, /foo/*ar/t*t, /foo/*ar/t*s*, /foo/*ar/te*, /foo/*ar/*t, /foo/*ar/*s*, /foo/*ar/*e*, /foo/*ar/t*, /foo/*ar/*, /foo/b*r/test, /foo/b*r/*est, /foo/b*r/t*st, /foo/b*r/te*t, /foo/b*r/tes*, /foo/b*r/*st, /foo/b*r/*e*t, /foo/b*r/*es*, /foo/b*r/t*t, /foo/b*r/t*s*, /foo/b*r/te*, /foo/b*r/*t, /foo/b*r/*s*, /foo/b*r/*e*, /foo/b*r/t*, /foo/b*r/*, /foo/ba*/test, /foo/ba*/*est, /foo/ba*/t*st, /foo/ba*/te*t, /foo/ba*/tes*, /foo/ba*/*st, /foo/ba*/*e*t, /foo/ba*/*es*, /foo/ba*/t*t, /foo/ba*/t*s*, /foo/ba*/te*, /foo/ba*/*t, /foo/ba*/*s*, /foo/ba*/*e*, /foo/ba*/t*, /foo/ba*/*, /foo/*r/test, /foo/*r/*est, /foo/*r/t*st, /foo/*r/te*t, /foo/*r/tes*, /foo/*r/*st, /foo/*r/*e*t, /foo/*r/*es*, /foo/*r/t*t, /foo/*r/t*s*, /foo/*r/te*, /foo/*r/*t, /foo/*r/*s*, /foo/*r/*e*, /foo/*r/t*, /foo/*r/*, /foo/*a*/test, /foo/*a*/*est, /foo/*a*/t*st, /foo/*a*/te*t, /foo/*a*/tes*, /foo/*a*/*st, /foo/*a*/*e*t, /foo/*a*/*es*, /foo/*a*/t*t, /foo/*a*/t*s*, /foo/*a*/te*, /foo/*a*/*t, /foo/*a*/*s*, /foo/*a*/*e*, /foo/*a*/t*, /foo/*a*/*, /foo/b*/test, /foo/b*/*est, /foo/b*/t*st, /foo/b*/te*t, /foo/b*/tes*, /foo/b*/*st, /foo/b*/*e*t, /foo/b*/*es*, /foo/b*/t*t, /foo/b*/t*s*, /foo/b*/te*, /foo/b*/*t, /foo/b*/*s*, /foo/b*/*e*, /foo/b*/t*, /foo/b*/*, /foo/*/test, /foo/*/*est, /foo/*/t*st, /foo/*/te*t, /foo/*/tes*, /foo/*/*st, /foo/*/*e*t, /foo/*/*es*, /foo/*/t*t, /foo/*/t*s*, /foo/*/te*, /foo/*/*t, /foo/*/*s*, /foo/*/*e*, /foo/*/t*, /foo/*/*, /*oo/bar/test, /*oo/bar/*est, /*oo/bar/t*st, /*oo/bar/te*t, /*oo/bar/tes*, /*oo/bar/*st, /*oo/bar/*e*t, /*oo/bar/*es*, /*oo/bar/t*t, /*oo/bar/t*s*, /*oo/bar/te*, /*oo/bar/*t, /*oo/bar/*s*, /*oo/bar/*e*, /*oo/bar/t*, /*oo/bar/*, /*oo/*ar/test, /*oo/*ar/*est, /*oo/*ar/t*st, /*oo/*ar/te*t, /*oo/*ar/tes*, /*oo/*ar/*st, /*oo/*ar/*e*t, /*oo/*ar/*es*, /*oo/*ar/t*t, /*oo/*ar/t*s*, /*oo/*ar/te*, /*oo/*ar/*t, /*oo/*ar/*s*, /*oo/*ar/*e*, /*oo/*ar/t*, /*oo/*ar/*, /*oo/b*r/test, /*oo/b*r/*est, /*oo/b*r/t*st, /*oo/b*r/te*t, /*oo/b*r/tes*, /*oo/b*r/*st, /*oo/b*r/*e*t, /*oo/b*r/*es*, /*oo/b*r/t*t, /*oo/b*r/t*s*, /*oo/b*r/te*, /*oo/b*r/*t, /*oo/b*r/*s*, /*oo/b*r/*e*, /*oo/b*r/t*, /*oo/b*r/*, /*oo/ba*/test, /*oo/ba*/*est, /*oo/ba*/t*st, /*oo/ba*/te*t, /*oo/ba*/tes*, /*oo/ba*/*st, /*oo/ba*/*e*t, /*oo/ba*/*es*, /*oo/ba*/t*t, /*oo/ba*/t*s*, /*oo/ba*/te*, /*oo/ba*/*t, /*oo/ba*/*s*, /*oo/ba*/*e*, /*oo/ba*/t*, /*oo/ba*/*, /*oo/*r/test, /*oo/*r/*est, /*oo/*r/t*st, /*oo/*r/te*t, /*oo/*r/tes*, /*oo/*r/*st, /*oo/*r/*e*t, /*oo/*r/*es*, /*oo/*r/t*t, /*oo/*r/t*s*, /*oo/*r/te*, /*oo/*r/*t, /*oo/*r/*s*, /*oo/*r/*e*, /*oo/*r/t*, /*oo/*r/*, /*oo/*a*/test, /*oo/*a*/*est, /*oo/*a*/t*st, /*oo/*a*/te*t, /*oo/*a*/tes*, /*oo/*a*/*st, /*oo/*a*/*e*t, /*oo/*a*/*es*, /*oo/*a*/t*t, /*oo/*a*/t*s*, /*oo/*a*/te*, /*oo/*a*/*t, /*oo/*a*/*s*, /*oo/*a*/*e*, /*oo/*a*/t*, /*oo/*a*/*, /*oo/b*/test, /*oo/b*/*est, /*oo/b*/t*st, /*oo/b*/te*t, /*oo/b*/tes*, /*oo/b*/*st, /*oo/b*/*e*t, /*oo/b*/*es*, /*oo/b*/t*t, /*oo/b*/t*s*, /*oo/b*/te*, /*oo/b*/*t, /*oo/b*/*s*, /*oo/b*/*e*, /*oo/b*/t*, /*oo/b*/*, /*oo/*/test, /*oo/*/*est, /*oo/*/t*st, /*oo/*/te*t, /*oo/*/tes*, /*oo/*/*st, /*oo/*/*e*t, /*oo/*/*es*, /*oo/*/t*t, /*oo/*/t*s*, /*oo/*/te*, /*oo/*/*t, /*oo/*/*s*, /*oo/*/*e*, /*oo/*/t*, /*oo/*/*, /f*o/bar/test, /f*o/bar/*est, /f*o/bar/t*st, /f*o/bar/te*t, /f*o/bar/tes*, /f*o/bar/*st, /f*o/bar/*e*t, /f*o/bar/*es*, /f*o/bar/t*t, /f*o/bar/t*s*, /f*o/bar/te*, /f*o/bar/*t, /f*o/bar/*s*, /f*o/bar/*e*, /f*o/bar/t*, /f*o/bar/*, /f*o/*ar/test, /f*o/*ar/*est, /f*o/*ar/t*st, /f*o/*ar/te*t, /f*o/*ar/tes*, /f*o/*ar/*st, /f*o/*ar/*e*t, /f*o/*ar/*es*, /f*o/*ar/t*t, /f*o/*ar/t*s*, /f*o/*ar/te*, /f*o/*ar/*t, /f*o/*ar/*s*, /f*o/*ar/*e*, /f*o/*ar/t*, /f*o/*ar/*, /f*o/b*r/test, /f*o/b*r/*est, /f*o/b*r/t*st, /f*o/b*r/te*t, /f*o/b*r/tes*, /f*o/b*r/*st, /f*o/b*r/*e*t, /f*o/b*r/*es*, /f*o/b*r/t*t, /f*o/b*r/t*s*, /f*o/b*r/te*, /f*o/b*r/*t, /f*o/b*r/*s*, /f*o/b*r/*e*, /f*o/b*r/t*, /f*o/b*r/*, /f*o/ba*/test, /f*o/ba*/*est, /f*o/ba*/t*st, /f*o/ba*/te*t, /f*o/ba*/tes*, /f*o/ba*/*st, /f*o/ba*/*e*t, /f*o/ba*/*es*, /f*o/ba*/t*t, /f*o/ba*/t*s*, /f*o/ba*/te*, /f*o/ba*/*t, /f*o/ba*/*s*, /f*o/ba*/*e*, /f*o/ba*/t*, /f*o/ba*/*, /f*o/*r/test, /f*o/*r/*est, /f*o/*r/t*st, /f*o/*r/te*t, /f*o/*r/tes*, /f*o/*r/*st, /f*o/*r/*e*t, /f*o/*r/*es*, /f*o/*r/t*t, /f*o/*r/t*s*, /f*o/*r/te*, /f*o/*r/*t, /f*o/*r/*s*, /f*o/*r/*e*, /f*o/*r/t*, /f*o/*r/*, /f*o/*a*/test, /f*o/*a*/*est, /f*o/*a*/t*st, /f*o/*a*/te*t, /f*o/*a*/tes*, /f*o/*a*/*st, /f*o/*a*/*e*t, /f*o/*a*/*es*, /f*o/*a*/t*t, /f*o/*a*/t*s*, /f*o/*a*/te*, /f*o/*a*/*t, /f*o/*a*/*s*, /f*o/*a*/*e*, /f*o/*a*/t*, /f*o/*a*/*, /f*o/b*/test, /f*o/b*/*est, /f*o/b*/t*st, /f*o/b*/te*t, /f*o/b*/tes*, /f*o/b*/*st, /f*o/b*/*e*t, /f*o/b*/*es*, /f*o/b*/t*t, /f*o/b*/t*s*, /f*o/b*/te*, /f*o/b*/*t, /f*o/b*/*s*, /f*o/b*/*e*, /f*o/b*/t*, /f*o/b*/*, /f*o/*/test, /f*o/*/*est, /f*o/*/t*st, /f*o/*/te*t, /f*o/*/tes*, /f*o/*/*st, /f*o/*/*e*t, /f*o/*/*es*, /f*o/*/t*t, /f*o/*/t*s*, /f*o/*/te*, /f*o/*/*t, /f*o/*/*s*, /f*o/*/*e*, /f*o/*/t*, /f*o/*/*, /fo*/bar/test, /fo*/bar/*est, /fo*/bar/t*st, /fo*/bar/te*t, /fo*/bar/tes*, /fo*/bar/*st, /fo*/bar/*e*t, /fo*/bar/*es*, /fo*/bar/t*t, /fo*/bar/t*s*, /fo*/bar/te*, /fo*/bar/*t, /fo*/bar/*s*, /fo*/bar/*e*, /fo*/bar/t*, /fo*/bar/*, /fo*/*ar/test, /fo*/*ar/*est, /fo*/*ar/t*st, /fo*/*ar/te*t, /fo*/*ar/tes*, /fo*/*ar/*st, /fo*/*ar/*e*t, /fo*/*ar/*es*, /fo*/*ar/t*t, /fo*/*ar/t*s*, /fo*/*ar/te*, /fo*/*ar/*t, /fo*/*ar/*s*, /fo*/*ar/*e*, /fo*/*ar/t*, /fo*/*ar/*, /fo*/b*r/test, /fo*/b*r/*est, /fo*/b*r/t*st, /fo*/b*r/te*t, /fo*/b*r/tes*, /fo*/b*r/*st, /fo*/b*r/*e*t, /fo*/b*r/*es*, /fo*/b*r/t*t, /fo*/b*r/t*s*, /fo*/b*r/te*, /fo*/b*r/*t, /fo*/b*r/*s*, /fo*/b*r/*e*, /fo*/b*r/t*, /fo*/b*r/*, /fo*/ba*/test, /fo*/ba*/*est, /fo*/ba*/t*st, /fo*/ba*/te*t, /fo*/ba*/tes*, /fo*/ba*/*st, /fo*/ba*/*e*t, /fo*/ba*/*es*, /fo*/ba*/t*t, /fo*/ba*/t*s*, /fo*/ba*/te*, /fo*/ba*/*t, /fo*/ba*/*s*, /fo*/ba*/*e*, /fo*/ba*/t*, /fo*/ba*/*, /fo*/*r/test, /fo*/*r/*est, /fo*/*r/t*st, /fo*/*r/te*t, /fo*/*r/tes*, /fo*/*r/*st, /fo*/*r/*e*t, /fo*/*r/*es*, /fo*/*r/t*t, /fo*/*r/t*s*, /fo*/*r/te*, /fo*/*r/*t, /fo*/*r/*s*, /fo*/*r/*e*, /fo*/*r/t*, /fo*/*r/*, /fo*/*a*/test, /fo*/*a*/*est, /fo*/*a*/t*st, /fo*/*a*/te*t, /fo*/*a*/tes*, /fo*/*a*/*st, /fo*/*a*/*e*t, /fo*/*a*/*es*, /fo*/*a*/t*t, /fo*/*a*/t*s*, /fo*/*a*/te*, /fo*/*a*/*t, /fo*/*a*/*s*, /fo*/*a*/*e*, /fo*/*a*/t*, /fo*/*a*/*, /fo*/b*/test, /fo*/b*/*est, /fo*/b*/t*st, /fo*/b*/te*t, /fo*/b*/tes*, /fo*/b*/*st, /fo*/b*/*e*t, /fo*/b*/*es*, /fo*/b*/t*t, /fo*/b*/t*s*, /fo*/b*/te*, /fo*/b*/*t, /fo*/b*/*s*, /fo*/b*/*e*, /fo*/b*/t*, /fo*/b*/*, /fo*/*/test, /fo*/*/*est, /fo*/*/t*st, /fo*/*/te*t, /fo*/*/tes*, /fo*/*/*st, /fo*/*/*e*t, /fo*/*/*es*, /fo*/*/t*t, /fo*/*/t*s*, /fo*/*/te*, /fo*/*/*t, /fo*/*/*s*, /fo*/*/*e*, /fo*/*/t*, /fo*/*/*, /*o/bar/test, /*o/bar/*est, /*o/bar/t*st, /*o/bar/te*t, /*o/bar/tes*, /*o/bar/*st, /*o/bar/*e*t, /*o/bar/*es*, /*o/bar/t*t, /*o/bar/t*s*, /*o/bar/te*, /*o/bar/*t, /*o/bar/*s*, /*o/bar/*e*, /*o/bar/t*, /*o/bar/*, /*o/*ar/test, /*o/*ar/*est, /*o/*ar/t*st, /*o/*ar/te*t, /*o/*ar/tes*, /*o/*ar/*st, /*o/*ar/*e*t, /*o/*ar/*es*, /*o/*ar/t*t, /*o/*ar/t*s*, /*o/*ar/te*, /*o/*ar/*t, /*o/*ar/*s*, /*o/*ar/*e*, /*o/*ar/t*, /*o/*ar/*, /*o/b*r/test, /*o/b*r/*est, /*o/b*r/t*st, /*o/b*r/te*t, /*o/b*r/tes*, /*o/b*r/*st, /*o/b*r/*e*t, /*o/b*r/*es*, /*o/b*r/t*t, /*o/b*r/t*s*, /*o/b*r/te*, /*o/b*r/*t, /*o/b*r/*s*, /*o/b*r/*e*, /*o/b*r/t*, /*o/b*r/*, /*o/ba*/test, /*o/ba*/*est, /*o/ba*/t*st, /*o/ba*/te*t, /*o/ba*/tes*, /*o/ba*/*st, /*o/ba*/*e*t, /*o/ba*/*es*, /*o/ba*/t*t, /*o/ba*/t*s*, /*o/ba*/te*, /*o/ba*/*t, /*o/ba*/*s*, /*o/ba*/*e*, /*o/ba*/t*, /*o/ba*/*, /*o/*r/test, /*o/*r/*est, /*o/*r/t*st, /*o/*r/te*t, /*o/*r/tes*, /*o/*r/*st, /*o/*r/*e*t, /*o/*r/*es*, /*o/*r/t*t, /*o/*r/t*s*, /*o/*r/te*, /*o/*r/*t, /*o/*r/*s*, /*o/*r/*e*, /*o/*r/t*, /*o/*r/*, /*o/*a*/test, /*o/*a*/*est, /*o/*a*/t*st, /*o/*a*/te*t, /*o/*a*/tes*, /*o/*a*/*st, /*o/*a*/*e*t, /*o/*a*/*es*, /*o/*a*/t*t, /*o/*a*/t*s*, /*o/*a*/te*, /*o/*a*/*t, /*o/*a*/*s*, /*o/*a*/*e*, /*o/*a*/t*, /*o/*a*/*, /*o/b*/test, /*o/b*/*est, /*o/b*/t*st, /*o/b*/te*t, /*o/b*/tes*, /*o/b*/*st, /*o/b*/*e*t, /*o/b*/*es*, /*o/b*/t*t, /*o/b*/t*s*, /*o/b*/te*, /*o/b*/*t, /*o/b*/*s*, /*o/b*/*e*, /*o/b*/t*, /*o/b*/*, /*o/*/test, /*o/*/*est, /*o/*/t*st, /*o/*/te*t, /*o/*/tes*, /*o/*/*st, /*o/*/*e*t, /*o/*/*es*, /*o/*/t*t, /*o/*/t*s*, /*o/*/te*, /*o/*/*t, /*o/*/*s*, /*o/*/*e*, /*o/*/t*, /*o/*/*, /*o*/bar/test, /*o*/bar/*est, /*o*/bar/t*st, /*o*/bar/te*t, /*o*/bar/tes*, /*o*/bar/*st, /*o*/bar/*e*t, /*o*/bar/*es*, /*o*/bar/t*t, /*o*/bar/t*s*, /*o*/bar/te*, /*o*/bar/*t, /*o*/bar/*s*, /*o*/bar/*e*, /*o*/bar/t*, /*o*/bar/*, /*o*/*ar/test, /*o*/*ar/*est, /*o*/*ar/t*st, /*o*/*ar/te*t, /*o*/*ar/tes*, /*o*/*ar/*st, /*o*/*ar/*e*t, /*o*/*ar/*es*, /*o*/*ar/t*t, /*o*/*ar/t*s*, /*o*/*ar/te*, /*o*/*ar/*t, /*o*/*ar/*s*, /*o*/*ar/*e*, /*o*/*ar/t*, /*o*/*ar/*, /*o*/b*r/test, /*o*/b*r/*est, /*o*/b*r/t*st, /*o*/b*r/te*t, /*o*/b*r/tes*, /*o*/b*r/*st, /*o*/b*r/*e*t, /*o*/b*r/*es*, /*o*/b*r/t*t, /*o*/b*r/t*s*, /*o*/b*r/te*, /*o*/b*r/*t, /*o*/b*r/*s*, /*o*/b*r/*e*, /*o*/b*r/t*, /*o*/b*r/*, /*o*/ba*/test, /*o*/ba*/*est, /*o*/ba*/t*st, /*o*/ba*/te*t, /*o*/ba*/tes*, /*o*/ba*/*st, /*o*/ba*/*e*t, /*o*/ba*/*es*, /*o*/ba*/t*t, /*o*/ba*/t*s*, /*o*/ba*/te*, /*o*/ba*/*t, /*o*/ba*/*s*, /*o*/ba*/*e*, /*o*/ba*/t*, /*o*/ba*/*, /*o*/*r/test, /*o*/*r/*est, /*o*/*r/t*st, /*o*/*r/te*t, /*o*/*r/tes*, /*o*/*r/*st, /*o*/*r/*e*t, /*o*/*r/*es*, /*o*/*r/t*t, /*o*/*r/t*s*, /*o*/*r/te*, /*o*/*r/*t, /*o*/*r/*s*, /*o*/*r/*e*, /*o*/*r/t*, /*o*/*r/*, /*o*/*a*/test, /*o*/*a*/*est, /*o*/*a*/t*st, /*o*/*a*/te*t, /*o*/*a*/tes*, /*o*/*a*/*st, /*o*/*a*/*e*t, /*o*/*a*/*es*, /*o*/*a*/t*t, /*o*/*a*/t*s*, /*o*/*a*/te*, /*o*/*a*/*t, /*o*/*a*/*s*, /*o*/*a*/*e*, /*o*/*a*/t*, /*o*/*a*/*, /*o*/b*/test, /*o*/b*/*est, /*o*/b*/t*st, /*o*/b*/te*t, /*o*/b*/tes*, /*o*/b*/*st, /*o*/b*/*e*t, /*o*/b*/*es*, /*o*/b*/t*t, /*o*/b*/t*s*, /*o*/b*/te*, /*o*/b*/*t, /*o*/b*/*s*, /*o*/b*/*e*, /*o*/b*/t*, /*o*/b*/*, /*o*/*/test, /*o*/*/*est, /*o*/*/t*st, /*o*/*/te*t, /*o*/*/tes*, /*o*/*/*st, /*o*/*/*e*t, /*o*/*/*es*, /*o*/*/t*t, /*o*/*/t*s*, /*o*/*/te*, /*o*/*/*t, /*o*/*/*s*, /*o*/*/*e*, /*o*/*/t*, /*o*/*/*, /f*/bar/test, /f*/bar/*est, /f*/bar/t*st, /f*/bar/te*t, /f*/bar/tes*, /f*/bar/*st, /f*/bar/*e*t, /f*/bar/*es*, /f*/bar/t*t, /f*/bar/t*s*, /f*/bar/te*, /f*/bar/*t, /f*/bar/*s*, /f*/bar/*e*, /f*/bar/t*, /f*/bar/*, /f*/*ar/test, /f*/*ar/*est, /f*/*ar/t*st, /f*/*ar/te*t, /f*/*ar/tes*, /f*/*ar/*st, /f*/*ar/*e*t, /f*/*ar/*es*, /f*/*ar/t*t, /f*/*ar/t*s*, /f*/*ar/te*, /f*/*ar/*t, /f*/*ar/*s*, /f*/*ar/*e*, /f*/*ar/t*, /f*/*ar/*, /f*/b*r/test, /f*/b*r/*est, /f*/b*r/t*st, /f*/b*r/te*t, /f*/b*r/tes*, /f*/b*r/*st, /f*/b*r/*e*t, /f*/b*r/*es*, /f*/b*r/t*t, /f*/b*r/t*s*, /f*/b*r/te*, /f*/b*r/*t, /f*/b*r/*s*, /f*/b*r/*e*, /f*/b*r/t*, /f*/b*r/*, /f*/ba*/test, /f*/ba*/*est, /f*/ba*/t*st, /f*/ba*/te*t, /f*/ba*/tes*, /f*/ba*/*st, /f*/ba*/*e*t, /f*/ba*/*es*, /f*/ba*/t*t, /f*/ba*/t*s*, /f*/ba*/te*, /f*/ba*/*t, /f*/ba*/*s*, /f*/ba*/*e*, /f*/ba*/t*, /f*/ba*/*, /f*/*r/test, /f*/*r/*est, /f*/*r/t*st, /f*/*r/te*t, /f*/*r/tes*, /f*/*r/*st, /f*/*r/*e*t, /f*/*r/*es*, /f*/*r/t*t, /f*/*r/t*s*, /f*/*r/te*, /f*/*r/*t, /f*/*r/*s*, /f*/*r/*e*, /f*/*r/t*, /f*/*r/*, /f*/*a*/test, /f*/*a*/*est, /f*/*a*/t*st, /f*/*a*/te*t, /f*/*a*/tes*, /f*/*a*/*st, /f*/*a*/*e*t, /f*/*a*/*es*, /f*/*a*/t*t, /f*/*a*/t*s*, /f*/*a*/te*, /f*/*a*/*t, /f*/*a*/*s*, /f*/*a*/*e*, /f*/*a*/t*, /f*/*a*/*, /f*/b*/test, /f*/b*/*est, /f*/b*/t*st, /f*/b*/te*t, /f*/b*/tes*, /f*/b*/*st, /f*/b*/*e*t, /f*/b*/*es*, /f*/b*/t*t, /f*/b*/t*s*, /f*/b*/te*, /f*/b*/*t, /f*/b*/*s*, /f*/b*/*e*, /f*/b*/t*, /f*/b*/*, /f*/*/test, /f*/*/*est, /f*/*/t*st, /f*/*/te*t, /f*/*/tes*, /f*/*/*st, /f*/*/*e*t, /f*/*/*es*, /f*/*/t*t, /f*/*/t*s*, /f*/*/te*, /f*/*/*t, /f*/*/*s*, /f*/*/*e*, /f*/*/t*, /f*/*/*, /*/bar/test, /*/bar/*est, /*/bar/t*st, /*/bar/te*t, /*/bar/tes*, /*/bar/*st, /*/bar/*e*t, /*/bar/*es*, /*/bar/t*t, /*/bar/t*s*, /*/bar/te*, /*/bar/*t, /*/bar/*s*, /*/bar/*e*, /*/bar/t*, /*/bar/*, /*/*ar/test, /*/*ar/*est, /*/*ar/t*st, /*/*ar/te*t, /*/*ar/tes*, /*/*ar/*st, /*/*ar/*e*t, /*/*ar/*es*, /*/*ar/t*t, /*/*ar/t*s*, /*/*ar/te*, /*/*ar/*t, /*/*ar/*s*, /*/*ar/*e*, /*/*ar/t*, /*/*ar/*, /*/b*r/test, /*/b*r/*est, /*/b*r/t*st, /*/b*r/te*t, /*/b*r/tes*, /*/b*r/*st, /*/b*r/*e*t, /*/b*r/*es*, /*/b*r/t*t, /*/b*r/t*s*, /*/b*r/te*, /*/b*r/*t, /*/b*r/*s*, /*/b*r/*e*, /*/b*r/t*, /*/b*r/*, /*/ba*/test, /*/ba*/*est, /*/ba*/t*st, /*/ba*/te*t, /*/ba*/tes*, /*/ba*/*st, /*/ba*/*e*t, /*/ba*/*es*, /*/ba*/t*t, /*/ba*/t*s*, /*/ba*/te*, /*/ba*/*t, /*/ba*/*s*, /*/ba*/*e*, /*/ba*/t*, /*/ba*/*, /*/*r/test, /*/*r/*est, /*/*r/t*st, /*/*r/te*t, /*/*r/tes*, /*/*r/*st, /*/*r/*e*t, /*/*r/*es*, /*/*r/t*t, /*/*r/t*s*, /*/*r/te*, /*/*r/*t, /*/*r/*s*, /*/*r/*e*, /*/*r/t*, /*/*r/*, /*/*a*/test, /*/*a*/*est, /*/*a*/t*st, /*/*a*/te*t, /*/*a*/tes*, /*/*a*/*st, /*/*a*/*e*t, /*/*a*/*es*, /*/*a*/t*t, /*/*a*/t*s*, /*/*a*/te*, /*/*a*/*t, /*/*a*/*s*, /*/*a*/*e*, /*/*a*/t*, /*/*a*/*, /*/b*/test, /*/b*/*est, /*/b*/t*st, /*/b*/te*t, /*/b*/tes*, /*/b*/*st, /*/b*/*e*t, /*/b*/*es*, /*/b*/t*t, /*/b*/t*s*, /*/b*/te*, /*/b*/*t, /*/b*/*s*, /*/b*/*e*, /*/b*/t*, /*/b*/*, /*/*/test, /*/*/*est, /*/*/t*st, /*/*/te*t, /*/*/tes*, /*/*/*st, /*/*/*e*t, /*/*/*es*, /*/*/t*t, /*/*/t*s*, /*/*/te*, /*/*/*t, /*/*/*s*, /*/*/*e*, /*/*/t*, /*/*/*]

```

3) Then I loop over the items in this list above and validate if it only matches a single file-path in the input array of file-paths. (I do this by checking two things: are the amount of slashes the same, and does it match the regex where every `*` is replaced with `.*`.)
If it does: keep the (first) shortest, which we return in the end.
> 7 votes

---
Tags: code-golf, string, file-system
---


title: Tetris strategy

text:
# Question
Title: Tetris strategy
Your task is to implement a Tetris strategy balanced in terms of score vs code size.

In this version of the game tetrominoes are rotated and dropped from above into a grid of 20 rows and 10 columns. While falling, they cannot be rotated or moved horizontally. As usual, a dropped piece stops when it reaches the bottom of the grid or when further downwards motion would cause collision with an already occupied square.

When `n` horizontal lines get filled completely, they collapse simultaneously, the grid is replenished with `n` empty lines at the top, and the score is incremented by 2n-1 points. For `n`=1,2,3,4 that's 1,3,7,15 points respectively. After the lines disappear, some blocks may remain floating in the air (there's no "gravity chain reaction").

When no room is available for the current piece to appear where desired, the grid is cleared, the current piece ignored, and the game continues with the next piece as current. There's no penalty for that.

You should read a stream of piece types and decide how to rotate them and where to drop them. Look-ahead for the next piece (just one) is allowed: you can look at piece `i+1` before responding to `i`, but you must have decided the fate of `i` before looking at `i+2`. No look-ahead is available beyond the last piece of the input.

Tetromino types and their rotations are encoded per the following table:

```
        type 0    1    2    3    4    5    6
             O    I    Z    J    L    S    T
            ┌────┬────┬────┬────┬────┬────┬────┐
 rotation 0 │##  │#   │##  │ #  │#   │ ## │### │
            │##  │#   │ ## │ #  │#   │##  │ #  │
            │    │#   │    │##  │##  │    │    │
            │    │#   │    │    │    │    │    │
            ├────┼────┼────┼────┼────┼────┼────┤
          1 │##  │####│ #  │### │  # │#   │#   │
            │##  │    │##  │  # │### │##  │##  │
            │    │    │#   │    │    │ #  │#   │
            │    │    │    │    │    │    │    │
            ├────┼────┼────┼────┼────┼────┼────┤
          2 │##  │#   │##  │##  │##  │ ## │ #  │
            │##  │#   │ ## │#   │ #  │##  │### │
            │    │#   │    │#   │ #  │    │    │
            │    │#   │    │    │    │    │    │
            ├────┼────┼────┼────┼────┼────┼────┤
          3 │##  │####│ #  │#   │### │#   │ #  │
            │##  │    │##  │### │#   │##  │##  │
            │    │    │#   │    │    │ #  │ #  │
            │    │    │    │    │    │    │    │
            └────┴────┴────┴────┴────┴────┴────┘

```

Input is binary - a sequence of bytes whose remainders when divided by 7 should be interpreted as the `OIZJLST` tetrominoes. They will occur with roughly the same probability (except that the first few types may appear slightly more often due to 256 not being a multiple of 7, but that should be negligible). Input can be from stdin or from a file named "i" or passed as an argument. You can read all of the input at once, provided you make sure to abide by the look-ahead restriction.

Output is binary too - a sequence of bytes of the same length as the input. It can be stdout or a file named "o" or the result from a function. Each byte encodes `r*16 + x`, where `r` is the desired rotation and `x` is the 0-based index of the column where the leftmost square of the rotated tetromino should go. Those `r` and `x` must be valid, i.e. `0 ≤ r ≤ 3` and `0 ≤ x ≤ 10-w`, where `w` is the width of the corresponding piece.

You program must be deterministic - given the same input, it has to produce exactly the same output. Using a PRNG is ok as long as it's const-seeded.

The total score is the score from the game minus the size of your code in bytes. Please use the following file (64kiB of pseudo-random noise) as input: https://gist.github.com/ngn/857bf2c99bfafc649b8eaa1e489e75e4/raw/880f29bd790638aa17f51229c105e726bce60235/i

The following python2/python3 script reads files "i" and "o" from the current directory, replays the game and prints the score (please remember to subtract your code size from the score):

```
a = [0] * 23 # grid (1square=1bit, 1row=1int, LSB is left, 3 empty rows on top)
#      O     I         Z       J       L       S       T        tetrominoes
t = [[[3,3],[1,1,1,1],[3,6],  [2,2,3],[1,1,3],[6,3],  [7,2]  ],
     [[3,3],[15],     [2,3,1],[7,4],  [4,7],  [1,3,2],[1,3,1]],
     [[3,3],[1,1,1,1],[3,6],  [3,1,1],[3,2,2],[6,3],  [2,7]  ],
     [[3,3],[15],     [2,3,1],[1,7],  [7,1],  [1,3,2],[2,3,2]]]
tw = [[2,1,3,2,2,3,3],[2,4,2,3,3,2,2],[2,1,3,2,2,3,3],[2,4,2,3,3,2,2]] # widths
th = [[2,4,2,3,3,2,2],[2,1,3,2,2,3,3],[2,4,2,3,3,2,2],[2,1,3,2,2,3,3]] # heights
score = 0
for p, rx in zip(bytearray(open('i', 'rb').read()),
                 bytearray(open('o', 'rb').read())):
    p %= 7; r = rx >> 4; x = rx & 15  # p:piece type, r:rotation, x:offset
    b = [u << x for u in t[r][p]]     # as a bit-matrix (list of ints)
    bw = tw[r][p]; bh = th[r][p]      # width and height
    y = 0                             # drop it
    while y <= 23 - bh and all((a[y + i] & b[i]) == 0 for i in range(bh)):
        y += 1
    y -= 1
    if y < 3:                         # no room?
        a = [0] * len(a)              # clear the grid and carry on
    else:
        for i in range(bh):           # add the piece to the grid
            a[y + i] |= b[i]
        n = 0
        for i in reversed(range(bh)): # collapse full lines
            if a[y + i] == (1 << 10) - 1:
                n += 1; del a[y + i]; a = [0] + a
        score += (1 << n) - 1
print(score)

```

So does the following much faster C program but it's guaranteed to work only on Linux:

```
#include<stdio.h>
#include<fcntl.h>
#include<sys/mman.h>
#include<sys/stat.h>
#define F(i,n,b...)for(i=0;i<n;i++){b;}
typedef int I;typedef char C;
I a[23],t[]={
51,4369,99,802,785,54,39,51,15,306,71,116,561,305,
51,4369,99,275,547,54,114,51,15,306,113,23,561,562};
C*th="2423322213223324233222132233";
I main(){
 struct stat h;stat("i",&h);I i,j,k,l=h.st_size,z=0;
 C*mi=mmap(0,l,1,1,open("i",0,0),0),*mo=mmap(0,l,1,1,open("o",0,0),0);
 F(k,l,
  I p=(mi[k]&255)%7,r=3&mo[k]>>4,q=r*7+p,x=mo[k]&15,y=0,h=th[q]-'0',b[4];
  F(i,h,b[i]=(t[q]>>(4*i)&15)<<x)
  while(y<=23-h){I u=0;F(i,h,u|=a[y+i]&b[i])if(u)break;y++;}
  if(--y<3){F(i,23,a[i]=0)continue;}
  F(i,h,a[y+i]|=b[i])
  I n=0;F(i,23,n+=a[i]==1023)
  if(n){j=23;F(i,20,a[j]=a[22-i];j-=a[j]!=1023)F(i,j,a[i]=0);z+=(1<<n)-1;})
 printf("%d\n",z);return 0;}

```

The highest total score wins. Standard loopholes are forbidden.

# Answer
> 7 votes
# C, score: 4136 (4290 - 154 bytes)

```
#include <stdio.h>
main(){int c,p=0,t[]={7,9,21,0,0,51,1,32,16,48,0,33,0,32,16,49};for(;(c=getchar())>=0;putchar(c)){c%=7;c=t[!c||!(10%c)?c:2*c+p++%4];}}

```

The idea is that blocks S,Z,O,I use fixed locations and rotations:

```
                  |
      s     z     |
      s s z z # # |
        s z   # # |
0 1 2 3 4 5 6 7 8 9

```

The rest - J,L,T - are packed into first three columns with some cyclic rotation.

Ungolfed version:

```
#include <stdio.h>
int main() {
    int c,p=0,t[] = {7,9,21,51, 1,32,16,48, 16,48,0,33, 0,32,16,49 };
    while ((c=getchar())!=EOF) {
            switch(c%7) {
            case 0: c = t[0]; break;
            case 1: c = t[1]; break;
            case 2: c = t[2]; break;
            case 3: c = t[4+p++%4]; break;
            case 4: c = t[8+p++%4]; break;
            case 5: c = t[3]; break;
            case 6: c = t[12+p++%4]; break;
            }
            putchar(c);
    }
    return 0;
}

```

---
Tags: code-challenge, ai-player, tetris
---


title: We do tower hopping

text:
# Question
Title: We do tower hopping
# Task

Given an array of non-negative integers `a`, determine the minimum number of rightward jumps required to jump "outside" the array, starting at position 0, or return zero/null if it is not possible to do so.

A *jump* from index `i` is defined to be an increase in array index by at most `a[i]`.

A *jump outside* is a jump where the index resulting from the jump `i` is out-of-bounds for the array, so for 1-based indexing `i>length(a)`, and for 0-based indexing, `i>=length(a)`.

## Example 1

Consider `Array = [4,0,2,0,2,0]`:

```
Array[0] = 4 -> You can jump 4 field
Array[1] = 0 -> You can jump 0 field
Array[2] = 2 -> You can jump 2 field
Array[3] = 0 -> You can jump 0 field
Array[4] = 2 -> You can jump 2 field
Array[5] = 0 -> You can jump 0 field

```

The shortest path by "jumping" to go out-of-bounds has length `2`:

We could jump from `0->2->4->outside` which has length `3` but `0->4->outside` has length `2` so we return `2`.

## Example 2

Suppose `Array=[0,1,2,3,2,1]`:

```
Array[0] = 0 -> You can jump 0 fields
Array[1] = 1 -> You can jump 1 field
Array[2] = 2 -> You can jump 2 field
Array[3] = 3 -> You can jump 3 field
Array[4] = 2 -> You can jump 2 field
Array[5] = 1 -> You can jump 1 field

```

In this case, it is impossible to jump outside the array, so we should return a zero/null or any non deterministic value like .

## Example 3

Suppose `Array=[4]`:

```
Array[0] = 4 -> You can jump 4 field

```

We can directly jump from index 0 outside of the array, with just one jump, so we return `1`.

# Edit:

Due to multiple questions about the return value: Returning  is totally valid, if there is no chance to escape. Because, if there is a chance, we can define that number.

This is , so the shortest code in bytes wins!

# Answer
# Husk, 9 bytes

```
Γö→▼Mo₀↓ŀ

```

Returns `Inf` when no solution exists. Try it online!

## Explanation

Husk's default return values come in handy here.

```
Γö→▼Mo₀↓ŀ  Implicit input: a list, say [2,3,1,1]
Γ          Deconstruct into head H = 2 and tail T = [3,1,1]
 ö         and feed them into this function:
        ŀ   Range from 0 to H-1: [0,1]
    Mo      For each element in range,
       ↓    drop that many element from T: [[3,1,1],[1,1]]
      ₀     and call this function recursively on the result: [1,2]
   ▼        Take minimum of the results: 2
  →         and increment: 3

```

If the input list is empty, then `Γ` cannot deconstruct it, so it returns the default integer value, 0. If the first element is 0, then the result of `Mo₀↓ŀ` is an empty list, on which  returns infinity.
> 5 votes

# Answer
# Haskell, ~~70~~ 58 bytes

```
f[]=0
f(0:_)=1/0
f(x:s)=minimum[1+f(drop k$x:s)|k<-[1..x]]

```

Try it online!

EDIT: -12 bytes thanks to @Esolanging Fruit and the OP for deciding to allow infinity!

Returns `Infinity` when there is no solution which makes the solution a lot simpler. Since we can only move forwards `f` just looks at the head of the list and drops `1<=k<=x` items from the list and recurs. Then we just add 1 to each solution the recursive calls found and take the minimum. If the head is 0 the result will be infinity (since we cannot move there is no solution). Since `1+Infinity==Infinity` this result will be carried back to the callers. If the list is empty that means we have left the array so we return a cost of 0.
> 6 votes

# Answer
# Python 2, 124 bytes

```
def f(a):
 i={0};l=len(a)
 for j in range(l):
	for q in{0}|i:
	 if q<l:i|=set(range(q-a[q],q-~a[q]))
	 if max(i)/l:return-~j

```

Try it online!

-11 bytes thanks to Mr. Xcoder
-12 bytes thanks to Mr. Xcoder and Rod
> 3 votes

# Answer
# ~~APL (Dyalog Classic)~~ ngn/apl, 18 bytes

EDIT: switched to my own implementation of APL because Dyalog doesn't support infinities and the challenge author doesn't allow finite numbers to act as "null"

```
⊃⊃{⍵,⍨1+⌊/⍺↑⍵}/⎕,0

```

~~Try it online!~~ try it at ngn/apl's demo page

returns ~~`⌊/⍬`~~  for no solution
> 3 votes

# Answer
# Haskell, 45 bytes

```
(1%)
0%_=1/0
a%(h:t)=min(1+h%t)$(a-1)%t
_%_=0

```

Try it online!

Outputs `Infinity` when impossible. The auxiliary left argument to `%` tracks how many more spaces we can move in our current hop.
> 3 votes

# Answer
# Perl 5, ~~56~~ 53 bytes

Includes `+1` for `a`

```
perl -aE '1until-@F~~%v?say$n:$n++>map\@v{$_-$F[-$_]..$_},%v,0'  <<< "4 0 2 0 2 0"; echo

```

Just the code:

```
#!/usr/bin/perl -a
1until-@F~~%v?say$n:$n++>map\@v{$_-$F[-$_]..$_},%v,0

```

Try it online!
> 2 votes

# Answer
# Perl 5, 80 bytes

```
sub f{$_[0]>=@_||1+((sort{$a?$b?$a-$b:-1:1}map f(@_[$_..$#_]),1..$_[0])[0]||-1)}

```

Try it online!
> 1 votes

# Answer
# Jelly, 32 bytes

```
ṛ/ṆȧJ’Ṛ
Rḟ"ÇƤZ$$Tị$Œp+\€Ṁ<Li0ȧ@Ḣ

```

Try it online!

This is just too long...
> 1 votes

# Answer
# Jelly, ~~19~~ 18 bytes

```
<LḢ
ḊßÐƤṁḢḟ0‘Ṃµ1Ç?

```

Try it online!

## Explanation

```
<LḢ  Helper link. Input: array
<    Less than
 L   Length
  Ḣ  Head - Returns 0 if its possible to jump out, else 1

ḊßÐƤṁḢḟ0‘Ṃµ1Ç?  Main link. Input: array
            Ç   Call helper link
             ?  If 0
           1      Return 1
                Else
          µ       Monadic chain
Ḋ                   Dequeue
 ßÐƤ                Recurse on each suffix
     Ḣ              Head of input
    ṁ               Mold, take only that many values
      ḟ0            Filter 0
        ‘           Increment
         Ṃ          Minimum

```
> 1 votes

# Answer
# JavaScript ES6, 118 bytes

```
(x,g=[[0,0]])=>{while(g.length){if((s=(t=g.shift())[0])>=x.length)return t[1];for(i=0;i++<x[s];)g.push([s+i,t[1]+1])}}

```

Try it online!

Performs a breadth first search of the array to find the shortest path.
> 1 votes

# Answer
# C (gcc), 80 bytes

```
f(A,l,M,j,r)int*A;{M=~0;for(j=0;l>0&&j++<*A;)if(M<1|M>(r=f(A+j,l-j)))M=r;A=-~M;}

```

Try it online!
> 0 votes

# Answer
# Julia 0.6, 79 bytes

Returns the number of jumps or `Inf` if you can't escape. Recursively look at the first element and either return `Inf` or `1` depending on if you can escape, otherwise add `1` to the shortest solution for truncated arrays representing each valid jump. The control flow is done with two ternary statements like `test1 ? ontrue1 : test2 ? ontrue2 : onfalse2`.

```
f(a,n=endof(a))=a[1]<1?Inf:a[1]>=n?1:1+minimum(f(a[z:min(z+a[1],n)]) for z=2:n)

```

Try it online!
> 0 votes

# Answer
# Python 2, ~~83~~ ~~73~~ 72 bytes

<sup> -10 thanks to @user202729
-1 thanks to @JonathanFrech</sup>

```
lambda a:a and(a[0]and-~min(f(a[k+1:])for k in range(a[0]))or 1e999)or 0

```

Try it online! Returns infinity for a null value.
> 0 votes

# Answer
# C# (.NET Core), 97 bytes

```
f=l=>{for(int c=l.Count,s=0,j=l[0];j>0;s=f(l.GetRange(j,c-j--)))if(s>0|j>=c)return s+1;return 0;}

```

Try it online!

Returns 0 if no path was found.

**Explanation**

```
f =
    l =>                                      //The list of integers
    {
        for (
            int c = l.Count,                  //The length of the list
                s = 0,                        //Helper to keep track of the steps of the recursion
                j = l[0];                     //The length of the jump, initialize with the first element of the list
                j > 0;                        //Loop while the jump length is not 0
                s = f(l.GetRange(j, c - j--)) //Recursive call of the function with a sub-list stating at the current jump length.
                                              //Then decrement the jumplength.
                                              //Returns the number of steps needed to jump out of the sup-list or 0 if no path was found.
                                              //This is only executed after the first run of the loop body.
            )
        {
            if (j >= c |                      //Check if the current jump lengt gets you out of the list.
                                              //If true return 1 (s is currently 0). OR
                s > 0 )                       //If the recursive call found a solution (s not 0)
                                              //return the number of steps from the recursive call + 1
                return s + 1;
        }
        return 0;                             //If the jump length was 0 return 0
                                              //to indicate that no path was found from the current sub-list.
    }

```
> 0 votes

---
Tags: code-golf, array, decision-problem, optimization
---


title: Find the dot product of Rationals

text:
# Question
Title: Find the dot product of Rationals
I was at a friend's house for dinner and they suggested the idea of a "Prime-factor vector space". In this space the positive integers are expressed as a vector such that the **n**th element in the vector is the number of times the **n**th prime divides the number. (Note that this means that our vectors have an infinite number of terms.) For example **20** is

```
2 0 1 0 0 0 ...

```

Because its prime factorization is **2 * 2 * 5**.

Since prime factorization is unique each number corresponds to one vector.

We can add vectors by pairwise adding their entries. This is the same as multiplying the numbers they are associated with. We can also do scalar multiplication, which is akin to raising the associated number to a power.

The problem is that this space is not in fact a vector space because there are no inverses. If we go ahead and add the inverses and close the vector space we now have a way of expressing every positive rational number as a vector. If we keep the fact that vector addition represents multiplication. Then the inverse of a natural number is its reciprocal.

For example the number **20** had the vector

```
2 0 1 0 0 0 ...

```

So the fraction **1/20** is its inverse

```
-2 0 -1 0 0 0 ...

```

If we wanted to find the vector associated with a fraction like **14/15** we would find **14**

```
1 0 0 1 0 0 ...

```

and **1/15**

```
0 -1 -1 0 0 0 ...

```

and multiply them by performing vector addition

```
1 -1 -1 1 0 0 ...

```

Now that we have a vector space we can modify it to form an inner product space by giving it an inner product. To do this we steal the inner product that vector spaces are given classically. The inner product of two vectors is defined as the sum of the pairwise multiplication of their terms. For example **20 · 14/15** would be calculated as follows

```
20    =  2  0  1  0  0  0 ...
14/15 =  1 -1 -1  1  0  0 ...
         2  0 -1  0  0  0 ...  -> 1

```

As another example the product **2/19 · 4/19**

```
2/19 = 1 0 0 0 0 0 0 -1 0 0 0 ...
4/19 = 2 0 0 0 0 0 0 -1 0 0 0 ...
       2 0 0 0 0 0 0  1 0 0 0 ... -> 3

```

Your task is to implement a program that performs this dot product. It should take two positive rational numbers via either a pair of positive integers (numerator and denominator) or a rational type (floats are not allowed, because they cause problems with precision and divisibility) and should output a integer representing the dot product of the two inputs.

This is so answers will be scored in bytes with fewer bytes being better.

## Test Cases

```
4 · 4 = 4
8 · 8 = 9
10 · 10 = 2
12 · 12 = 5
4 · 1/4 = -4
20 · 14/15 = 1
2/19 · 4/19 = 3

```

# Answer
> 4 votes
# MATL, 12 bytes

```
YF2:&Y)dwd*s

```

Input is an array `[num1 den1 num2 den2]`.

Try it online! Or verify all test cases.

### Explanation

Consider example input `[20 1 14 15]`.

```
YF      % Implicit input: array of 4 numbers. Exponents of prime factorization.
        % Gives a matrix, where each row corresponds to one of the numbers in
        % the input array. Each row may contain zeros for non-present factors
        % STACK: [2 0 1 0
                  0 0 0 0
                  1 0 0 1
                  0 1 1 0]
2:&Y)   % Push a submatrix with the first two rows, then a submatrix with the
        % other two rows
        % STACK: [2 0 1 0
                  0 0 0 0],
                 [1 0 0 1
                  0 1 1 0]
d       % Consecutive difference(s) along each column
        % STACK: [2 0 1 0
                  0 0 0 0],
                 [-1 1 -1 1]
wd      % Swap, and do the same for the other submatrix
        % STACK: [-1 1 -1 1]
                 [-2 0 -1 0]
*       % Element-wise product
        % STACK: [2 0 -1 0]
s       % Sum. Implicit display
        % STACK: 1

```

# Answer
> 4 votes
# C (gcc), 99+32 = 131 bytes

* Using a compiler flag requiring 32 bytes, `-D=F(v,V,e)for(;v%p<1;V+=e)v/=p;`.

```
T,p,A,C;f(a,b,c,d){T=0;for(p=2;a+b+c+d>4;p++){A=C=0;F(a,A,1)F(b,A,~0)F(c,C,1)F(d,C,~0)T+=A*C;}a=T;}

```

Try it online!

# Answer
> 3 votes
# Jelly, ~~12~~ 11 bytes

```
ÆEz0_2/€P€S

```

Try it online!

# Answer
> 3 votes
# Python 2, 110 bytes

```
l=input()
p=t=2
while~-max(l):r=i=0;exec"while l[i]%p<1:l[i]/=p;r+=1j**i\ni+=1\n"*4;t+=r*r;p+=1
print t.imag/2

```

Try it online!

Takes input like `[num1, num2, den1, den2]`. Uses a complex number `r` to store the entries for prime `p` for the two rationals, and `(r*r).imag/2` to extract their product `r.real*r.imag` within overall the sum `t`. Adding `1j**i` for `i=0,1,2,3` does each combination of incrementing or decrementing the real or imaginary part for the four input numbers.

*Bubbler saved 2 bytes combining the initial values `p=t=2`.*

# Answer
> 2 votes
# Wolfram Language (Mathematica), 55 bytes

```
Dot@@PadRight[SparseArray[Rule@@@FactorInteger@#]&/@#]&

```

Try it online!

# Answer
> 1 votes
# Python 2, 133 127 bytes

```
a=input();s=0;p=2;P=lambda n,i=0:n%p and(n,i)or P(n/p,i+1)
while~-max(a):a,(w,x,y,z)=zip(*map(P,a));s+=(w-x)*(y-z);p+=1
print s

```

Try it online!

Stole the loop condition from xnor's submission.

Thanks for the advice by @mathmandan to change the function into a program (Yes, it indeed saved some bytes).

Obsolete, incorrect solution (124 bytes):

```
lambda w,x,y,z:sum((P(w,p)-P(x,p))*(P(y,p)-P(z,p))for p in[2]+range(3,w+x+y+z,2))
P=lambda n,p,i=1:n%p and i or P(n/p,p,i+1)

```

# Answer
> 1 votes
# JavaScript (Node.js), ~~104~~ ... ~~100~~ 94 bytes

```
F=(A,i=2)=>A.some(x=>x>1)&&([a,b,c,d]=A.map(G=(x,j)=>x%i?0:1+G(A[j]/=i,j)),a-b)*(c-d)+F(A,i+1)

```

Try it online!

Pass the numbers as an array of \[Num1, Den1, Num2, Den2\].

Thanks for Arnauld for fixing the missing `F=` with no extra bytes, and 2 more bytes less.

## Explanation & ungolfed

```
function F(A, i = 2) {                 // Main function, recursing from i = 2
 if (A.some(function(x) {              // If not all numbers became 1:
  return x > 1;
 })) {
  var B = A.map(G = function(x, j) {   // A recursion to calculate the multiplicity
   if (x % i)
    return 0;
   else
    return 1 + G(A[j] /= i, j);        // ...and strip off all powers of i
  });
  return (B[0] - B[1]) * (B[2] - B[3]) // Product at i
   + F(A, i + 1);                      // Proceed to next factor. All composite factors
 }                                     // will be skipped effectively
 else
  return 0;                            // Implied in the short-circuit &&
}

```

# Answer
> 1 votes
# , 19 bytes

```
1#.*/@,:&([:-/_&q:)

```

Try it online!

## Explanation:

A dyadic verb, arguments are on both left hand and right hand side

```
         &(        ) - for both arguments (which are lists of 2 integers)
               _&q:  - decompose each number to a list of prime exponents
           [:-/      - and find the difference of these lists
       ,:            - laminate the resulting lists for both args (to have the same length)
   */@               - multiply them
1#.                  - add up

```

# Answer
> 1 votes
# Stax, 11 bytes

```
ä÷ß½♂←√:=Ü]

```

Run and debug it

The corresponding ascii representation of the same program is this.

```
{|nmMFE-~-,*+

```

Basically, it gets the prime factorization's exponents for each part. It takes the difference of each pair, then the product, and finally sums all the results.

# Answer
> 1 votes
# Haskell, 153 bytes

```
(2%)
n%m|all(<2)m=0|(k,[a,b,c,d])<-unzip[(,)=<<div x.max 1.(n*)$until((>0).mod x.(n^))(+1)1-1|x<-m]=(a-b)*(c-d)+[i|i<-[n..],all((>0).rem i)[2..i-1]]!!1%k

```

Try it online! Example usage for `20 · 14/15`: `(2%) [20,1,14,15]`.

---
Tags: code-golf, math, number-theory, linear-algebra, factoring
---


title: How many Magic Cubes?

text:
# Question
Title: How many Magic Cubes?
## Your Task:

You all know what a magic square is! But what about a magic cube? A magic cube is the 3D version of a magic square, and is a set of numbers in a cube, where the sums of every straight (not diagonal) line are equal. You must write a program or function that receives an integer, and returns the number of valid magic cubes made up of up to one of each integer between 1 and that integer (inclusive).

## Input:

An integer.

## Output:

The number of magic cubes you can make by using up to one of of each integer between 1 and the input. A cube with various rotations should only be counted once.

## Scoring:

This is , lowest byte count wins.

## BOUNTY:

I will award a 100 rep bounty to the first user that manages to do this in \< 100 bytes without using built-ins designed specifically towards magic cubes or squares (looking at you Mathematica).

# Answer
> 3 votes
# Clingo, 220 + 2 = 222 bytes

```
1{s(S):S=0..n,S**3==n}.
A{a(0..n-1,A)}:-A=1..n.
:-a(P,A-1),{a(P,A)}0,A<n.
:-s(S),{a(P,A):P-P/K\S*K=Q-Q/K\S*K}>(S*n+S)/2,Q=0..n,K=(1;S;S*S).
:-s(S),a(((0;1)+(0;S)+(0;S*S))*~-S,A),{a(0,A)}0.
:-s(S),a((S;S*S)*~-S,A),{a(S-1,A)}0.

```

Run with `clingo magic-cubes.lp -n0 -cn=INPUT`. The answer will be printed next to `Models`.

All newlines are optional and shown here for clarity but excluded from the byte count. I’m scoring +2 bytes for `-n0` (“count all models”).

The last two lines ensure that only one rotated version of each cube is counted.

The answers for 1, 8, 27 are quickly found to be 1, 0, 216; the rest are probably too hard.

If you want to see the cubes in a more readable format, add `b((P\S,P/S\S,P/S/S),A):s(S),-a(P,A),not a(P,A-1). #show b/2.`

```
$ clingo magic-cubes.lp -n0 -cn=1
clingo version 5.1.0
Reading from magic-cubes.lp
Solving...
Answer: 1
a(0,1) s(1)
SATISFIABLE

Models       : 1
Calls        : 1
Time         : 0.009s (Solving: 0.00s 1st Model: 0.00s Unsat: 0.00s)
CPU Time     : 0.010s
$ clingo magic-cubes.lp -n0 -cn=8
clingo version 5.1.0
Reading from magic-cubes.lp
Solving...
UNSATISFIABLE

Models       : 0
Calls        : 1
Time         : 0.010s (Solving: 0.00s 1st Model: 0.00s Unsat: 0.00s)
CPU Time     : 0.000s
$ clingo magic-cubes.lp -n0 -cn=27
clingo version 5.1.0
Reading from magic-cubes.lp
Solving...
Answer: 1
a(7,1) a(7,2) a(13,2) a(7,3) a(13,3) a(19,3) a(7,4) a(13,4) a(15,4) a(19,4) a(7,5) a(13,5) a(15,5) a(19,5) a(21,5) a(0,6) a(7,6) a(13,6) a(15,6) a(19,6) a(21,6) a(0,7) a(7,7) a(13,7) a(15,7) a(19,7) a(21,7) a(26,7) a(0,8) a(5,8) a(7,8) a(13,8) a(15,8) a(19,8) a(21,8) a(26,8) a(0,9) a(5,9) a(7,9) a(11,9) a(13,9) a(15,9) a(19,9) a(21,9) a(26,9) a(0,10) a(2,10) a(5,10) a(7,10) a(11,10) a(13,10) a(15,10) a(19,10) a(21,10) a(26,10) a(0,11) a(2,11) a(5,11) a(7,11) a(11,11) a(13,11) a(15,11) a(17,11) a(19,11) a(21,11) a(26,11) a(0,12) a(2,12) a(5,12) a(7,12) a(11,12) a(13,12) a(15,12) a(17,12) a(19,12) a(21,12) a(23,12) a(26,12) a(0,13) a(2,13) a(5,13) a(7,13) a(10,13) a(11,13) a(13,13) a(15,13) a(17,13) a(19,13) a(21,13) a(23,13) a(26,13) a(0,14) a(2,14) a(5,14) a(7,14) a(10,14) a(11,14) a(13,14) a(15,14) a(17,14) a(19,14) a(21,14) a(23,14) a(25,14) a(26,14) a(0,15) a(2,15) a(4,15) a(5,15) a(7,15) a(10,15) a(11,15) a(13,15) a(15,15) a(17,15) a(19,15) a(21,15) a(23,15) a(25,15) a(26,15) a(0,16) a(2,16) a(4,16) a(5,16) a(7,16) a(10,16) a(11,16) a(13,16) a(15,16) a(17,16) a(18,16) a(19,16) a(21,16) a(23,16) a(25,16) a(26,16) a(0,17) a(2,17) a(4,17) a(5,17) a(6,17) a(7,17) a(10,17) a(11,17) a(13,17) a(15,17) a(17,17) a(18,17) a(19,17) a(21,17) a(23,17) a(25,17) a(26,17) a(0,18) a(2,18) a(4,18) a(5,18) a(6,18) a(7,18) a(10,18) a(11,18) a(12,18) a(13,18) a(15,18) a(17,18) a(18,18) a(19,18) a(21,18) a(23,18) a(25,18) a(26,18) a(0,19) a(2,19) a(3,19) a(4,19) a(5,19) a(6,19) a(7,19) a(10,19) a(11,19) a(12,19) a(13,19) a(15,19) a(17,19) a(18,19) a(19,19) a(21,19) a(23,19) a(25,19) a(26,19) a(0,20) a(2,20) a(3,20) a(4,20) a(5,20) a(6,20) a(7,20) a(9,20) a(10,20) a(11,20) a(12,20) a(13,20) a(15,20) a(17,20) a(18,20) a(19,20) a(21,20) a(23,20) a(25,20) a(26,20) a(0,21) a(2,21) a(3,21) a(4,21) a(5,21) a(6,21) a(7,21) a(9,21) a(10,21) a(11,21) a(12,21) a(13,21) a(15,21) a(17,21) a(18,21) a(19,21) a(21,21) a(23,21) a(24,21) a(25,21) a(26,21) a(0,22) a(2,22) a(3,22) a(4,22) a(5,22) a(6,22) a(7,22) a(9,22) a(10,22) a(11,22) a(12,22) a(13,22) a(14,22) a(15,22) a(17,22) a(18,22) a(19,22) a(21,22) a(23,22) a(24,22) a(25,22) a(26,22) a(0,23) a(2,23) a(3,23) a(4,23) a(5,23) a(6,23) a(7,23) a(9,23) a(10,23) a(11,23) a(12,23) a(13,23) a(14,23) a(15,23) a(17,23) a(18,23) a(19,23) a(20,23) a(21,23) a(23,23) a(24,23) a(25,23) a(26,23) a(0,24) a(2,24) a(3,24) a(4,24) a(5,24) a(6,24) a(7,24) a(8,24) a(9,24) a(10,24) a(11,24) a(12,24) a(13,24) a(14,24) a(15,24) a(17,24) a(18,24) a(19,24) a(20,24) a(21,24) a(23,24) a(24,24) a(25,24) a(26,24) a(0,25) a(2,25) a(3,25) a(4,25) a(5,25) a(6,25) a(7,25) a(8,25) a(9,25) a(10,25) a(11,25) a(12,25) a(13,25) a(14,25) a(15,25) a(17,25) a(18,25) a(19,25) a(20,25) a(21,25) a(22,25) a(23,25) a(24,25) a(25,25) a(26,25) a(0,26) a(1,26) a(2,26) a(3,26) a(4,26) a(5,26) a(6,26) a(7,26) a(8,26) a(9,26) a(10,26) a(11,26) a(12,26) a(13,26) a(14,26) a(15,26) a(17,26) a(18,26) a(19,26) a(20,26) a(21,26) a(22,26) a(23,26) a(24,26) a(25,26) a(26,26) a(0,27) a(1,27) a(2,27) s(3) a(3,27) a(4,27) a(5,27) a(6,27) a(7,27) a(8,27) a(9,27) a(10,27) a(11,27) a(12,27) a(13,27) a(14,27) a(15,27) a(16,27) a(17,27) a(18,27) a(19,27) a(20,27) a(21,27) a(22,27) a(23,27) a(24,27) a(25,27) a(26,27)
Answer: 2
[…]
Answer: 216
a(0,2) a(12,1) a(12,2) a(0,3) a(12,3) a(24,3) a(0,4) a(12,4) a(22,4) a(24,4) a(0,5) a(10,5) a(12,5) a(22,5) a(24,5) a(0,6) a(7,6) a(10,6) a(12,6) a(22,6) a(24,6) a(0,7) a(5,7) a(7,7) a(10,7) a(12,7) a(22,7) a(24,7) a(0,8) a(5,8) a(7,8) a(10,8) a(12,8) a(20,8) a(22,8) a(24,8) a(0,9) a(5,9) a(7,9) a(10,9) a(12,9) a(17,9) a(20,9) a(22,9) a(24,9) a(0,10) a(5,10) a(7,10) a(10,10) a(12,10) a(16,10) a(17,10) a(20,10) a(22,10) a(24,10) a(0,11) a(4,11) a(5,11) a(7,11) a(10,11) a(12,11) a(16,11) a(17,11) a(20,11) a(22,11) a(24,11) a(0,12) a(4,12) a(5,12) a(7,12) a(10,12) a(12,12) a(16,12) a(17,12) a(19,12) a(20,12) a(22,12) a(24,12) a(0,13) a(4,13) a(5,13) a(7,13) a(10,13) a(12,13) a(16,13) a(17,13) a(19,13) a(20,13) a(22,13) a(24,13) a(26,13) a(0,14) a(4,14) a(5,14) a(7,14) a(10,14) a(12,14) a(14,14) a(16,14) a(17,14) a(19,14) a(20,14) a(22,14) a(24,14) a(26,14) a(0,15) a(2,15) a(4,15) a(5,15) a(7,15) a(10,15) a(12,15) a(14,15) a(16,15) a(17,15) a(19,15) a(20,15) a(22,15) a(24,15) a(26,15) a(0,16) a(2,16) a(4,16) a(5,16) a(6,16) a(7,16) a(10,16) a(12,16) a(14,16) a(16,16) a(17,16) a(19,16) a(20,16) a(22,16) a(24,16) a(26,16) a(0,17) a(2,17) a(4,17) a(5,17) a(6,17) a(7,17) a(10,17) a(12,17) a(14,17) a(16,17) a(17,17) a(19,17) a(20,17) a(21,17) a(22,17) a(24,17) a(26,17) a(0,18) a(2,18) a(4,18) a(5,18) a(6,18) a(7,18) a(9,18) a(10,18) a(12,18) a(14,18) a(16,18) a(17,18) a(19,18) a(20,18) a(21,18) a(22,18) a(24,18) a(26,18) a(0,19) a(2,19) a(4,19) a(5,19) a(6,19) a(7,19) a(9,19) a(10,19) a(11,19) a(12,19) a(14,19) a(16,19) a(17,19) a(19,19) a(20,19) a(21,19) a(22,19) a(24,19) a(26,19) a(0,20) a(2,20) a(4,20) a(5,20) a(6,20) a(7,20) a(8,20) a(9,20) a(10,20) a(11,20) a(12,20) a(14,20) a(16,20) a(17,20) a(19,20) a(20,20) a(21,20) a(22,20) a(24,20) a(26,20) a(0,21) a(2,21) a(4,21) a(5,21) a(6,21) a(7,21) a(8,21) a(9,21) a(10,21) a(11,21) a(12,21) a(14,21) a(16,21) a(17,21) a(19,21) a(20,21) a(21,21) a(22,21) a(23,21) a(24,21) a(26,21) a(0,22) a(2,22) a(4,22) a(5,22) a(6,22) a(7,22) a(8,22) a(9,22) a(10,22) a(11,22) a(12,22) a(14,22) a(16,22) a(17,22) a(18,22) a(19,22) a(20,22) a(21,22) a(22,22) a(23,22) a(24,22) a(26,22) a(0,23) a(2,23) a(4,23) a(5,23) a(6,23) a(7,23) a(8,23) a(9,23) a(10,23) a(11,23) a(12,23) a(14,23) a(15,23) a(16,23) a(17,23) a(18,23) a(19,23) a(20,23) a(21,23) a(22,23) a(23,23) a(24,23) a(26,23) a(0,24) a(2,24) a(3,24) a(4,24) a(5,24) a(6,24) a(7,24) a(8,24) a(9,24) a(10,24) a(11,24) a(12,24) a(14,24) a(15,24) a(16,24) a(17,24) a(18,24) a(19,24) a(20,24) a(21,24) a(22,24) a(23,24) a(24,24) a(26,24) a(0,25) a(1,25) a(2,25) a(3,25) a(4,25) a(5,25) a(6,25) a(7,25) a(8,25) a(9,25) a(10,25) a(11,25) a(12,25) a(14,25) a(15,25) a(16,25) a(17,25) a(18,25) a(19,25) a(20,25) a(21,25) a(22,25) a(23,25) a(24,25) a(26,25) a(0,26) a(1,26) a(2,26) a(3,26) a(4,26) a(5,26) a(6,26) a(7,26) a(8,26) a(9,26) a(10,26) a(11,26) a(12,26) a(14,26) a(15,26) a(16,26) a(17,26) a(18,26) a(19,26) a(20,26) a(21,26) a(22,26) a(23,26) a(24,26) a(25,26) a(26,26) a(0,27) a(1,27) a(2,27) s(3) a(3,27) a(4,27) a(5,27) a(6,27) a(7,27) a(8,27) a(9,27) a(10,27) a(11,27) a(12,27) a(13,27) a(14,27) a(15,27) a(16,27) a(17,27) a(18,27) a(19,27) a(20,27) a(21,27) a(22,27) a(23,27) a(24,27) a(25,27) a(26,27)
SATISFIABLE

Models       : 216
Calls        : 1
Time         : 6.101s (Solving: 6.07s 1st Model: 1.03s Unsat: 0.37s)
CPU Time     : 6.090s

```

# Answer
> 3 votes
# Ruby, 275 bytes

```
n=gets.to_i;p (2.upto(n**(1/3r)).map{|i|(1..n).to_a.permutation(i**3).map{|x|c=eval'x'+".each_slice(#{i}).to_a"*2;[c,c.map(&:transpose),c.transpose.map(&:transpose)].map{|q|q.map{|a|a.map{|b|b.inject(:+)}}.flatten.uniq.length}.inject(:+)==3?1:0}}+[0]).flatten.inject(:+)/48+n

```

Try it online!

In theory, this works. In practice, since it creates every permutation of the list of possible numbers, it'll take hopelessly large amounts of time and memory for any input more than 13 or so. I haven't taken the time to test it past 12, but it seems no 2×2×2 magic cubes exist for that range, so all it really does is tell you how many 1×1×1 cubes you can make.

I "golfed" it a bit (really just made it hard to read for minimal size reduction returns). I'm sure the size can be reduced quite a bit, though getting it under 100 characters is a pretty tall order.

Ruby 2.4 added `.sum`, but TIO doesn't support it yet, so this has a few `.inject(:+)`s.

I'll add a non-golfed version + explanation if requested.

# Answer
> 2 votes
# Jelly, 36 bytes

```
;Z;Z€ẎS€E
*3³œcŒ!€Ẏs€s€¹Ç€S
Ç€ḊS÷24+

```

Try it online!

As you expect, it's terribly slow.

## Explanation

* Link 1: Given a cube, check if it's valid.

```
;Z;Z€ẎS€E   Input: N =
            [  [ [a,b],    [ [e,f],
                 [c,d] ],    [g,h] ]   ]

;Z          Concatenate with zip of N. The zip (transpose) of N is
            [   [ [a,b],    [ [c,d],
                  [e,f] ],    [g,h] ]   ]
            (by treating each 2-element block as an unit
            and transpose the large table)

;Z€         Concatenate with plane-wise zip of N, that is
            [  [ [a,c],    [ [e,g],
                 [b,d] ],    [f,h] ]   ]
            (transpose each 2x2 block)

            The current value is:
            [ [ [a,b],   [ [e,f],   [ [a,b],   [ [c,d],   [ [a,c],   [ [e,g],
                 [c,d] ],   [g,h] ],   [e,f] ],   [g,h] ],   [b,d] ],   [f,h] ] ]

Ẏ           Tighten, concatenate all elements inside, similar to `;/`.
            Get [ [a,b], [c,d], [e,f], [g,h],
                  [a,b], [e,f], [c,d], [g,h],
                  [a,c], [b,d], [e,g], [f,h] ]
S€          Sum each sublist. `ZS` also works.
E           All **E**qual? `1` if all elements are equal, `0` otherwise.

```
* Link 2: Given a side length `x`, generate all cubes with that side length and calculate number of valid cubes.

```
*3³œcŒ!€Ẏs€s€¹Ç€S   Given: `x` (side length).
*3                  Calculate .
  ³                 First commandline argument. (**n**)
   œc               Generate all subsets of the range `[1..n]` having length .
     Œ!€Ẏ           All permutation of each and tighten.
                      (the current value is a list of all ways to choose
                      an ordered tuple of  elements from `[1..n]`)
         s€s€       Split each twice into slices of length `x`.
                      On a list of (list of  integers), this format
                      each sublist into a cube.
             ¹      Do nothing. Because Jelly is a tacit programming language
                      without this the program will behave differently.
              Ç€    Apply last link for ach.
                S   **S**um.

```
* Link 3 (main link): For all side lengths from `1` to `n`, calculate number of cubes (rotations are counted multiple times) for each side length, dequeue and sum it (so we get the sum of number of cubes with side length `>= 2`), divide by `24` (to avoid duplication of cubes) and add the number of side length 1 cube (input).

```

Ç          Apply last link...
 €           for ach element from `1` to `n`.
  Ḋ        equeue, dispose the result for value 1.
   S÷24    **S**um and divide by 24.
       +   Add the input (number of cubes with side length 1)

```

---
Tags: code-golf
---


title: Code-Challenge: Farey sequence (II)

text:
# Question
Title: Code-Challenge: Farey sequence (II)
## Challenge

> In this task you would be given an integer N (less than 10^6), output the number of terms in the Farey sequence of order N.

The input N \< 106 is given in a single line, the inputs are terminated by EOF.

The challenge is to implement the fastest solution so that it can process a maximum of 106-1 values as fast as possible.

**Input**

```
7
10
999
9999
79000
123000

```

**Output**

```
19
33
303793
30393487
1897046599
4598679951

```

**Constraints**

* You can use any language of your choice
* Take care about your fingers, do not use more than **4096** bytes of code.
* Fastest solution, based on the running time measured for N = 106-1.

# Answer
> 3 votes
**C - 0.1 Secs on Ideone**

http://www.ideone.com/E3S2t

Explanation included in code.

```
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

long long A[1000001]={0};
int main()
{
    int isprime[1001],d,n,k,i,e,p;

    for (n=2;n<1001;n++)
        isprime[n]=1;

    //Sieve of Eratosthenes for Prime
    //Storing the smallest prime which divides n.
    //If A[n]=0 it means it is prime number.
    for(d=2;d<1001;d++)
    {
        if(isprime[d])
        {
            for (n=d*d;n<1001;n+=d)
            {
                isprime[n]=0;
                A[n]=d;
            }
            for (;n<=1000000;n+=d)
                A[n]=d;
        }
    }

    //Uses multiplicative property of
    //Euler Totient Function
    //Phi(n)=Phi(p1^k1)*Phi(p2^k2)...*Phi(pr^kr)
    //and Phi(pi^ki)=(pi-1)*(pi^(ki-1))
    A[1]=1;
    for(n=2;n<=1000000;n++)
    {
        if (A[n]==0)
           A[n]=n-1;
        else
        {
           p=A[n],k=n/p,e=1;
           while (k%p==0)
                 k/=p,e*=p;
           A[n]=A[k]*e*(p-1);
        }
    }
    //Number of terms in Farey Series
    //|F(n)| = 1 + Sigma(i,1,n,phi(i))
    A[1]=2;
    for(n=2;n<=1000000;n++)
        A[n]+=A[n-1];

    while (~scanf("%d",&i))
        printf("%lld\n",A[i]);
    return 0;
}

```

A little more explanation:

> For all numbers we get a prime factor of it from the sieve(or 0 if it is a prime). Next we use the fact that ETF is multiplicative. That is if m and n are coprime then `phi(m*n)=phi(m)*phi(n)`. Here we take out the multiple of prime factor out and hence the left part and the multiple part are co-prime. We already have the ETF for the left part since it is either smaller then current value or equal to 1. We only need to calculate the ETF for the multiple which we calculate using the formula `phi(pi^ki)=(pi-1)*(pi^(ki-1))`.

# Answer
> 2 votes
# C - Less than a second for 999999

```
#include "stdio.h"
#include "time.h"
#define i64 unsigned long long
#define i32 unsigned int
#define PLIM 1100
#define FLIM 1000000

i32 primes[PLIM];
i64 f[FLIM];

int main(int argc, char *argv[]){
    i64 start=clock();
    i32 primesindex=0;
    f[0]=1;
    f[1]=2;
    i32 a,b,c;
    i32 notprime;
    //Make a list of primes
    for(a=2;a<PLIM;a++){
        notprime=0;
        for(b=0;b<primesindex;b++){
            if(!(a%primes[b])){
                notprime=1;
            }
        }
        if(!notprime){
            primes[primesindex]=a;
            primesindex++;
        }
    }
    i32 count,divided;
    i32 nextjump=4;
    i32 modlimit=2;
    i32 invalue;
    a=2;
    for(c=1;c<argc;c++){
        invalue=atoi(argv[c]);
        if(invalue<FLIM && invalue){
            //For each number from a to invalue find the totient by prime factorization
            for(;a<=invalue;a++){
                count=a;
                divided=a;
                b=0;
                while(primes[b]<=modlimit){
                    if(!(divided%primes[b])){
                        divided/=primes[b];
                        //Adjust the count when a prime factor is found
                        count=(count/primes[b])*(primes[b]-1);
                        //Discard duplicate prime factors
                        while(!(divided%primes[b])){
                            divided/=primes[b];
                        }
                    }
                    b++;
                }
                //Adjust for the remaining prime, if one is there
                if(divided>1){
                    count=(count/divided)*(divided-1);
                }
                //Summarize with the previous totients
                f[a]=f[a-1]+(i64)count;
                //Adjust the limit for prime search if needed
                if(a==nextjump){
                    modlimit++;
                    nextjump=modlimit*modlimit;
                }
            }
            //Output result
            printf("%I64u\n",f[invalue]);
        }
    }
    i64 end=clock();
    //printf("Runtime: %I64u",end-start);
    return 0;
}

```

This takes input from command line.

The computation is a simple sum of totients, it's only done once and only up to the biggest input.

Here is an Ideone version: http://www.ideone.com/jVbc0

# Answer
> 2 votes
## C (0.2 sec in Ideone)

I thought of adding my approach too: (this is not as fast as Gaurav's)

```
 #include <stdio.h>
 #define N 1000000
 long long Phi[N+1];

 //Sieve ETF

int main(){
   int i,j;

 for(i=1;i<=N;i++)
    Phi[i]=i;

 for(i=2;i<=N;i++){
    if(Phi[i] == i)
       for(j=i;j<=N;j+=i)
           Phi[j] = (Phi[j]/i)*(i-1);
  }

int t,n;

 Phi[1]=2;
 for(i = 2; i < N; i++)
     Phi[i] += Phi[i-1];

for(;~scanf("%d",&n);)
    printf("%lld\n",Phi[n]);

return 0;
}

```

TESTING ...

# Answer
> 2 votes
## J, 0.2s, short code

It feels weird to write ungolfed J, but it actually *is* the language for the task, for once.

```
input =: ". ;. _2 stdin ''
phi =: 5 & p:
max =: >. / input
acc_totient =: +/ \ phi >: i. max
output =: >: (<: input) { acc_totient
echo output

```

Reads input, constructs accumulated sum of totients up to the max, and reads output from there.

# Answer
> 2 votes
# VB.NET, 0.11 s for 10^6

This is basically a totient computation using prime sieve. The time is measured 10 times and the average is computed.

```
Module Module1

Sub Main()
    Dim sw As New Stopwatch
    Dim M As Integer = Console.ReadLine()
    sw.Start()

    Dim is_prime(M) As Integer
    Dim phi(M) As Integer

    For i = 0 To M
        phi(i) = i
        is_prime(i) = True
    Next

    For i = 2 To M
        If is_prime(i) = True Then
            phi(i) = i - 1
            Dim j As Integer = 2 * i
            Do Until j > M
                is_prime(j) = False
                phi(j) = phi(j) - (phi(j) / i)
                j += i
            Loop
        End If
    Next

    Dim result As Long = 1
    For i = 1 To M
        result += phi(i)
    Next

    Console.WriteLine(result)
    sw.Stop()
    Console.WriteLine("Time Elasped : " & sw.ElapsedMilliseconds)
    Dim a = Console.ReadLine()
End Sub

End Module

```

---
Tags: math, fastest-code
---


title: Visualize Merge Sort

text:
# Question
Title: Visualize Merge Sort
Merge sort is a sorting algorithm which works by splitting a given list in half, recursively sorting both smaller lists, and merging them back together to one sorted list. The base case of the recursion is arriving at a singleton list, which cannot be split further but is per definition already sorted.

The execution of the algorithm on the list `[1,7,6,3,3,2,5]` can be visualized in the following way:

```
       [1,7,6,3,3,2,5]
       /             \      split
   [1,7,6,3]       [3,2,5]
    /     \        /    \   split
 [1,7]   [6,3]   [3,2]  [5]
 /   \   /   \   /   \   |  split
[1] [7] [6] [3] [3] [2] [5]
 \   /   \   /   \   /   |  merge
 [1,7]   [3,6]   [2,3]  [5]
    \     /         \   /   merge
   [1,3,6,7]       [2,3,5]
       \             /      merge
       [1,2,3,3,5,6,7]

```

# The Task

Write a program or function which takes a list of integers in any reasonable way as input and visualizes the different partitions of this list while being sorted by a merge sort algorithm. This means you **don't** have to output a graph like above, but just the lists are fine:

```
[1,7,6,3,3,2,5]
[1,7,6,3][3,2,5]
[1,7][6,3][3,2][5]
[1][7][6][3][3][2][5]
[1,7][3,6][2,3][5]
[1,3,6,7][2,3,5]
[1,2,3,3,5,6,7]

```

Furthermore, any reasonable list notation is fine, therefore the following would also be a valid output:

```
1 7 6 3 3 2 5
1 7 6 3|3 2 5
1 7|6 3|3 2|5
1|7|6|3|3|2|5
1 7|3 6|2 3|5
1 3 6 7|2 3 5
1 2 3 3 5 6 7

```

Finally, the way to split a list in two smaller lists is up to you as long as the length of both resulting lists differs at most by one. That means instead of splitting `[3,2,4,3,7]` into `[3,2,4]` and `[3,7]`, you could also split by taking elements at even and odd indexes (`[3,4,7]` and `[2,3]`) or even randomize the split every time.

This is , so the shortest code *in any language* measured in bytes wins.

### Test cases

As noted above, the actual format and the way to split lists in half is up to you.

```
[10,2]
[10][2]
[2,10]

[4,17,1,32]
[4,17][1,32]
[4][17][1][32]
[4,17][1,32]
[1,4,17,32]

[6,5,4,3,2,1]
[6,5,4][3,2,1]
[6,5][4][3,2][1]
[6][5][4][3][2][1]
[5,6][4][2,3][1] <- Important: This step cannot be [5,6][3,4][1,2], because 3 and 4 are on different branches in the the tree
[4,5,6][1,2,3]
[1,2,3,4,5,6]

```

# Answer
> 8 votes
# Haskell, ~~137~~ ~~128~~ ~~127~~ ~~125~~ ~~121~~ ~~109~~ 106 bytes

(-2)+(-4)=(-6) bytes thanks to nimi! Changing it to collect all the steps in a list (again due to nimi) saves 12 more bytes.

Another 3 bytes due to Laikoni, with pattern guard binding and a clever use of list comprehension to encode the guard.

```
import Data.List
g x|y<-x>>=h=x:[z|x/=y,z<-g y++[sort<$>x]]
h[a]=[[a]]
h x=foldr(\x[b,a]->[x:a,b])[[],[]]x

```

Try it online!

Splitting the lists into the odd and the even positioned elements is a shorter code than into the two sequential halves, because we're spared having to measure the `length`, then.

Works by "printing" the lists, then recursing with the split lists (`x >>= h`) *if* there actually was any splitting done, and "printing" the sorted lists; starting with the one input list; assuming the non-empty input. And instead of actual printing, just *collecting* them in a list.

The list produced by `g[[6,5..1]]`, printed line-by-line, is:

```
[[6,5,4,3,2,1]]
[[6,4,2],[5,3,1]]
[[6,2],[4],[5,1],[3]]
[[6],[2],[4],[5],[1],[3]]
[[2,6],[4],[1,5],[3]]
[[2,4,6],[1,3,5]]
[[1,2,3,4,5,6]]

```

# Answer
> 7 votes
# Wolfram Language (Mathematica), ~~146~~ ~~127~~ ~~111~~ 102 bytes

```
Join[u=Most[#/.a:{_,b=__Integer}:>TakeDrop[a,;;;;2]&~FixedPointList~#],Reverse@Most@u/.a:{b}:>Sort@a]&

```

Try it online!

Returns a `List` that contains the steps.

## Explanation

```
#/.a:{_,b=__Integer}:>TakeDrop[a,;;;;2]&

```

In an input, split all `List`s containing 2 or more integers in half. The first sublist has the odd-indexed elements (1-indexed), and the second one has the even-indexed elements.

```
u=Most[... &~FixedPointList~#]

```

Repeat that until nothing changes (i.e. all sublists are length-1). Keep all intermediate results. Store this (the `List` of all steps) in `u`.

```
Reverse@Most@u

```

Drop the last element of `u` and reverse it.

```
... /.a:{b}:>Sort@a

```

From the result above, sort all occurrences of a list of integers.

# Answer
> 6 votes
# Clean, ~~228~~ ~~206~~ ~~168~~ ~~157~~ ~~140~~ ~~121~~ 104 bytes

Builds the list of stages from the ends inwards, using the fact that the `n`-th element from the end is the sorted version of the `n`-th element from the beginning.

*Idea from JungHwan Min's comment*

```
import StdEnv
@u#(a,b)=splitAt(length u/2)u
=if(a>[])[[u]:[x++y\\y<- @b&x<- @a++ @a++ @a]][]++[[sort u]]

```

Try it online!

# Answer
> 4 votes
# Charcoal, ~~145~~ ~~133~~ ~~123~~ 122 bytes

```
≔⟦⪪Ｓ ⟧θＷ⊖Ｌ§θ⁰«⟦⪫Ｅθ⪫κ ¦|⟧≔ＥＥ⊗Ｌθ§θ÷λ²✂κ﹪λ²Ｌκ²θ»⟦⪫ΦＥθ⪫ι ι|⟧Ｗ⊖Ｌθ«≔⮌θη≔⟦⟧θＷη«≔⊟ηε≔⟦⟧ζＦ⊟η«≔εδ≔⟦⟧εＦδ⊞⎇‹ＩμＩλζεμ⊞ζλ»⊞θ⁺ζε»⟦⪫Ｅθ⪫κ ¦|

```

Try it online! Link is to verbose version of code. ~~Still having to work around Charcoal bugs...~~ Edit: Saved 5 bytes by using a double `Map` as a poor man's array comprehension. Saved 4 bytes by using `Pop` to double iterate over an array. Saved 3 bytes by using concatenation instead of `Push`. Saved 10 bytes by coming up with a golfier `while` condition that also avoids a Charcoal bug. Saved 1 byte by discovering that Charcoal does indeed have a filter operator. Explanation:

```
≔⟦⪪Ｓ ⟧θ

```

Split the input on spaces, and then wrap the result in an outer array, saving that to `q`.

```
Ｗ⊖Ｌ§θ⁰«

```

Repeat while the first element of `q` has more than one element. (The first element of `q` always has the most elements because of the way the lists are divided into two.)

```
⟦⪫Ｅθ⪫κ ¦|⟧

```

Print the elements of `q` joined with spaces and vertical lines. (The array causes the result to print on its own line. There are other ways of achieving this for the same byte count.)

```
≔ＥＥ⊗Ｌθ§θ÷λ²✂κ﹪λ²Ｌκ²θ»

```

Create a list by duplicating each element of `q`, then map over that list and take half of each list (using the alternate element approach), saving the result back in `q`.

```
⟦⪫ΦＥθ⪫ι ι|⟧

```

Print the elements of `q` joined with spaces and vertical lines. Actually, at this point the elements of `q` are either empty or single-element lists, so joining them just converts them to empty strings or their elements. The empty strings would add unnecessary trailing lines so they are filtered out. A flatten operator would have been golfier though (something like `⟦⪫Σθ|⟧`).

```
Ｗ⊖Ｌθ«

```

Repeat while `q` has more than one element. (The following code requires an even number of elements.)

```
≔⮌θη≔⟦⟧θ

```

Copy `q` to `h`, but reversed (see below), and reset `q` to an empty list.

```
Ｗη«

```

Repeat until `h` is empty.

```
≔⊟ηε

```

Extract the next element of `h` into `e`. (`Pop` extracts from the end, which is why I have to reverse `q`.)

```
≔⟦⟧ζ

```

Initialise `z` to an empty list.

```
Ｆ⊟η«

```

Loop over the elements of the next element of `h`.

```
≔εδ≔⟦⟧ε

```

Copy `e` to `d` and reset `e` to an empty list.

```
Ｆδ

```

Loop over the elements of `d`.

```
⊞⎇‹ＩμＩλζεμ

```

Push them to `z` or `e` depending on whether they are smaller than the current element of the next element of `h`.

```
⊞ζλ»

```

Push the current element of the next element of `h` to `z`.

```
⊞θ⁺ζε»

```

Concatenate `z` with any elements remaining in `e` and push that to `q`. This completes the merge of two elements of `h`.

```
⟦⪫Ｅθ⪫κ ¦|

```

Print the elements of `q` joined with spaces and vertical lines.

# Answer
> 3 votes
# Python 2, ~~145~~ 144 bytes

Idea from JungHwan Min's comment
-1 byte thanks to Jonathan Frech

```
p=input()
l=[[p]]
i=0
while 2**i<len(p):l[i+1:i+1]=[sum([[x[1::2],x[::2]][len(x)<2:]for x in l[i]],[]),map(sorted,l[i])];i+=1
for s in l:print s

```

Try it online!

# Answer
> 3 votes
# Husk, 14 bytes

```
S+ȯ†O↔hUmfL¡ṁ½

```

Takes an array containing a single array. Try it online!

## Explanation

```
S+ȯ†O↔hUmfL¡ṁ½  Implicit input, say A = [[4,17,32,1]].
           ¡    Iterate this function on A:
            ṁ½   Split each array in two, concatenate results: [[4,17],[32,1]]
                Result is [[[4,17,32,1]],
                           [[4,17],[32,1]],
                           [[4],[17],[32],[1]],
                           [[4],[],[17],[],[32],[],[1],[]],
                           ...
        mfL     Map filter by length, removing empty arrays.
                Result is [[[4,17,32,1]],
                           [[4,17],[32,1]],
                           [[4],[17],[32],[1]],
                           [[4],[17],[32],[1]],
                           ...
       U        Longest prefix of unique elements:
                       P = [[[4,17,32,1]],[[4,17],[32,1]],[[4],[17],[32],[1]]]
      h         Remove last element: [[[4,17,32,1]],[[4,17],[32,1]]]
     ↔          Reverse: [[[4,17],[32,1]],[[4,17,32,1]]]
   †O           Sort each inner array: [[[4,17],[1,32]],[[1,4,17,32]]]
S+ȯ             Concatenate to P:
                           [[[4,17,32,1]],
                            [[4,17],[32,1]],
                            [[4],[17],[32],[1]],
                            [[4,17],[1,32]],
                            [[1,4,17,32]]]
                Implicitly print.

```

The built-in `½` takes an array and splits it at the middle. If its length is odd, the first part is longer by one element. A singleton array `[a]` results in `[[a],[]]` and an empty array `[]` gives `[[],[]]`, so it's necessary to remove the empty arrays before applying `U`.

# Answer
> 2 votes
## JavaScript (ES6), 145 bytes

```
f=a=>a.join`|`+(a[0][1]?`
${f([].concat(...a.map(b=>b[1]?[b.slice(0,c=-b.length/2),b.slice(c)]:[b])))}
`+a.map(b=>b.sort((x,y)=>x-y)).join`|`:``)

```

Takes input as an array within an array, i.e. `f([[6,5,4,3,2,1]])`. Works by generating the first and last lines of the output, then splitting and calling itself again, until every sub-array has length 1. Here's a basic demonstration of how it works:

```
f([[6,5,4,3,2,1]]):
  6,5,4,3,2,1
  f([[6,5,4],[3,2,1]]):
    6,5,4|3,2,1
    f([[6,5],[4],[3,2],[1]]):
      6,5|4|3,2|1
      f([[6],[5],[4],[3],[2],[1]]):
        6|5|4|3|2|1
      end f
      5,6|4|2,3|1
    end f
    4,5,6|1,2,3
  end f
  1,2,3,4,5,6
end f

```

# Answer
> 1 votes
# Stax, ~~116(÷3\>)~~ ~~38~~ 29 bytesCP437

-9 bytes per comment by @recursive. Now the input is given as a singleton whose only element is an array of the numbers to be sorted.

```
ƒ3s}óºE/ßB╢↕êb∩áαπüµrL╞¶è,te+

```

Try it online!

Unpacked version with 35 bytes:

```
{c{Jm'|*Pc{2Mm:f{fc{Dm$wW{{eoJm'|*P

```

## Explanation

The code can be splitted to two parts. The first part visualizes splitting and the second visualizes merging.

Code for visualizing splitting:

```
{                      w    Do the following while the block generates a true value
 c                          Copy current nested array for printing
  {Jm                       Use spaces to join elements in each part
     '|*                    And join different parts with vertical bar
        P                   Pop and print

         c                  Copy current nested array for splitting
          {2Mm              Separate each element of the array to two smaller parts with almost the same size
                                That is, if the number of elements is even, partition it evenly.
                                Otherwise, the first part will have one more element than the second.
              :f            Flatten the array once
                {f          Remove elements that are empty arrays

                  c         Copy the result for checking
                   {Dm$     Is the array solely composed of singletons?
                            If yes, ends the loop.

```

The code for visualizing merging:

```
W              Execute the rest of the program until the stack is empty
 {{eoJm        For each part, sort by numeric value, then join with space
       '|*     Join the parts with vertical bar
          P    Pop and print the result

```

## Old version, actually building the nested list structure.

```
{{cc0+=!{x!}Mm',*:}}Xd;%v:2^^{;s~{c^;<~sc%v,*{2M{s^y!svsm}M}YZ!x!Q,dmU@e;%v:2^{;%v:2^-N~0{c;={scc0+=Cc%v!C:f{o}{scc0+=C{s^y!svsm}?}Y!cx!P,dcm

```

`cc0+=` is used thrice in the code to check whether the top of stack is a scalar or an array.

`{{cc0+=!{x!}Mm',*:}}X` builds a block that recursively calls itself to output a nested array of numbers properly. (Default output in Stax vectorizes a nested array before printing).

```
{                  }X    Store the code block in X
 {           m           Map each element in the list with block
  cc                     Make two copies of the element
    0+                   + 0. If the element is a scalar, nothing will change
                              If the element is an array, the element 0 will be appended
      =!{  }M            If the element has changed after the `0+` operation
                             Which means it is an array
         x!              Recursively execute the whole code block on the element

              ',*        Join the mapped elements with comma
                 :}      Bracerizes the final result

```

There are two other blocks that performs the splitting and the merging, respectively. They are too verbose and I don't care to explain (there are a little bit more information in the historical version of this post but don't expect too much).

---
Tags: code-golf, array, sorting
---


title: Polygonal Numbers!

text:
# Question
Title: Polygonal Numbers!
## Introduction

> In mathematics, a polygonal number is a number represented as dots or pebbles arranged in the shape of a regular polygon. The dots are thought of as alphas (units). These are one type of 2-dimensional figurate numbers.
>
> The number 10, for example, can be arranged as a triangle:
>
> ```
> *
> **
> ***
> ****
>
> ```
>
> But 10 cannot be arranged as a square. The number 9, on the other hand, can be:
>
> ```
> ***
> ***
> ***
>
> ```
>
> Some numbers, like 36, can be arranged both as a square and as a triangle:
>
> ```
> ******  *
> ******  **
> ******  ***
> ******  ****
> ******  *****
> ******  ******
>
> ```
>
> By convention, 1 is the first polygonal number for any number of sides. The rule for enlarging the polygon to the next size is to extend two adjacent arms by one point and to then add the required extra sides between those points. In the following diagrams, each extra layer is shown as in red.
>
> Triangular Numbers:
>
> Square Numbers:
>
> Polygons with higher numbers of sides, such as pentagons and hexagons, can also be constructed according to this rule, although the dots will no longer form a perfectly regular lattice like above.
>
> Pentagonal Numbers:
>
> Hexagonal Numbers:

Source: Wikipedia

## Your task

Given a positive integer *N* (1 \<= *N* \<= 1000), print every type of Polygonal Number *N* is starting from Triangular Numbers up to and including Icosagonal (20-gon) Numbers.

For example, the number 10 is a triangular number and a decagonal number, so the output should be something like (you can choose your own output format, but it should look somewhat like this):

```
3 10

```

## Test cases

```
1 -> 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
2 -> (None)
3 -> 3
6 -> 3 6
36 -> 3 4 13

```

For reference, the `n`-th `k`-gonal number is:

Credit: xnor

Remember, this is , so the code with the fewest bytes wins.

# Answer
> 2 votes
## Python 3, 68 bytes

```
lambda R:[s+2for s in range(1,19)if(s-2+(4+s*(s-4+8*R))**.5)/2%s==0]

```

For each potential number of sides `s+2`, solves the quadratic formula `R=s*n*(n-1)/2 + n` for `n` to see if the result is a whole number.

Compare (73 bytes):

```
lambda R:[s+2for s in range(1,19)if R in[n+s*n*~-n/2for n in range(R+1)]]

```

An alternative approach of solving for `s` gives 62 bytes in Python 3, but fails on `R=1`.

```
lambda R:{(R-n)*2/n/~-n+2for n in range(2,R+1)}&{*range(3,21)}

```

# Answer
> 1 votes
## JavaScript (ES6), 90 bytes

```
n=>[...Array(21).keys(n--)].slice(3).filter(i=>(Math.sqrt(i*i+8*i*n-16*n)+i-4)%(i+i-4)==0)

```

Solves the quadratic equation. 73 bytes on new enough versions of Firefox:

```
n=>[for(i of Array(18).keys())if(((~-i**2+8*n*-~i)**.5+~-i)/2%-~i==0)i+3]

```

# Answer
> 1 votes
# Axiom 203 bytes

```
 l(x)==(local q,m,a;v:List INT:=[];for i in 3..20 repeat(q:=solve((i-2)*n*(n-1)+2*n-2*x=0,n);if #q>1 then(m:=rhs q.1;a:=rhs q.2;if(m>0 and denom(m)=1)or(a>0 and denom(a)=1)then v:=cons(i,v)));v:=sort v;v)

```

here is less golfed and routine that show numbers

```
 l(x)==
  local q,m,a
  v:List INT:=[]
  for i in 3..20 repeat
     q:=solve((i-2)*n*(n-1)+2*n-2*x=0,n)  -- this would find only rational solutions as r/s with r,s INT
     if #q>1 then -- if exist rational solution and denominator =1=> add to list of result
        m:=rhs q.1;a:=rhs q.2;
        if(m>0 and denom(m)=1)or(a>0 and denom(a)=1)then v:=cons(i,v)
  v:=sort v
  v

 (2) ->  [[i,l(i)]  for i in 1..45]
    Compiling function l with type PositiveInteger -> List Integer

    (2)
    [[1,[3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20]], [2,[]], [3,[3]],
     [4,[4]], [5,[5]], [6,[3,6]], [7,[7]], [8,[8]], [9,[4,9]], [10,[3,10]],
     [11,[11]], [12,[5,12]], [13,[13]], [14,[14]], [15,[3,6,15]], [16,[4,16]],
     [17,[17]], [18,[7,18]], [19,[19]], [20,[20]], [21,[3,8]], [22,[5]],
     [23,[]], [24,[9]], [25,[4]], [26,[]], [27,[10]], [28,[3,6]], [29,[]],
     [30,[11]], [31,[]], [32,[]], [33,[12]], [34,[7]], [35,[5]], [36,[3,4,13]],
     [37,[]], [38,[]], [39,[14]], [40,[8]], [41,[]], [42,[15]], [43,[]],
     [44,[]], [45,[3,6,16]]]
                                                           Type: List List Any

```

# Answer
> 1 votes
# \>\<\>, 62 + 3 = 65 bytes

```
&1v
v0<;?)+8a:+1~~<
1.292:{<>+n}ao^
>:&:&=?^:&:&)?^:@:@$-{:}++

```

Expects the input at the top of the stack, so +3 bytes for the `-v` flag.

This is my first time programming in \>\<\>, so I may be missing some obvious tricks to shorten the code.

## Explanation:

### Initialization

```
&1v
v0<
1

```

Moves *N* to the register, pushes the counter to the stack (starting at `1`, which corresponds to triangular numbers), and starts the sequence with the values `0` and `1`.

### Main Loop

```
 :&:&=?^:&:&)?^:@:@$-{:}++

```

Compares the top of the stack with the register. If it is equal, go to the print routine. If it is greater, go to the reset routine. Otherwise take the difference between the top two stack items, add the counter, and add to the previous top stack item. This calculates the next polygonal number.

### Print

```
 .292:{<>+n}ao^
       ^

```

Prints the counter + 2, followed by a newline, then moves to the reset routine.

### Reset

```
v0<;?)+8a:+1~~<
1             ^

```

Removes the top two stack items and increments the counter. Ends the program if the counter is greater than 18, otherwise pushes the starting numbers `0` and `1` to the stack and returns to the main loop.

# Answer
> 1 votes
# Jelly, 22 bytes

```
18pȷµḢ×’×H+µ€_³¬FT:ȷ+3

```

Try it online!

**Explanation**

```
18pȷµḢ×’×H+µ€_³¬FT:ȷ+3
18pȷ                   - All possible (k-2,n) pairs
    µ      µ€          - to each pair compute the corresponding polygonal number:
     Ḣ                 -   retrieve k-2
      ×’               -   multiply by n-1
        ×H             -   multiply by half of n
          +            -   add n
             _³        - subtract the input. There will now be 0's at (k-2,n) pairs which produce the input
               ¬FT     - retrieve all indices of 0's. The indices are now (k-2)*1000+n
                  :ȷ   - floor division by 1000, returning k-3
                    +3 - add 3 to get all possible k.

```

# Answer
> 0 votes
# AWK, 67 bytes

```
{for(k=2;++k<21;)for(n=0;++n<=$1;)if((k/2-1)*(n*n-n)+n==$1)print k}

```

Try it online!

I tried actually solving the quadratic, but checking each value to see if it works is shorter *(and less error-prone for me)*

# Answer
> 0 votes
# R, ~~68~~ 66 bytes

```
N=scan();m=expand.grid(k=1:18,1:N);n=m$V;m$k[m$k*n*(n-1)/2+n==N]+2

```

Reads `N` from stdin. Computes the first `N` k-gonal numbers and gets the `k` where they equal `N`, using xnor's formula; however, saves bytes on parentheses by using `1:18` instead of `3:20` and adding `2` at the end.

`expand.grid` by default names the columns `Var1`, `Var2`, ..., if a name is not given. `$` indexes by partial matching, so `m$V` corresponds to `m$Var2,` the second column.

old version:

```
N=scan();m=expand.grid(k=3:20,1:N);n=m$V;m$k[(m$k-2)*n*(n-1)/2+n==N]

```

Try it online!

# Answer
> 0 votes
# Pari/GP, 34 bytes

Pari/GP has a built-in to test whether a number is a polygonal number.

```
x->[s|s<-[3..20],ispolygonal(x,s)]

```

Try it online!

# Answer
> 0 votes
# Jelly, 20 bytes

I just started writing an effective dupe of this challenge (albeit covering all k\>1 not just \[1,20\]) ...so instead I'll answer it!

```
Ṫð’××H+⁸
18pÇċ¥Ðf⁸+2

```

A full program printing a Jelly list representation of the results\*

**Try it online!**

* No results prints nothing;
a single result prints just that number;
multiple results prints a `[]` enclosed, `,`  separated list of the numbers

### How?

```
Ṫð’××H+⁸ - Link 1, ith (x+2)-gonal number: list [x,i]   e.g. [3,4] (for 4th Pentagonal)
Ṫ        - tail & modify (i.e. yield i & make input [x])     4
 ð       - new dyadic chain, i.e. left = i, right = [x]
  ’      - decrement i                                       3
   ×     - multiply by [x]                                   [9]
     H   - halve [x]                                         [2]
    ×    - multiply                                          [18]
       ⁸ - chain's left argument, i                          4
      +  - add                                               [22]

18pÇċ¥Ðf⁸+2 - Main link: number, n                      e.g. 36
18p         - Cartesian product of range [1,18] with n       [[1,1],[1,2],...,[1,36],[2,1],...,[18,1],[18,2],[18,36]]
            -   (all pairs of [(k-2),i] which could result in the ith k-gonal number being n)
      Ðf    - filter keep if this is truthy:
        ⁸   -   chain's left argument, n                     36
     ¥      -   last two links as a dyad:
   Ç        -     call the last link as a monad (note this removes the tail of each)
    ċ       -     count (this is 1 if the result is [n] and 0 otherwise)
            -                            filter keep result: [[1],[2],[11]]
         +2 - add two                                        [[3],[4],[13]]
            - implicit print ...due to Jelly representation: [3, 4, 13]

```

---
Tags: code-golf, number, classification
---