title: How many friday the 13th in a year?

text:
# Question
Title: How many friday the 13th in a year?
Your challenge is to write a program which, given a year, outputs the number of "Friday 13ths" in it.

**Rules & Details:**

* You can take input via `STDIN`, or as an argument passed to your program.
* You should output the result to `STDOUT`.
* You may assume that input will be a valid year, and does not pre-date the Gregorian calendar (undefined behaviour is permitted in these cases).
* Calendar/Date libraries are allowed.

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

(Related challenge link)

# Answer
> 3 votes
# APL (Dyalog APL) with cal from dfns, 29 bytes

```
+/{13∊⍎,⍉3↑¯5↑⍉2↓cal⍵}¨⎕,¨⍳12

```

Try it online!

`⍳ 12` the integers one through twelve

`⎕ ,¨` take numeric input and prepend to each of the twelve numbers

`{` on each of the pairs, apply the function…

`cal⍵` get a calendar for that year-month

`2 ↓` drop two rows (caption and days)

transpose (so we can address columns instead of rows)

`¯5 ↑` take the last five (two digits for each of Friday and Saturday plus one space)

`3 ↑` take the first two (two digits for Friday plus a space)

transpose (so we get reading order)

`,` ravel

execute as APL expression (gives list of Fridays' dates)

`13 ∊` is thirteen a member of that list?

`+/` sum the 12 Booleans

---

Using @Wrzlprmft's algorithm, we can do it without libraries for 53 bytes:

```
'21232211321211'⊃⍨14|2 3 ¯1+.×⊢,0≠.=400 100 4∘.|-∘0 1

```

`-∘0 1` subtract zero and one

`400 100 4 ∘.|` division remainder table for the two years (across) divided by these numbers (down)

`0 ≠.=` inner "product" with 0, but using ≠ and = instead of +.×

`⊢ ,` prepend the unmodified argument year

`2 3 ¯1 +.×` inner product with these numbers

`14 |` division remainder when divided by fourteen

`'21232211321211' ⌷⍨` index into this string

# Answer
> 12 votes
# Mathematica ~~49 46 45 44~~ 42

As a **pure function**: 42 chars

```
DayName@{#,m,6}~Table~{m,12}~Count~Friday&

```

Example

```
DayName@{#,m,6}~Table~{m,12}~Count~Friday&[2013]

```

> 2

---

As a **named function**: 44 chars

```
f=DayName@{#,m,6}~Table~{m,12}~Count~Friday&

```

Examples

```
f[1776]
f[2012]
f[2013]
f[2014]

```

> 2
> 3
> 2
> 1

# Answer
> 8 votes
## Ruby, ~~49 48 47~~ 46

```
f=->m{(1..12).count{|i|Time.gm(m,i,6).friday?}}

```

Edit: Shaved a character by going back a week, thanks to Jan, and another by switching from Time.new to Time.gm

Edit: At the expense of obfuscating it a bit more, I can get to 46 with

```
f=->m{(1..12).count{|i|Time.gm(m,i,8).wday<1}}

```

# Answer
> 8 votes
## Powershell, ~~68~~ ~~63~~ ~~58~~ ~~52~~ 50

Thanks Iszi for the tip.

```
$n=$args;(1..12|?{!+(date $n-$_).DayOfWeek}).Count

```

Using the fact that if the 1st day in the month is Sunday, the 13th will be Friday.

I've also tried:

```
(1..12|?{!+(date $args-$_).DayOfWeek}).Count

```

but it's not the same `$args` inside the script block.

# Answer
> 7 votes
## bash ~~47~~ 36

```
seq -f$1-%g-6 12|date -f-|grep -c ^F

```

Thanks @DigitalTrauma for saving 10 chars by using `seq` with default start to `1`.

~~```
date -f<(printf "%s\n" $1-{1..12}-6)|grep -c ^F

```~~

(Previous version using `echo` present a bug because of the empty line when `<(echo $1-{1..12}-6$'\n')`. So this function worked fine until today **is** a Friday.

### Lets see:

```
set -- 2013
seq -f$1-%g-6 1 12|date -f-|grep -c ^F
2

date -f<(printf "%s\n" $1-{1..12}-13)|grep -c ^F
2

```

This is **locale** dependant, so if this don't work, you may have to

```
export LANG=C

```

or

```
LANG=C date -f<(printf "%s\n" $1-{1..12}-13)|grep -c ^F

```

### Into a function; +7 -\> 43

```
f(){ seq -f$1-%g-6 12|date -f-|grep -c ^F;}

f 2013
2

for i in {2010..2017};do echo $i $(f $i) ;done
2010 1
2011 1
2012 3
2013 2
2014 1
2015 3
2016 1
2017 2

```

### Bonus: +78 -\> 121

From there, if my function become:

```
f(){ o=();for t in $(seq -f$1-%g-6 12|date -f- +%a,%b);do [ "${t:0:1}" = "F" ]&&o+=(${t#*,});done;echo ${#o[@]} ${o[@]};}

```

or

```
f(){ o=();
     for t in $(seq -f$1-%g-6 1 12|date -f- +%a,%b);do
         [ "${t:0:1}" = "F" ]&&o+=(${t#*,})
       done
     echo ${#o[@]} ${o[@]}
}

for i in {2010..2017};do echo $i $(f $i) ;done
2010 1 Aug
2011 1 May
2012 3 Jan Apr Jul
2013 2 Sep Dec
2014 1 Jun
2015 3 Feb Mar Nov
2016 1 May
2017 2 Jan Oct

```

# Answer
> 6 votes
Not using any libraries or built-in date functions:

# Golfscript – 51

```
~..({4/.25/.4/--@}2*2*\3*+-
14%' [3/=RI[)a%:*.'\=5%

```

> `' [3/=RI[)a%:*.'` could as well be `'feefefgeeffgfe'`

# Python – ~~82~~ 79

Essentially the same algorithm.

```
l=lambda y:y/4-y/100+y/400
i=input()
print"21232211321211"[(2*i+3*l(i)-l(i-1))%14]

```

Using this trick, this can be golfed down further to:

```
l=lambda y:y/4-y/100+y/400
i=input()
print 94067430>>(4*i+6*l(i)-2*l(i-1))%28&3

```

---

> This exploits the fact that, calender-wise, there are only 14 different years, which are distinguishable by their last day and whether they are leaping. `l` calculates the number of leap years up to its argument (if the Gregorian calendar extended backwards to the year 1). `(2*i+3*l(i)-l(i-1))%14` is short for `l(i)-l(i-1)+(i+l(i))%7*2`, where `l(i)-l(i-1)` tells us whether the argument is a leap year and `i+l(i)` sums up the shifts of the last day (one in a normal year, two in a leap year).

# Answer
> 5 votes
## R ~~76~~ ~~72~~ 57

```
sum(format(as.Date(paste(scan(),1:12,1,sep="-")),"%w")<1)

```

# Answer
> 5 votes
## Python2.7 ~~90~~ 86

```
from datetime import*
s=c=0
exec's+=1;c+=date(%d,s,9).weekday()<1;'%input()*12
print c

```

Monday the 9th may not have quite the same ring to it but works just as well.

Edit: A year and a half to notice that `date` is shorter than `datetime` :)

# Answer
> 4 votes
# C ~~301+~~ 287

```
main(int x,char**v){char p[400],*a[]={"abbababbacaacbac","bacabbb","baabbaca","abbb","aabbacaac","abbbbcaac","abbbbaabb"},*b="adcadcadcaebcadcadcafbcadcadcagbcadcadcadc";int c=0,i,y=atoi(v[0]);for(i=0;i<42;i++)strcpy(&p[c],a[b[i]-'a']),c+=strlen(a[b[i]-'a']);printf("%d",p[y%400]-'`');}

```

Not the shortest answer, but uses no libraries.

# Answer
> 4 votes
## JavaScript, 70

```
f=function(a){b=0;for(c=12;c--;)b+=!new Date(a,c,1).getDay();return b}

```

# Answer
> 4 votes
# C (~~151~~ ~~145~~ ~~137~~ ~~131~~ 130 chars)

I am surprised to see that there is only one other solution that doesn't use built-in calendar tools. Here is a (highly obfuscated) mathematical approach, also in C:

```
f(x){return(x+(x+3)/4-(x+99)/100+!!x)%7;}main(int x,char**v){int y=atoi(v[1])%400,a=f(y+1);putchar('1'+((f(y)&3)==1)+(a>2&&a-5));}

```

(The above compiles in GCC with no errors)

# Alternative solution: C (287-\>215 chars)

I rather enjoyed Williham Totland's solution and his use of compression. I fixed two small bugs and tweaked the code to shorten its length:

```
main(int x,char**v){char p[400],*a[]={"1221212213113","213122221122131","12213113","22213113","22221122","2131"},*b="abababafcbababafdbababafebababab";*p=0;for(;*b;b++)strcat(p,a[*b-97]);putchar(p[atoi(v[1])%400]);}

```

# Answer
> 4 votes
# PHP, 82

`<?for($i=1,$c=0;$i<13;$i++)$c+=(date("N",mktime(0,0,0,$i,1,$argv[1]))==7);echo $c;`

Based on

"Any month that starts on a Sunday contains a Friday the 13th, and there is at least one Friday the 13th in every calendar year."

From http://en.wikipedia.org/wiki/Friday\_the\_13th

# Answer
> 3 votes
# k

64 characters

```
{+/6={x-7*x div 7}(.:')x,/:(".",'"0"^-2$'$:1+!:12),\:".13"}[0:0]

```

Reads from stdin

# Answer
> 3 votes
## Common Lisp (CLISP), 149

```
(print
    (loop for i from 1 to 12 count
        (= 4 (nth-value 6
            (decode-universal-time
                (encode-universal-time 0 0 0 13 i
                    (parse-integer (car *args*)) 0))))))

```

# Answer
> 2 votes
# C# ~~110~~ ~~101~~ ~~93~~ 92

```
int f(int y){int c=0;for(int i=1;i<13;i++)c+=new DateTime(y,i,8).DayOfWeek>0?0:1;return c;}

```

# C# Linq 88

```
int g(int y){return Enumerable.Range(1,12).Count(m=>new DateTime(y,m,8).DayOfWeek==0);}

```

Thanks to Jeppe Stig Nielsen for linq and suggestion of checking for sunday on the 8th.

Thanks to Danko Durbić for suggesting `>` instead of `==`.

# Answer
> 2 votes
# PHP, 55 bytes

```
for(;++$i<13;)$c+=!date(w,strtotime($argn.-$i));echo$c;

```

Run with `echo <year> | php -nR '<code>'`.

Basically the same that Oleg tried and Damir Kasipovic did, just with better golfing:
Every month that starts with a sunday, has a Friday the 13th.
So I loop through the months and count the first days that are sundays.

**breakdown**

```
for(;++$i<13;)          // loop $i from 1 to 12
    $c+=!                   // 4. if result is not truthy (weekday==0), increment $c
        date(w,             // 3. get weekday (0 stands for Sunday)
            strtotime(      // 2. convert to timestamp (midnight 1st day of the month)
                $argn.-$i   // 1. concatenate year, "-" and month
            )
        )
    ;
echo$c;                 // output

```

# Answer
> 1 votes
# Python 195 / 204

Works only for previous years, because `monthdatescalendar` returns a calendar for the given year until *now*. I think there is a lot of optimizing potential left :).

```
import calendar, sys
c=calendar.Calendar()
f=0
for m in range(1,12):
 for w in c.monthdatescalendar(int(sys.argv[1]),m):
  for d in w:
   if d.weekday() == 4 and d.day == 13:
    f=f+1
print(f)

```

Another solution, works for every date but it isn't smaller:

```
import datetime,sys
y=int(sys.argv[1])
n=datetime.date
f=n(y,1,1)
l=n(y,12,31)
i=0
for o in range(f.toordinal(), l.toordinal()):
 d=f.fromordinal(o)
 if d.day == 13 and d.weekday() == 4:
  i=i+1
print(i)

```

# Answer
> 1 votes
# Bash (52 47 characters)

```
for m in {1..12};do cal $m $Y;done|grep -c ^15

```

# Answer
> 1 votes
# K, 42

```
{+/1={x-7*x div 7}"D"$"."/:'$+(x;1+!12;1)}

```

.

```
k){+/1={x-7*x div 7}"D"$"."/:'$+(x;1+!12;1)}'1776 2012 2013 2014
2 3 2 1

```

# Answer
> 1 votes
# Rebol, 63

```
f: 0 repeat m 12[d: do ajoin["6-"m"-"y]if d/weekday = 5[++ f]]f

```

Usage example in Rebol console:

```
>> y: 2012
== 2012

>> f: 0 repeat m 12[d: do ajoin["6-"m"-"y]if d/weekday = 5[++ f]]f
== 3

```

Alternative solution which collects all the Friday 13th in given year is:

```
>> collect[repeat m 12[d: do ajoin["13-"m"-"y]if d/weekday = 5[keep d]]]
== [13-Jan-2012 13-Apr-2012 13-Jul-2012]

```

# Answer
> 1 votes
## Bash and Sed, 39

```
ncal $1|sed '/F/s/13/\
/g'|grep -c ^\ 2

```

`ncal` prints a calendar for the given year with days of the week down the left.

`sed` with a `/g` flag subs out all 13s with newlines

`grep -c` counts the lines that start with " 2" (20 always follows 13)

Thanks to @DigitalTrauma for finding a bug in my old version and proposing a solution!

# Answer
> 1 votes
# Scala, ~~76~~ 68 characters

In 78 chars:

`def f(y:Int)=0 to 11 count(new java.util.GregorianCalendar(y,_,6).get(7)==6)`

Nothing out of ordinary, except for using magical numbers for `DAY_OF_WEEK = 7` and `FRIDAY = 6`.

68 character version:

`def f(y:Int)=0 to 11 count(new java.util.Date(y-1900,_,6).getDay==5)`

Yes, Java changed values of day of the week constants between API's.

# Answer
> 1 votes
## Perl 6, ~~55~~ 53

```
{sum (1..12).map: {Date.new($_,$^a,1).day-of-week>6}}

```

Old answer:

```
{sum (1..12).map: {Date.new($_,$^a,13).day-of-week==5}}

```

# Answer
> 0 votes
**Python(v2) 120**

```
import datetime as d,sys
s=0
for m in range(1, 13):
    if d.datetime(int(sys.argv[1]),m,6).weekday()==4: s=s+1
print s

```

# Answer
> 0 votes
## Perl + lib POSIX 55

With the idea of not looking for `13th` but first, and as `sunday` is `0` this let save 3 chars! Thanks @ Iszi and Danko Durbić!

```
$==$_;$_=grep{!strftime"%w",0,0,0,1,$_,$=-1900}(0..11)

```

Could compute 2010 to 2017 (for sample) in this way:

```
perl -MPOSIX -pE '$==$_;$_=grep{!strftime"%w",0,0,0,1,$_,$=-1900}(0..11)' <(
    printf "%s\n" {2010..2017})
11321312

```

(Ok, there is no *newline*, but that was not asked;)

### Old post: 63

```
$==grep{5==strftime"%w",0,0,0,13,$_,$ARGV[0]-1900}(0..11);say$=

```

### In action:

```
for i in {2010..2017};do
    echo $i $(
        perl -MPOSIX -E '
            $==grep{5==strftime"%w",0,0,0,13,$_,$ARGV[0]-1900}(0..11);say$=
            ' $i );
  done
2010 1
2011 1
2012 3
2013 2
2014 1
2015 3
2016 1
2017 2

```

# Answer
> 0 votes
In **Smalltalk** (Squeak/Pharo flavour), implement this method in Integer (**86** chars)

```
countFriday13^(1to:12)count:[:m|(Date year:self month:m day:13)dayOfWeekName='Friday']

```

Then use it like this: `2014countFriday13`.

Of course, we could use a shorter name, but then it would not be Smalltalk

# Answer
> 0 votes
# C++ - Too many bytes :(

I tried a solution which doesn't make use of any date libraries.

I found a pretty cool (if I may say so myself) solution. Unfortunately I can't get it shorter than this, which really bugs me because it feels like there should be a better way.

The solution hinges on this algorithm which is only 44 bytes in itself. Unfortunately I need another 100 bytes to wrap it nicely...

```
#include<stdlib.h>
main(int,char**v){int f=0,d,m,y;for(m=1;m<13;++m)d=13,y=atoi(v[1]),(d+=m<3?y--:y-2,23*m/9+d+4+y/4-y/100+y/400)%7-5||++f;return f;}

```

Output through the return code (in C++, using `cout` or `printf` or anything like that requires another `#include`, which would blow up the solution even more).

Driver / test program:

```
# Make sure we're not running an old version
rm doomsday.exe

gcc doomsday.cpp -o doomsday.exe

./doomsday.exe 1776
echo 1766: $?

./doomsday.exe 2012
echo 2013: $?

./doomsday.exe 2013
echo 2013: $?

./doomsday.exe 2014
echo 2014: $?

echo `wc doomsday.cpp -c` characters

```

Output of the driver program:

```
$ ./test_doomsday
1766: 2
2013: 3
2013: 2
2014: 1
150 doomsday.cpp characters

```

# Answer
> 0 votes
# Clojure, ~~207~~ 187 bytes

-20 bytes by getting rid of the `import`, and some whitespace I missed.

```
(import '[java.time LocalDate DayOfWeek])#(loop[d(LocalDate/parse(str %"-01-01"))c 0](if(=(.getYear d)%)(recur(.plusDays d 1)(if(and(=(.getDayOfMonth d)13)(= (.getDayOfWeek d) DayOfWeek/FRIDAY))(inc c)c))c))

```

Starting on Janauary 1st of the given year, it loops over each day. If the day is Friday the 13th, it increments the count. It continues to loop until it reaches the next year.

```
(import '[java.time LocalDate DayOfWeek])

(defn count-friday-13ths [year]
  (loop [d (LocalDate/parse (str year "-01-01")) ; Starting date
         c 0] ; The count
    (if (= (.getYear d) year) ; If we haven't moved onto the next year...
      (recur (.plusDays d 1) ; Add a day...
             (if (and (= (.getDayOfMonth d) 13) ; And increment the count if it's Friday the 13th
                      (= (.getDayOfWeek d) DayOfWeek/FRIDAY))
               (inc c) c))
      c))) ; Return the count once we've started the next year.

```

# Answer
> 0 votes
# PHP, no builtins, 81 bytes

```
echo 0x5da5aa76d7699a>>(($y=$argn%400)+($y>102?$y>198?$y>299?48:32:16:0))%28*2&3;

```

Run with `echo <year> | php -nR '<code>'`.

**breakdown**

Weekdays repeat every 400 years.
In the results for 1600 to 1999 (for example), there is a 28-length period with just three gaps:

```
  0:2212122131132131222211221311
 28:2212122131132131222211221311
 56:2212122131132131222211221311
 84:2212122131132131122
103:       131132131222211221311
124:2212122131132131222211221311
152:2212122131132131222211221311
180:2212122131132131222
199:       131132131222211221311
220:2212122131132131222211221311
248:2212122131132131222211221311
276:221212213113213122221122
300:            2131222211221311
316:2212122131132131222211221311
344:2212122131132131222211221311
372:2212122131132131222211221311

```

After adjusting the year for these gaps, we can get the result with a simple hash:

```
$y=$argn%400;foreach([300,199,103]as$k)$y<$k?:$y+=16;
echo"2212122131132131222211221311"[$y%28];

```

Not short (95 bytes) but pretty. And we can golf

* 4 bytes by using a ternary chain for the offset,
* 8 bytes by converting the hash map from a base4 string to integer,
* one more by using the hex representation,
* and one by merging the expressions.

# Answer
> 0 votes
# Japt `-x`, ~~10~~ 8 bytes

```
CÆ!ÐUX e

```

Try it

```
CÆ5¥ÐUXD e     :Implicit input of integer U
C              :12
 Æ             :  Map each X in the range [0,C) (months are 0-indexed in JavaScript)
  5¥           :  Check if 5 is equal to
    ÐUXD       :  new Date(U,X,13)
         e     :  0-based index of day of the week
               :Implicitly reduce by addition and output

```

# Answer
> 0 votes
# JavaScript, ~~56~~ 47 bytes

```
f=(y,m=12)=>m&&f(y,--m)+!new Date(y,m).getDay()

```

Try It Online!

# Answer
> 0 votes
# C, 76 bytes

A function that accepts a year and returns the count of Fridays the 13th for that year:

```
d(y){return(y+y/4-y/100+y/400)%7;}f(y){return(22>>d(y)&1|2)-(55>>d(y-1)&1);}

```

If a full program is really required, it comes in at **111** bytes, accepting a single argument and printing to standard out:

```
d(y){return(y+y/4-y/100+y/400)%7;}main(y,v)char**v;{y=atoi(*++v);putchar('0'+(22>>d(y)&1|2)-(55>>d(y-1)&1));}

```

# Explanation

```
int day_index(int year)
{
    return (year + year/4 - year/100 + year/400) % 7;
}
int f(int year)
{
    const char a[] = "2332322";
    const char b[] = "1110110";
    return a[day_index(year)]
        -  b[day_index(year-1)];
}

```

We split the year into two parts (Jan-Feb and Mar-Dec) so that leap years don't disrupt the calculation.

The helper function computes the weekday of New Year's Eve (0 = Sunday). We first use this to determine (in `a`) how many Fridays the 13th are in March-December. Then we use the weekday index of the preceding year to get the count from `b` for January and February.

The golfed code uses a bit mask rather than a character array: `a` becomes `22` and `b` becomes `55`.

# Demo

The demo is on Try It Online.

```
#include <stdio.h>
int main(void)
{
    for (int year = 1990;  year < 2050;  ++year) {
        printf("%d: %d\n", year, f(year));
    }
}

```

```
1990: 2
1991: 2
1992: 2
1993: 1
1994: 1
1995: 2
1996: 2
1997: 1
1998: 3
1999: 1
2000: 1
2001: 2
2002: 2
2003: 1
2004: 2
2005: 1
2006: 2
2007: 2
2008: 1
2009: 3
2010: 1
2011: 1
2012: 3
2013: 2
2014: 1
2015: 3
2016: 1
2017: 2
2018: 2
2019: 2
2020: 2
2021: 1
2022: 1
2023: 2
2024: 2
2025: 1
2026: 3
2027: 1
2028: 1
2029: 2
2030: 2
2031: 1
2032: 2
2033: 1
2034: 2
2035: 2
2036: 1
2037: 3
2038: 1
2039: 1
2040: 3
2041: 2
2042: 1
2043: 3
2044: 1
2045: 2
2046: 2
2047: 2
2048: 2
2049: 1

```

# Answer
> 0 votes
# Lua, 95 bytes

```
n=0 for i=1,12 do n=os.date('%w',os.time{month=i,day=13,year=...})=='5'and n+1or n end print(n)

```

Try it online!

# Answer
> 0 votes
# JavaScript (Node.js), 47 bytes

```
f=(y,m=12)=>m&&f(y,--m)+!new Date(y,m).getDay()

```

Attempt This Online!

-2 bytes thanks to l4m2

# Answer
> 0 votes
# Scala 3, 107 bytes

Golfed version. Attempt This Online!

```
y=>(1 to 12).map{m=>if(java.time.LocalDate.of(y,m,6).getDayOfWeek==java.time.DayOfWeek.FRIDAY)1 else 0}.sum

```

Ungolfed version. Attempt This Online!

```
import java.time._

object Main {
  def main(args: Array[String]): Unit = {
    println(countFridays(1776))
    println(countFridays(2012))
    println(countFridays(2013))
    println(countFridays(2014))
  }

  def countFridays(year: Int): Int = {
    (1 to 12).map { month =>
      val firstDay = LocalDate.of(year, month, 6).getDayOfWeek
      if (firstDay == DayOfWeek.FRIDAY) 1 else 0
    }.sum
  }
}

```

# Answer
> 0 votes
# Go, 114 bytes

```
import."time"
func f(y int)(c int){for i:=0;i<12;i++{if Date(y,Month(i+1),1,0,0,0,0,UTC).Weekday()<1{c++}}
return}

```

Counts months starting with Sundays.

Attempt This Online!

# Answer
> 0 votes
# Rust, 103 bytes

Golfed version. Run it on Rust Playground!

```
fn c(y:i32)->i32{(1..=12).filter(|m|NaiveDate::from_ymd(y,*m,6).weekday()==Weekday::Fri).count()as i32}

```

Ungolfed version. Run it on Rust Playground!

```
use chrono::{Datelike, Weekday, NaiveDate};

fn main() {
    println!("{}", count_fridays(1776));
    println!("{}", count_fridays(2012));
    println!("{}", count_fridays(2013));
    println!("{}", count_fridays(2014));
}

fn count_fridays(year: i32) -> i32 {
    let mut count = 0;
    for month in 1..=12 {
        let date = NaiveDate::from_ymd(year, month, 6);
        if date.weekday() == Weekday::Fri {
            count += 1;
        }
    }
    count
}

```

---
Tags: code-golf, date
---


title: Counting universal n-ary logic gates

text:
# Question
Title: Counting universal n-ary logic gates
## Background

A classical logic gate is an idealized electronic device implementing a Boolean function, i.e. one that takes a certain number of Boolean inputs and outputs a Boolean. We only consider two-input logic gates in this challenge.

There are \\$2^{2 \times 2} = 16\\$ distinct two-input logic gates (2×2 input combinations and 2 possible outputs for each input combination). Out of the 16, only two, namely NAND and NOR gates, are **universal**, in the sense that you can build arbitrary circuits (any Boolean function) by composing the single type of gates. CGCCers might recognize NAND gates because we had a few challenges to build arbitrary circuits out of them.

```
NAND | 0   1      NOR | 0   1
-----+-------    -----+-------
  0  | 1   1       0  | 1   0
  1  | 1   0       1  | 0   0

```

We can generalize the concept of logic gates to n-ary inputs and outputs instead of Booleans, for example ternary for \\$n=3\\$. (Physical three-state circuits are also being studied.)

For ternary logic gates, the allowed states are often written as `- 0 +`. There are \\$3^{3 \times 3} = 19683\\$ distinct ternary logic gates in total, and Craig Gidney managed to enumerate 3774 universal ternary logic gates out of the 19683. (Full C# code)

Typos in the blog post and an off-by-one error corrected thanks to @AnttiP

One such logic gate looks like this (named `tand` in the blog post):

```
tand | -   0   +
-----+-----------
  -  | 0   +   +
  0  | +   +   +
  +  | +   +   -

```

Another looks like this: (X can take any value out of `-0+`. All three gates represented by this pattern are universal.)

```
  ?  | -   0   +
-----+-----------
  -  | +   -   0
  0  | X   -   -
  +  | +   +   -

```

On the other hand, Malbolge's Crazy operator is NOT universal.

```
 crz | -   0   +
-----+-----------
  -  | 0   -   -
  0  | 0   -   +
  +  | +   +   0

```

For \\$n=1\\$, there is only one possible logic gate (constant), and it is trivially universal because the one logic gate can build every possible (the only one) logic gate.

## Challenge

Given the value of \\$n \ge 1\\$, compute the number of distinct universal n-ary logic gates.

Standard rules apply. The shortest code in bytes wins. Note that your code must theoretically calculate the answer for any valid input, when run in an idealized machine (integers and/or floats have unlimited precision) with enough but finite time and memory.

The known values are:

```
1 -> 1
2 -> 2
3 -> 3774
4 -> 942897552 (first calculated by @AnttiP, needs cross-check)

```

# Answer
# Python 3.8 (pre-release), 287 282 242 bytes

-5 bytes thanks to @Dialfrost

```
f=lambda n,g=0,c=0:g<n**len(e:=range(n*n))!=(s:={g,sum(i//n*n**i for i in e),sum(i%n*n**i for i in e)})and f(n,g+1,c+([s:=s|{sum(g//n**(l//n**i%n*n+r//n**i%n)%n*n**i for i in e)}for _ in"a"*n**n**2for l in s for r in s]!=len(s)==n**n**2))or c

```

Try it online!

Uses a simple integer encoding of the gates, and composes them to depth `n**(n*n)` which should be sufficient. It's able to calculate up to `n=2`.

Full disclosure, this python golf is just to qualify this answer as code golf. The rest of this answer will explain how to calculate `n=4`

# Explanation of the algorithm used to calculate n=4

The following algorithm works for all `n>=2`. In this explanation I refer to gates (also) as functions. `f(a,b)` denotes the value of gate `f` with inputs `a` and `b`. Gates can be composed just like functions. To keep every function binary, I often use the special functions `l(a,b)=a` and `r(a,b)=b` (which just pass the left/right argument).

## Core algorithm

### Unary completeness

A gate `f` is said to be unary complete if it's possible to create every unary function using `f`. Obviously, `f` has to be unary complete to be functionally complete.

We first check if `f` is unary complete. If not, then it's not functionally complete. Then we move to the next section.

### Functional completeness

Assuming that `f` is unary complete, we can check if `f` is functionally complete with the two following tests.

### Lonelyness-test

We want to find some symbols `a, b, c, d` where `a≠b` and `c≠d`, so that `f(a, c)` is distinct from `f(a, d)`, `f(b, c)` and `f(b, d)`. This means that `f` is "lonely".

Using these values, and unary functions, we can simulate all of boolean logic.

If there are no such `a, b, c, d` I claim that `f` can't be functionally complete.

To see why, let's look at how non-lonely functions compose. Note that the functions `l(x,y)=x` and `r(x,y)=y` are not lonely. Assume `L` and `R` are non-lonely functions. `g(a,b)=f(L(a, b), R(a,b))`. In general, `L`, `R` and `f` have the one of the three following "truth" tables, for the relevant inputs:

```
. a b
c x x
d y y

. a b
c x y
d x y

. a b
c x y
d y x

```

It should be clear that composing these does not make the resulting function lonely. This is a finitary problem and can be easily proved with brute-force. It is the same reason `xor` and `not` are not functionally complete.

In other words, composing non-lonely functions makes non-lonely functions, and since some gates are lonely, a non-lonely gate cannot be universal.

### Constructible-test

Again, we assume `f` is unary complete, and also lonely.

A function `f` is n+1-constructible if there are some subsets of the alphabet `L` and `R` where `|L|=|R|=n`, `|f[L,R]|≥n+1`. A function `f` is constructible iff it is n-constructible for all `n≥3` up to the length of the alphabet.

If `f` is constructible, then it is definitely functionally complete. You can just convert your input to base-2, do whatever calculations you want, and then convert back to the full alphabet.

Now is it possible to not be constructible and still be functionally complete? No.

Let's assume that there is some `n` so that `f` is not n-constructible. Note that the functions `l(x,y)=x` and `r(x,y)=y` are never n-constructible. Assume `L` and `R` are non-n-constructible functions. Then `g(a,b)=f(L(a,b),R(a,b))` is also non-n-constructible. Because the image of `L` and `R` has cardinality `≤n`, so does `g`. Therefore `g` is also non-n-constructible

Therefore `f` has to be constructible to be functionally complete, because again, non-n-constructible gates compose to create non-n-constructible gates and some gates are n-constructible.

## Optimizations

### Data Format

A duadic function `f` is represented as a `n*n` list, so that `f(a, b) = list[a*n+b]`. This is a bit slow, so for `n=4` I use a 32-bit integer. Every function has a unique index. The indices start from 0 and have no gaps. Every monadic function `f(a,b)=g(b)` has a unique index. It also starts from 0 and has no gaps.

### Transposition

A transposition `fᵀ` is defined as `fᵀ(a,b)=f(b,a)`

### Permutation

`p` is a permutation of the alphabet. `p(x)` applies the permutation. `p⁻¹(x)` applies the inverse. `p(p⁻¹(x))=p⁻¹(p(x))=x`.

`fₚ` is defined as `fₚ(a,b)=p⁻¹(f(p(a),p(b)))`

### Theorem 1

Claim: `f` is functionally complete, iff `fᵀ` also is.

Proof: You can just swap the arguments lol

### Theorem 2

Claim: `f` is functionally complete, iff `fₚ` also is (for all permutations `p`)

Proof: When you do function composition with `fₚ`, the outer and inner permutations cancel out. So the "meat" of the function doesn't change, just that the alphabet is relabled.

### Minimal representation

`f` is said to be minimal if `f≤fₚ` and `f≤fₚᵀ` for all permutations `p` (here  refers to some total order). By theorem 1 and 2, we only need to consider minimal elements.

# Rust code for n=4

## main.rs

```
#![feature(let_else)]
#![feature(map_first_last)]
#![feature(adt_const_params)]
#![feature(generic_const_exprs)]
#![feature(label_break_value)]
use indicatif::{ProgressBar, ProgressStyle};
use itertools::Itertools;
use rand::Rng;
use rayon::prelude::*;
use std::sync::atomic::AtomicBool;
use std::sync::atomic::AtomicUsize;
use std::sync::atomic::Ordering::*;
use std::thread;

#[cfg(not(debug_assertions))]
macro_rules! get_unsafe {
    [$a:expr, $i:expr] => {
        *unsafe {$a.get_unchecked($i)}
    };
}

#[cfg(debug_assertions)]
macro_rules! get_unsafe {
    [$a:expr, $i:expr] => {
        *$a.get($i).unwrap()
    };
}

#[cfg(not(debug_assertions))]
macro_rules! get_mut_unsafe {
    [$a:expr, $i:expr] => {
        *unsafe {$a.get_unchecked_mut($i)}
    };
}

#[cfg(debug_assertions)]
macro_rules! get_mut_unsafe {
    [$a:expr, $i:expr] => {
        *$a.get_mut($i).unwrap()
    };
}

trait Function: std::hash::Hash + Clone + std::cmp::Eq + std::fmt::Debug + std::cmp::Ord {
    const N: usize;

    fn impl_eval(&self, a: usize, b: usize) -> usize;

    #[cfg(debug_assertions)]
    fn eval(&self, a: usize, b: usize) -> usize {
        assert!(
            a < Self::N && b < Self::N,
            "Called eval with a={}, b={} but N={}",
            a,
            b,
            Self::N
        );
        self.impl_eval(a, b)
    }

    #[cfg(not(debug_assertions))]
    fn eval(&self, a: usize, b: usize) -> usize {
        use std::hint::unreachable_unchecked;
        if a >= Self::N || b >= Self::N {
            // I am speed
            unsafe {
                unreachable_unchecked();
            }
        }
        self.impl_eval(a, b)
    }

    fn pass_left() -> Self;
    fn pass_right() -> Self;

    fn compose(&self, left: &Self, right: &Self) -> Self;

    fn unary_compose(&self, left: usize, right: usize) -> usize {
        self.compose(
            &Self::from_unary_index(left),
            &Self::from_unary_index(right),
        )
        .unary_index()
    }

    // Used by fuzzers
    fn random<R: Rng>(rng: &mut R) -> Self;

    // Returns true if should be discarded
    fn low_effort_discard(&self) -> bool {
        for n in 0..Self::N {
            if self.eval(n, n) == n {
                return true;
            }
        }
        false
    }

    // Unique, no holes, for r-unary ops
    fn unary_index(&self) -> usize {
        let mut ret = 0;
        for a in (0..Self::N).rev() {
            ret *= Self::N;
            ret += self.eval(a, a);
        }
        ret
    }

    fn from_unary_index(i: usize) -> Self;

    fn is_unary_complete(&self) -> bool
    where
        [(); Self::N.pow(Self::N as u32)]:,
    {
        // Bruteforce-checks if self is a unary-complete function
        // Keeps track of all the visited nodes and has a queue of functions to add
        // A function is popped from the queue and composed with every previous function, plus itself
        // The new compositions are added to the queue

        // visited is a "Linked list" containing the already visited unary functions
        // 0 - not visited
        // n - visited, next visited in n steps (n is possibly negative)
        // Hack - this list can store BOTH the queue AND the already visited nodes
        let mut visited = [0isize; Self::N.pow(Self::N as u32)];
        let vl = visited.len() as isize;
        let mut start = vl;
        let mut queue;

        let pri = Self::pass_right().unary_index();
        get_mut_unsafe![visited, pri] = vl - pri as isize;
        queue = pri as isize;

        while queue != vl {
            let ui = queue as usize;
            // Pop from queue
            queue += get_unsafe![visited, ui];
            // Redundant, visited[ui] will get overwritten anyway
            // visited[ui] = 0;

            // Start iterating
            let mut ptr = start;
            while ptr != vl {
                let add = [
                    self.unary_compose(ptr as usize, ui as usize),
                    self.unary_compose(ui as usize, ptr as usize),
                ];
                // Push to queue
                for x in add {
                    if get_unsafe![visited, x] == 0 {
                        get_mut_unsafe![visited, x] = queue - x as isize;
                        queue = x as isize;
                    }
                }
                // Next visited function
                ptr += get_unsafe![visited, ptr as usize];
            }
            // Self-composition
            let x = self.unary_compose(ui as usize, ui as usize);
            // Push
            if get_unsafe![visited, x] == 0 {
                get_mut_unsafe![visited, x] = queue - x as isize;
                queue = x as isize;
            }

            // Add self
            get_mut_unsafe![visited, ui] = start - ui as isize;
            start = ui as isize;
        }
        visited.iter().all(|&x| x != 0)
    }

    fn is_functionally_complete(&self) -> bool
    where
        [(); Self::N.pow(Self::N as u32)]:,
    {
        let n = Self::N;
        let unary = self.is_unary_complete();
        if !unary {
            return false;
        }
        // Loneliness
        let mut pass = false;
        'a: for a in 0..n {
            for b in 0..a {
                for c in 0..n {
                    for d in 0..c {
                        let ac = self.eval(a, c);
                        let bc = self.eval(b, c);
                        let ad = self.eval(a, d);
                        let bd = self.eval(b, d);
                        let mut arr = [ac, bc, ad, bd];
                        arr.sort_unstable();
                        if arr[0] != arr[1] || arr[2] != arr[3] {
                            pass = true;
                            break 'a;
                        }
                    }
                }
            }
        }

        if !pass {
            return false;
        }

        // k+1 - completeness
        self.is_k_complete()
    }

    fn is_k_complete(&self) -> bool {
        let n = Self::N;
        let mut counter = vec![0; n];
        let mut k = 2;
        'b: while k < n {
            let cmb: Vec<_> = (0..n).combinations(k).collect();
            for l in &cmb {
                for r in &cmb {
                    for &a in l {
                        for &b in r {
                            counter[self.eval(a, b)] = 1;
                        }
                    }
                    let s = counter.iter().sum();
                    counter.fill(0);
                    if s > k {
                        k = s;
                        continue 'b;
                    }
                }
            }
            return false;
        }
        true
    }

    fn from_index(i: usize) -> Self;
    fn to_index(&self) -> usize;

    // If this function is minimal in it's equivalence class, returns the number of functions in the equivalence class
    // Else returns zero
    fn cifminelse0(&self) -> usize;

    // Pretty prints this gate
    fn pretty_print(&self) {
        println!("Gate i={}", self.to_index());
        let pad = " ";
        let space = " ";
        print!("{}?", pad);
        for b in 0..Self::N {
            print!("{}{}",space,b);
        }
        println!();
        for a in 0..Self::N {
            print!("{}{}", pad, a);
            for b in 0..Self::N {
                print!("{}{}",space,self.eval(a,b));
            }
            println!();
        }
    }
}

// Four bit functions
impl Function for u32 {
    const N: usize = 4;
    fn impl_eval(&self, a: usize, b: usize) -> usize {
        *self as usize >> (a * 4 + b) * 2 & 3
    }

    fn pass_left() -> u32 {
        0xFFAA5500
    }

    fn pass_right() -> u32 {
        0xE4E4E4E4
    }

    fn compose(&self, l: &Self, r: &Self) -> Self {
        let mut ret = 0;
        for a in (0..4).rev() {
            for b in (0..4).rev() {
                ret <<= 2;
                ret |= self.eval(l.eval(a, b), r.eval(a, b));
            }
        }
        ret as u32
    }

    fn random<R: Rng>(rng: &mut R) -> Self {
        rng.gen()
    }

    fn to_index(&self) -> usize {
        *self as usize
    }

    fn from_index(i: usize) -> Self {
        i as u32
    }

    fn unary_index(&self) -> usize {
        *self as usize & 255
    }

    fn from_unary_index(i: usize) -> Self {
        let r = i | (i << 8);
        let r = r | (r << 16);
        r as u32
    }

    fn cifminelse0(&self) -> usize {
        const PERM4: [[usize; 4]; 24] = [
            [0, 1, 2, 3],
            [0, 1, 3, 2],
            [0, 2, 1, 3],
            [0, 2, 3, 1],
            [0, 3, 1, 2],
            [0, 3, 2, 1],
            [1, 0, 2, 3],
            [1, 0, 3, 2],
            [1, 2, 0, 3],
            [1, 2, 3, 0],
            [1, 3, 0, 2],
            [1, 3, 2, 0],
            [2, 0, 1, 3],
            [2, 0, 3, 1],
            [2, 1, 0, 3],
            [2, 1, 3, 0],
            [2, 3, 0, 1],
            [2, 3, 1, 0],
            [3, 0, 1, 2],
            [3, 0, 2, 1],
            [3, 1, 0, 2],
            [3, 1, 2, 0],
            [3, 2, 0, 1],
            [3, 2, 1, 0],
        ];

        fn flipped(f: u32) -> u32 {
            f & 0xc0_30_0c_03
                | f << 6 & 0x30_0c_03_00
                | f << 12 & 0x0c_03_00_00
                | f << 18 & 0x03_00_00_00
                | f >> 6 & 0x00_c0_30_0c
                | f >> 12 & 0x00_00_c0_30
                | f >> 18 & 0x00_00_00_c0
        }

        fn permuted(f: u32, p: &[usize; 4]) -> u32 {
            let mut invp = [0, 0, 0, 0];
            for i in 0..4 {
                invp[p[i]] = i as u32;
            }
            let mut r = 0;
            for a in (0..4).rev() {
                for b in (0..4).rev() {
                    r <<= 2;
                    r |= invp[f.eval(p[a], p[b])];
                }
            }
            r
        }

        let mut m = vec![*self; 48];
        m[1] = flipped(*self);
        if m[1] < *self {
            return 0;
        }
        for (i, p) in PERM4.iter().enumerate().skip(1) {
            m[i * 2] = permuted(*self, p);
            m[i * 2 + 1] = flipped(m[i * 2]);
            if m[i * 2] < *self || m[i * 2 + 1] < *self {
                return 0;
            }
        }
        m.sort_unstable();
        m.dedup();
        m.len()
    }
}

impl<const N: usize> Function for [[usize; N]; N] {
    const N: usize = N;
    fn impl_eval(&self, a: usize, b: usize) -> usize {
        self[a][b]
    }

    fn pass_left() -> Self {
        let mut r = [[0; N]; N];
        for a in 0..N {
            r[a] = [a; N];
        }
        r
    }

    fn pass_right() -> Self {
        let mut d = [0; N];
        for b in 0..N {
            d[b] = b;
        }
        [d; N]
    }

    fn compose(&self, l: &Self, r: &Self) -> Self {
        let mut ret = [[0; N]; N];
        for a in 0..N {
            for b in 0..N {
                ret[a][b] = self.eval(l.eval(a, b), r.eval(a, b));
            }
        }
        ret
    }

    fn random<R: Rng>(rng: &mut R) -> Self {
        let mut r = [[0; N]; N];
        for a in 0..N {
            for b in 0..N {
                r[a][b] = rng.gen_range(0..N);
            }
        }
        r
    }

    fn from_index(mut i: usize) -> Self {
        let mut r = [[0; N]; N];
        for a in 0..N {
            for b in 0..N {
                r[a][b] = i % N;
                i /= N;
            }
        }
        r
    }

    fn to_index(&self) -> usize {
        let mut r = 0;
        for a in (0..N).rev() {
            for b in (0..N).rev() {
                r *= N;
                r += self[a][b];
            }
        }
        r
    }

    fn from_unary_index(mut i: usize) -> Self {
        let mut x = [0; N];
        for n in 0..N {
            x[n] = i % N;
            i /= N;
        }
        [x; N]
    }

    fn cifminelse0(&self) -> usize {
        let flip = |i: &Self| i.compose(&Self::pass_right(), &Self::pass_left());
        let permute_self = |p: &[usize]| {
            let mut inv = [0; N];
            for i in 0..N {
                inv[p[i]] = i;
            }
            let mut ret = [[0; N]; N];
            for a in 0..N {
                for b in 0..N {
                    ret[a][b] = inv[self.eval(p[a], p[b])];
                }
            }
            ret
        };

        let mut m = vec![*self; (1..=N).product::<usize>() * 2];
        m[1] = flip(self);
        if m[1] < *self {
            return 0;
        }
        for (i, p) in (0..N).permutations(N).enumerate().skip(1) {
            m[i * 2] = permute_self(&p);
            m[i * 2 + 1] = flip(&m[i * 2]);
            if m[i * 2] < *self || m[i * 2 + 1] < *self {
                return 0;
            }
        }
        m.sort_unstable();
        m.dedup();
        m.len()
    }
}

#[test]
fn test_pass() {
    fn test_pass_g<F: Function + std::fmt::Debug>() {
        let l = F::pass_left();
        let r = F::pass_right();
        for a in 0..F::N {
            for b in 0..F::N {
                assert_eq!(l.eval(a, b), a, "a is {}, b is {}, l is {:?}", a, b, l);
                assert_eq!(r.eval(a, b), b, "a is {}, b is {}, r is {:?}", a, b, r);
            }
        }
    }
    test_pass_g::<u32>();
    test_pass_g::<[[usize; 3]; 3]>();
    test_pass_g::<[[usize; 4]; 4]>();
}

#[test]
fn test_compose() {
    use rand::rngs::SmallRng;
    use rand::SeedableRng;
    fn test_compose_g<F: Function + std::fmt::Debug>() {
        let mut rng = SmallRng::seed_from_u64(42);
        let repeats = 1_000_000;
        for _ in 0..repeats {
            let f = F::random(&mut rng);
            let l = F::random(&mut rng);
            let r = F::random(&mut rng);
            let c = f.compose(&l, &r);
            let a = rng.gen_range(0..F::N);
            let b = rng.gen_range(0..F::N);
            assert_eq!(
                c.eval(a, b),
                f.eval(l.eval(a, b), r.eval(a, b)),
                "a:{} b:{} f:{:?} l:{:?} r:{:?} c:{:?}",
                a,
                b,
                f,
                l,
                r,
                c
            );
        }
    }
    test_compose_g::<u32>();
    test_compose_g::<[[usize; 3]; 3]>();
    test_compose_g::<[[usize; 4]; 4]>();
}

#[test]
fn test_low_effort_discard() {
    use rand::rngs::SmallRng;
    use rand::SeedableRng;
    fn test_low_effort_discard_g<F: Function + std::fmt::Debug>()
    where
        [(); F::N.pow(F::N as u32)]:,
    {
        let mut rng = SmallRng::seed_from_u64(42);
        let repeats = 1_000;
        for _ in 0..repeats {
            let f = F::random(&mut rng);
            assert!(
                !f.low_effort_discard() || !f.is_functionally_complete(),
                "Discarded f:{:?}",
                f
            );
        }
    }
    test_low_effort_discard_g::<u32>();
    test_low_effort_discard_g::<[[usize; 3]; 3]>();
    test_low_effort_discard_g::<[[usize; 4]; 4]>();
}

#[test]
fn test_specifics() {
    // Using the examples from the blog post + = 0, 0 = 1, 1 = 2
    let triplets = [
        ([[0; 3]; 3], false),
        ([[1; 3]; 3], false),
        ([[2; 3]; 3], false),
        ([[0, 1, 2]; 3], false),
        ([[0; 3], [1; 3], [2; 3]], false),
        ([[0, 1, 2], [1, 1, 2], [2, 2, 2]], false), // Min
        ([[0, 1, 2], [0, 1, 1], [0, 0, 0]], false), // Imp
        ([[0; 3], [1; 3], [0; 3]], false),          // Imp composition
        ([[2, 0, 0], [0, 0, 0], [0, 0, 1]], true),  // Tand
        ([[2, 1, 1], [1, 0, 1], [1, 1, 1]], true),  // Modified Tand
        ([[2, 2, 2], [2, 0, 2], [2, 2, 1]], true),  // Modified Tand
        ([[1, 0, 0], [0, 2, 0], [0, 0, 0]], true),  // Modified Tand
        ([[1, 1, 1], [1, 2, 1], [1, 1, 0]], true),  // Modified Tand
        ([[1, 2, 2], [2, 2, 2], [2, 2, 0]], true),  // Modified Tand
        ([[2, 0, 1], [0, 0, 0], [1, 0, 1]], true),  // Pointy Tand
        // Experimentally found
        ([[0, 2, 0], [0, 0, 0], [0, 0, 0]], false),
        ([[1, 2, 0], [0, 0, 0], [0, 0, 0]], true),
        // From the post
        ([[2, 0, 1], [0, 0, 0], [2, 2, 0]], true),
        ([[2, 0, 1], [1, 0, 0], [2, 2, 0]], true),
        ([[2, 0, 1], [2, 0, 0], [2, 2, 0]], true),
        ([[1, 0, 0], [1, 0, 2], [2, 2, 1]], false),
    ];
    for (f, r) in triplets {
        println!("{:?} -> {}", f, r);
        assert_eq!(f.is_functionally_complete(), r);
    }
}

fn smart_method<F: Function>()
where
    [(); F::N.pow(F::N as u32)]:,
{
    let amount = F::N.pow(F::N as u32 * F::N as u32);
    (0..amount).into_par_iter().for_each(|i| {
        let n = F::from_index(i);
        let m = n.cifminelse0();
        if m == 0 {
            return;
        }
        let r = n.low_effort_discard() || !n.is_functionally_complete();
        if !r {
            TC.fetch_add(m, Relaxed);
        } else {
            FC.fetch_add(m, Relaxed);
        }
    });
    CONT.store(false, Release);
}

static TC: AtomicUsize = AtomicUsize::new(0);
static FC: AtomicUsize = AtomicUsize::new(0);
static CONT: AtomicBool = AtomicBool::new(true);

// Change this to [[usize;3];3] for n=3
type T = u32;

fn main() {
    // Fluff
    let start = std::time::Instant::now();
    let amount = T::N.pow(T::N as u32 * T::N as u32);
    let pb = ProgressBar::new(amount as u64);
    pb.set_style(
        ProgressStyle::default_bar().template(
            "{wide_bar:.green/red}\n{pos}/{len} - {percent}% - {per_sec} - {eta} - {msg}",
        ),
    );
    let t = thread::spawn(move || {
        while CONT.load(Acquire) {
            thread::sleep(std::time::Duration::from_millis(100));
            let t = TC.load(Relaxed);
            let f = FC.load(Relaxed);
            pb.set_position(t as u64 + f as u64);
            pb.set_message(format!(
                "Ratio at {}/{} = {:.5}",
                t,
                t + f,
                t as f64 / (t as f64 + f as f64)
            ));
            pb.tick();
        }
    });
    // Call
    smart_method::<T>();
    // Fluff
    match t.join() {
        Err(_e) => {
            println!("Failed to join ui-thread :/");
        }
        _ => {}
    };
    let t = TC.load(Relaxed);
    let f = FC.load(Relaxed);
    println!(
        "Ended with {} universal gates and {} non-universal gates. Ratio is {}/{} = {:.5}",
        t,
        f,
        t,
        t + f,
        t as f64 / (t as f64 + f as f64)
    );
    println!("Took {:?}", start.elapsed());
    // Remember to reset TC, FC and CONT if you want to call again
}

```

## cargo.toml

```
[dependencies]
itertools = "0.10"
rand = {version="0.8", features=["small_rng"]}
rayon = "1.5"
indicatif = {version = "0.16", features = ["rayon"]}

```

Takes around 20 minutes on my machine™. The actual code is not that interesting, maybe with the exception of the unary completeness check, which uses a buffer with two non-overlapping linked lists, to form a very efficient deduplicated queue + set data structure.

# n=5?

For `n=5` you basically need a new idea (or a lot of computing power). Checking each gate individually becomes impractical (if you could do it in one cycle, it would still take two years). If someone manages to calculate `n=5`, I'm happy to forward Bubblers +500 bounty to them.
> 24 votes

# Answer
# Python, 1648 bytes

```
lambda n:(K:=G(n))and n**(n*n)-sum(U([O({((x,y),):C(K)if x!=y else[(B[x],)]for x,y in W(K,K)},j)for j in[{((x,y),):C(S)for x,y in W(S,S)}for j in G(1,n)for S in combinations(K,j)]+[{Z(W(X,V)):sum(([*W(*[S]*len(X)*len(V))]for S in P if not S==X==V),[])for X,V in W(P,P)}for P in R(K)if 1<len(P)<n]+sum(([{Z(zip(X,V[i:]+V[:i])):[S[i:]+S[:i]for S in P for i in G(p)]for X,V,i in W(P,P,G(p))}for P in R(K)if set(map(len,P))=={p}]for p in G(2,n+1)if n%p<1),[])])for B in W(*[K]*n))or 1
from itertools import*
import math
from collections import*
W=product
Z=tuple
H=Counter
G=range
def T(l):
	d={(i,):C(c)for i in G(len(l[0]))if{*H(x[:i]+x[i+1:]for x in l).values()}=={len((c:=H(x[i]for x in l)))}!=2>len({*c.values()})};r=Z({*G(len(l[0]))}-{*sum(d,())})
	if r:d[r]=[*{Z(x[i]for i in r)for x in l}]
	return d
E=lambda s:math.prod(map(len,s.values()))
C=lambda l:[(i,)for i in l]
def O(s,o):
	q={i:[dict(zip(I,l))for l in s[I]]for I in s for i in I};D={}
	for I in o:
		d=[dict(zip(I,l))for l in o[I]];S=set()
		for i in I:S|={*q[i][0]};d=[h for a,b in W(d,q[i])for h in[a|{}]if all(b[j]==h.setdefault(j,b[j])for j in b)]
		for i in S:q[i]=d
	for d in q.values():
		if[]==d:return{Z(q):d}
		t=Z(sorted(d[0]));D[t]=[Z(l[j]for j in t)for l in d]
	for i in[*D]:
		if d:=T(D[i]):D.pop(i);D|={Z(i[k]for k in j):d[j]for j in d}
	return D
def M(l):
	if l:
		for a,b in M(l[1:]):yield(l[0],)+a,b;yield a,(l[0],)+b
	else:yield(),()
R=lambda l:[(a+(l[0],),*t)for(a,b)in M(l[1:])for t in R(b)]if l else[()]
def U(L):
	L=[s for s in L if E(s)]
	if[]==L:return 0
	x=L[0];L2=[];L1=[]
	for i in L:
		if i!=x!=E((j:=O(i,x)))<E(i):L1+=[i];L2+=[j]
	return E(x)+U(L1)-U(L2)

```

Attempt This Online! (only up to n=4)

Golfed version of my code for `n=5`.

# Explanation

This algorithm relies almost entirely on the fundamental theorem from the paper mentioned in the comments: On n-Valued Sheffer Functions by Roy O. Davies.

The fundamental theorem lists three conditions that are both sufficient and necessary for a given n-ary logic gate to be complete.

Let \\$U=\\{1,2,...,n\\}\\$

A function \\$f:U\times U\rightarrow U\\$ is complete if and only if none of the following hold:

* There exists a nonempty set \\$S\subsetneq U\\$ such that for all \\$x,y\in S\\$, \\$f(x,y)\in S\\$ (e.g. if `f(0,0)==0` then `f` must be incomplete)
* There exists a nontrivial equivalence relation on \\$U\\$ where if \\$x\_1\sim x\_2\\$ and \\$y\_1\sim y\_2\\$, then \\$f(x\_1,y\_1)\sim f(x\_2,y\_2)\\$ (that is, you can view \\$f\\$ as acting on the equivalence classes). (Here an equivalence relation is trivial if \\$a\\$ and \\$b\\$ are either always related, or related only when \\$a=b\\$).
* There exists a permutation \\$\pi\\$ on \\$U\\$ consisting of \\$\frac{n}{p}\\$ cycles where \\$p\\$ is a prime factor of \\$n\\$ such that for all \\$x,y\in U\\$: \\$\pi(f(x,y))=f(\pi(x),\pi(y))\\$. (For example, if \\$(a,b,c)\\$ is a cycle and \\$(x,y,z)\\$ is a cycle, then \\$(f(a,x), f(b,y), f(c,z))\\$ is a cycle)

So we can count the number of complete gates by counting the number of incomplete gates and subtracting that from the total number of gates. The number of incomplete gates can be calculated by considering each reason a gate could be incomplete individually and then combining the results using inclusion-exclusion.

For example, consider the set of gates that fail the first test where \\$n=4\\$ and \\$S=\\{0,1\\}\\$. It's pretty easy to see that \\$f(0,0), f(0,1), f(1,0), f(1,1)\\$ each have 2 choices (0 and 1), and the other 12 outputs have 4 choices each.

The other two cases are a little more complicated because values are no longer independent, so the representation I settled on is to partition \\$U\times U\\$ into pairwise disjoint sets \\$S\_i\\$, and for each such set list the outputs that the whole set can take.

The set of gates where \\$f(0,0)=f(1,1)\\$ would be represented by

* \\$(f(0,0),f(1,1))\in\\{(0,0),(1,1),(2,2),(3,3)\\}\\$
* \\$f(0,1)\in U\\$
* \\$f(0,2)\in U\\$
* ...

With this representation, calculating the size of the set is easy, finding the intersection of two sets is relatively easy (the number of options can easily blow up, so the code tries to compress the representation when possible), and the rest of the cases can be represented.

There is one other major optimization as well:

If we fix \\$f(i,i)\\$ for \\$i\in U\\$ then the number of cases to consider is dramatically reduced (which is helpful because PIE is exponential in the number of cases) at the cost of having \\$n^n\\$ disjoint cases. Moreover, if you consider the directed graph induced by \\$f(i,i)\\$, isomorphic graphs correspond to the same number of complete gates, reducing the amount of work for \\$n=5\\$ by nearly 250 times! In fact, for \\$n=5\\$ it actually also fixes \\$f(0,1)\\$ which fixes one very slow case. (this optimization (among others) is removed in the golfed code).

Full code:

```
import itertools
from collections import Counter

def length(x):
    # counts the number of functions in the set
    z = 1
    for i in x.values():
        z *= len(i)
    return z

def intersect(A, B):
    # finds the intersection of two sets
    q = {}
    for I, L in A.items():
        d = [dict(zip(I,l)) for l in L]
        for i in I:
            q[i] = d
    for I, L in B.items():
        d = [dict(zip(I,l)) for l in L]
        seen = set()
        for i in I:
            d1 = q[i]
            if len(d1) == 0: return {tuple(q):[]}
            if min(d1[0]) in seen: continue
            seen.update(d1[0])
            d2 = []
            for a in d:
                for b in d1:
                    h = a.copy()
                    for j, k in b.items():
                        if h.setdefault(j, k) != k:
                            break
                    else:
                        d2.append(h)
            d = d2
            if len(d) == 0: return {tuple(q):[]}
        for i in seen:
            q[i] = d
    D = {}
    for i, d in q.items():
        if len(d) == 0:
            return {tuple(q):[]}
        elif i == min(d[0]):
            t = tuple(sorted(d[0]))
            D[t] = [tuple(l[j] for j in t) for l in d]
    return simplify(D)

def simplify(self):
    # simplifies the set representation
    if length(self) == 0:
        self = {(j,):[] for i in self for j in i}
    else:
        l0 = length(self)
        for i in list(self):
            l = self[i]
            d = split_up(l)
            if len(d) > 1:
                for j, o in d.items():
                    self[tuple(i[k] for k in j)] = o
                self.pop(i)
        assert l0 == length(self)
    return self

def split_up(l):
    # helps to simplify a list of assignments
    # e.g. [(0,0),(0,1),(0,2),(1,0),(1,1),(1,2)] can be expressed as (0,1)x(0,1,2)
    d = {}
    for i in range(len(l[0])):
        c = Counter(x[i] for x in l)
        if len(set(c.values())) == 1:
            q = Counter(x[:i]+x[i+1:] for x in l)
            if set(q.values()) == {len(c)}:
                d[i,] = [(j,) for j in c]
    remaining = tuple(set(range(len(l[0])))-set(sum(d,())))
    if remaining:
        d[remaining] = list({tuple(x[i] for i in remaining) for x in l})
    return d

def basic(l):
    # returns the representation for the set of functions f where f(i,i) = l[i]
    r = range(len(l))
    a = [(i,) for i in r]
    return {((x,y),):a if x != y else [(l[x],)] for x in r for y in r}

def nonempty_proper_subsets(l):
    for i in range(1, len(l)):
        yield from itertools.combinations(l, i)

def splits(l):
    if len(l) == 0:
        yield (), ()
        return
    x, *l1 = l
    for a,b in splits(l1):
        yield (x,)+a, b
        yield a, (x,)+b

def partitions(l):
    if len(l) == 0:
        yield ()
        return
    x, *l1 = l
    for a, b in splits(l1):
        a += (x,)
        for t in partitions(b):
            yield (a,) + t

def special_permutations(n, p):
    for P in partitions(list(range(n))):
        if set(map(len, P)) == {p}:
            d = {}
            options = [S[i:]+S[:i] for S in P for i in range(p)]
            for S1 in P:
                for S2_ in P:
                    for i in range(p):
                        S2 = S2_[i:] + S2_[:i]
                        d[tuple(zip(S1, S2))] = options
            yield d

def factors(n):
    p = 2
    s = set()
    while n > 1:
        if n%p == 0:
            s.add(p)
            n //= p
            while n%p == 0:
                n //= p
        p += 1 + p%2
    return s

def canonize_(l, d, r1, r2):
    options = []
    len0 = len(d)
    r = r1 or r2
    if len(r) == 0:
        return ()
    for i in r:
        while i not in d:
            d.append(i)
            i = l[i]
        p = (len(d)-len0, d.index(i))
        options.append(p + canonize_(l, d,
            [j for j in r1 if j not in d],
            [j for j in r2 if j not in d]
        ))
        while len(d) > len0: d.pop()
    return max(options)

def canonize(l):
    r2 = set(l)
    r1 = set(range(len(l))) - r2
    return canonize_(l, [], r1, r2)

def union_length(L):
    L = [s for s in L if length(s) > 0]
    if len(L) == 0: return 0
    x = max(L, key=length)
    L2 = []
    L1 = []
    for i in L:
        if i is not x:
            ix = intersect(i,x)
            if length(ix) < length(i):
                L1.append(i)
                L2.append(ix)
    return length(x) + union_length(L1) - union_length(L2)

def magic(n):
    if n == 1: return 1
    l = list(range(n))
    Z = []
    for S in nonempty_proper_subsets(l):
        allowed = [(i,) for i in S]
        Z.append({
            ((x, y),): allowed
                for x in S
                for y in S
        })
    for P in partitions(l):
        if len(P) == n: continue
        if len(P) == 1: continue
        options = {}
        d = {}
        for S1 in P:
            for S2 in P:
                if S1 is S2:
                    option = []
                    for S in P:
                        if S is S1: continue
                        option.extend(itertools.product(S, repeat=len(S1)*len(S1)))
                    d[tuple(itertools.product(S1, S1))] = option
                else:
                    ab = len(S1) * len(S2)
                    if ab not in options:
                        option = []
                        for S in P:
                            option.extend(itertools.product(S, repeat=ab))
                        options[ab] = option
                    d[tuple(itertools.product(S1, S2))] = options[ab]
        Z.append(d)
    for p in factors(n):
        Z.extend(special_permutations(n, p))
    if True:
        cache = {}
        out = 0
        for ll in itertools.product(range(n), repeat=n):
            if any(i==j for i,j in enumerate(ll)): continue
            c = canonize(ll)
            if c in cache:
                out += cache[c]
            else:
                standard = basic(ll)
                q = 0
                rs = max(n-4, 0)
                for t in itertools.product(range(n), repeat=rs):
                    x = standard
                    if rs:
                        x = intersect(x, {
                            ((0,i+1),):[(t[i],)]
                            for i in range(rs)
                        })
                    q += length(x) - union_length([intersect(x,i) for i in Z])
                cache[c] = q
                out += q
        return out

for i in [1,2,3,4,5]:
    print(magic(i))

```

Attempt This Online! (takes about a minute for n=5)

As an aside (also from the paper), another sufficient and necessary condition for completeness is if for each distinct \\$a,b,c\in U\\$, \\$f\\$ generates a function \\$g:U\rightarrow U\\$ such that \\$f(a)=a\\$ and \\$f(b)=c\\$, which means that unary completeness implies completeness.
> 8 votes

# Answer
# JavaScript (Node.js), 194 bytes

```
f=(n,c=[],k=0)=>k-n?1/c[n*n]?(F=>g=s=>s[n**n*8]?eval(`try{for(A=n;A--;)for(B=n;B--;)eval(s)+~(A<B?A:B)%n&&G;1}catch{}`):[...'AB()F'].some(_=>g(s+_)))(t=>u=>c[t*n+u])``:f(n,c,k+1)+f(n,[...c,k]):0

```

Try it online!

If a function can express `f(x,y)=max(x,y)+1`, then it's universal:

* `f(x,x)=x+1`, therefore we can get `x+c` for any `c`
* `max(x,x+1,...,x+n-2)` is `n-1`, unless `x` is zero where the result is `n-2`
* `max(x,max(a,a+1,...,a+n-2,b,b+1,...,b+n-2)+1)` is `x` if either `a` or `b` is not 0, and `n+1` if `a` and `b` are both 0
* Set the value using this

The `eval` never meet a function that can't fit the exact length:

* The expression built with `AB()F` is always of odd length (`F(A)(B)`)
* One can write `A` as `((((A))))` to use even spaces
> 2 votes

---
Tags: code-golf, sequence, combinatorics, logic-gates
---


title: Print ASCII building

text:
# Question
Title: Print ASCII building
## Challenge

Display to the screen or write to stdout this exactly:

```
    **
    **
   ****
   ****
   ****
   ****
   ****
   ****
   ****
**********
**********
**********

```

# Winning

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

# Answer
# Python 3, 47 bytes

```
for n in b"":print(f"{'**'*n:^10}")

```

Try it online!

Yawn, bytestrings. I got close with a few other approaches:

**48 bytes**

```
for n in[2]*2+[4]*7+[10]*3:print(f"{'*'*n:^10}")

```

Try it online!

**48 bytes**

```
for n in[1]*2+[2]*7+[5]*3:print(-n%5*' '+'**'*n)

```

Try it online!

This code is 46 bytes in Python 2 where `print` doesn't need parens. Thanks to dingledooper for -1 byte with `-n%5`.

**49 bytes**

```
print("    **\n"*2+"   ****\n"*7+('*'*10+'\n')*3)

```

Try it online!

**50 bytes**

```
n=15
while n-3:print(f"{(5>>n//7)*'**':^10}");n-=1

```

Try it online!
> 13 votes

# Answer
# CP-1610 machine code, 47 DECLEs1 = 58.75 bytes

*1. CP-1610 instructions are encoded with 10-bit values (0x000 to 0x3FF), known as DECLEs. Although the Intellivision is also able to work on 16-bit, programs were really stored in 10-bit ROM back then.*

A full program in 10-bit ROM format, mapped at $4800. This includes an initialization of the video chip so that the display is correct.

```
                            ROMW    10          ; use 10-bit ROM
                            ORG     $4800       ; map our program at $4800

4800  0002                  EIS                 ; enable interrupts

4801  0001                  SDBD                ; R4 = data pointer
4802  02BC 002B 0048        MVII    #data,  R4
4805  02BD 0200             MVII    #$200,  R5  ; R5 = BACKTAB pointer

4807  02A0            loop  MVI@    R4,     R0  ; load data word into R0
4808  0080                  TSTR    R0          ; if it's zero ...
4809  0204 001A             BEQ     done        ; ... exit

480B  0081                  MOVR    R0,     R1  ; copy R0 to R1
480C  03B9 0007             ANDI    #7,     R1  ; isolate the 3 least significant bits

480E  0275            line  PSHR    R5          ; save R5 on the stack
480F  0082                  MOVR    R0,     R2  ; copy R0 to R2
4810  0066                  SLR     R2,     2   ; right-shift R2 by 3 positions
4811  0062                  SLR     R2
4812  03BA 0007             ANDI    #7,     R2  ; isolate the 3 least significant bits
4814  00D5                  ADDR    R2,     R5  ; add that to R5
4815  0083                  MOVR    R0,     R3  ; copy R0 to R3
4816  02BA 0057             MVII    #$0057, R2  ; load the value of a white '*' in R2

4818  026A            char  MVO@    R2,     R5  ; write the character
4819  033B 0040             SUBI    #$40,   R3  ; subtract 64 from R3
481B  0223 0004             BPL     char        ; keep drawing while it's positive

481D  02B5                  PULR    R5          ; restore R5
481E  02FD 0014             ADDI    #20,    R5  ; advance to the next line

4820  0011                  DECR    R1          ; decrement R1
4821  022C 0014             BNEQ    line        ; draw another line if it's not zero
4823  0220 001D             B       loop        ; or process the next value

4825  02BD 0030       done  MVII    #$30,   R5  ; R5 = pointer into STIC registers
4827  0268                  MVO@    R0,     R5  ; no horizontal delay
4828  0268                  MVO@    R0,     R5  ; no vertical delay
4829  0268                  MVO@    R0,     R5  ; no border extension

482A  0017            spin  DECR    R7          ; loop forever

482B  0062            data  DECLE   $062        ; data format: WWWWPPPNNN
482C  00DF                  DECLE   $0DF        ; W = width - 1
482D  0243                  DECLE   $243        ; P = left padding
482E  0000                  DECLE   0           ; N = number of lines

```

## Output

*made with jzIntv*
> 10 votes

# Answer
# Haskell, ~~81~~ ~~72~~ 60 bytes

```
unlines[(' '<$['1'..a])++("**"<*[a..'9'])|a<-"998888888555"]

```

Attempt This Online!

-9 bytes thanks to Unrelated String

-9 byte thanks to ovs

Uses the range syntax \[a..'9'\] to do substraction.
> 7 votes

# Answer
# Perl 5, 42 bytes

```
say$"x(5-$_/2),'*'x$_ for 2,2,(4)x7,(10)x3

```

Try it online!
> 6 votes

# Answer
# ///, ~~60~~ ~~54~~ ~~51~~ ~~48~~ ~~47~~ 46 bytes

```
/a/**//s/   a//w/
aaaaa//b/
sa/ s
 sbbbbbbbwww

```

Try it online!

-1 byte thanks to @Philippos
> 5 votes

# Answer
# sed, 45 bytes

Quite straight forward, with some optimisations:

* starting with 3 trailing spaces, which can later be turned into `*`
* of course using the `p` flag for saving one byte
* `s/ /**/4` to simply replace one space by two `*`
* `h;H;G` to produce three identical lines

```
s/^/    **   /p;p
s/ /**/4p;h;H;G;p;p
s/ /*/g

```

Try it online!
> 5 votes

# Answer
# Zsh, 65 bytes

```
repeat 2 <<<'    **'
repeat 7 <<<'   ****'
repeat 3 <<<**********

```

Try it online!

It's pretty basic, clever tricks like left-padding *`l:expr::string1:`* didn't help.
> 5 votes

# Answer
# Python 3.11 (~~69~~ 67 bytes ~~nice~~)

```
print(''.join(map(lambda a,c:f"{'*'*a:^10}\n"*c,(2,4,10),(2,7,3))))

```

removed parentheses around fstring thanks to @corvus\_192
> 4 votes

# Answer
# Vyxal, 97 bitsv2, 12.125 bytes

```
»ƛ⁼c»yøḊ×v*øm

```

Try it Online!

Bitstring:

```
0000111111001110001100010001100001000110001001001010100111011011101111010100110110101111000100100

```

**Explanation**:

```
»ƛ⁼c»yøḊ×v*øm
»ƛ⁼c»          Decompresses integer => 122753
     yøḊ       Interleave, Run-length decoding => [1,1,2,2,2,2,2,2,2,5,5,5]
        ×v*    Map repeat asterisk n times
           øm  Palindromise, center and join by newlines

```

The more trivial answer `»ɽβ≬ǓG»f×v*øm` has a higher vyncode score (probably because the compressed part is longer).
> 4 votes

# Answer
# JavaScript (V8), 59 bytes

*-5 thanks to @l4m2*

```
for(n of"443333333000")print("".padEnd(n).padEnd(10-n,"*"))

```

Try it online!
> 4 votes

# Answer
# Charcoal, 14 bytes

```
↑Ｅ333ac×*⍘ιφ‖Ｃ

```

Try it online! Link is to verbose version of code. Explanation:

```
↑Ｅ333ac×*⍘ιφ

```

Output the first five columns of the figure, whose heights are the hexadecimal digits `333ac`, starting at the bottom working up.

```
‖Ｃ

```

Make a mirror copy to complete the figure.
> 4 votes

# Answer
# Japt `-R`, 17 bytes

```
#p#Þ#Þ555ì Ëç*²Ãû

```

Test it

```
#p#Þ#Þ555ì Ëç*²Ãû
#p#Þ#Þ555             :Compressed integer 112222222555
         ì            :To digit array
           Ë          :Map
            ç         :  Repeat
             *²       :    "*" duplicated
               Ã      :End map
                û     :Centre pad with spaces to the length of the longest
                      :Implicit output joined with newlines

```
> 4 votes

# Answer
# MathGolf, 13 bytes

```
2_4··♂∙]⌂*♂Ωn

```

Try it online.

**Explanation:**

```
2             # Push 2
 _            # Duplicate it
  4           # Push 4
   ··         # Quadruplicate it twice
     ♂        # Push 10
      ∙       # Triplicate it
       ]      # Wrap all values on the stack into a list: [2,2,4,4,4,4,4,4,4,10,10,10]
        ⌂*    # Convert each to strings with that many "*"
          ♂Ω  # Centralize the strings to length 10
            n # Join the list of padded strings by newlines
              # (after which the entire stack is output implicitly as result)

```
> 4 votes

# Answer
# 6510-Assembler for C64, 42 bytes

```
*=$c000
  ldy #23
  lda #32
w ldx data,y
q jsr $ffd2
  dex
  bpl q
  eor #10
  dey
  bpl w
  rts

data
!byte 9,29,9,29,9,32,3,35,3,35,3,35,3,35,3,35,3,35,3,36,1,37,1,3

```
> 4 votes

# Answer
# ARBLE, 47 bytes

```
explode"112222222555"|rep(" ",5-x)..rep("**",x)

```

Relatively self explanatory, explodes the string `112222222555` into a list of single characters, each of which represents half the width of the building as it goes down. Then, maps over that list, replacing each entry with a string of `5-x` spaces, and `2*x` asterisks, which effectively rebuilds it.

Try it online!
> 3 votes

# Answer
# Scratch, 134 bytes

**NOTE: This code assumes that `x` is already displayed. To see the full \*STDOUT\* as it is, you should drag the list to the full screen.**

Direct solution. Had to add some spaces so it would align up nicely because when Scratch displays lists, line numbers are displayed *and* modify the position of their corresponding item.

Alternatively, 0 bytes

```
define
delete[all v]of[x v
add[       **]to[x v
add[       **]to[x v
repeat(7
add[      ****]to[x v
end
repeat(3
add[**********]to[x v

```

A joke about line lengths
> 3 votes

# Answer
# APL+WIN, ~~52~~ ~~33~~, 31 bytes

19 bytes saved thanks to Jonah. 2 bytes more by switching from index origin 1 to 0

```
'* '[2 7 3⌿⊃(⊂10⍴2)⊤¨975 903 0]

```

Try it online! Thanks to Dyalog Classic

Original code:

```
m←12 5⍴' '⋄((∊10 35 15⍴¨(⊂5⍴2)⊤¨1 3 31)/,m)←'#'⋄m,⌽m

```
> 3 votes

# Answer
# C# (.NET 4.7.2), 92 90 87 88 bytes

```
foreach(var x in "443333333000")Console.WriteLine("".PadRight(x-48).PadRight(58-x,'*'));

```

Edit: @corvus\_192 pointed out that using 48 instead of '0' would save a few chars. Thanks!

Implementation of Arnauld's JS version: https://codegolf.stackexchange.com/a/266751/120291
> 3 votes

# Answer
# Commodore BASIC V2 or compatible interpreter (Most notably the Commodore C64 or C128) - non-competing/just for fun - 106 tokenised BASIC bytes

```
0reada,b,c:s=1:on-(a<.)goto2:forx=1toc:ifsthen?spc(a);:s=.
1fory=1tob:?"**";:next:?:s=1:next:goto
2data4,1,2,3,2,7,0,5,3,-1,,

```

Here it is in action:

I will add a better explanation later, but for those who maybe are unfamiliar with Commodore BASIC, here is a more readable listing of broadly the same outcome that I made in order to work out the logic before I minimised and crunched the BASIC listing into the three lines in this entry:
> 3 votes

# Answer
# PowerShell, 64 bytes (Thanks Julian!)

```
4,4,(,3*7),0,0,0|%{$_}|%{""|% *ht($_-'0')|% *ht(10-($_-'0'))'*'}

```

Try it online!

~~\# PowerShell, 85 bytes~~

~~```
foreach($n in 4,4,3,3,3,3,3,3,3,0,0,0){"".PadRight($n-'0').PadRight(10-($n-'0'),'*')}

```
Try it online!
\# PowerShell, 64 bytes
```
foreach($n in $c){"".PadRight($n-'0').PadRight(10-($n-'0'),'*')}

```
Try it online!
~~

Thanks to @lost\_in\_a\_musical\_note's answer for laying the groundwork!
> 3 votes

# Answer
# brainfuck, 107 bytes

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

```

Try it online!
> 3 votes

# Answer
# , 25 bytes

```
'* '{~2 7 3#:@#975,903,0:

```

Try it online!

This just encodes the full rows as binary numbers, then duplicates them according to the 2 7 3 frequency. This results in a 12 by 10 binary matrix, which is converted to ascii.

I didn't find a way to exploit the symmetry in a way that beats this.
> 2 votes

# Answer
# Google Sheets, ~~88~~ ~~80~~ ~~79~~ 75 bytes

```
=let(c,"**",n,"**
",e,"    "&n,f,"   "&c&n,g,c&c&c&c&n,e&e&rept(f,7)&g&g&g)

```

Put the formula in cell `A1`. It uses simple string concatenation. The whole output is displayed in that one cell.

The text string in `n` is two asterisks followed by a newline. A literal newline can be specified this way in Google Sheets, saving nine bytes over `"&char(10)&"`.

Structured version (80 bytes):

```
=map({2;7;3},{4;3;0},{2;4;10},lambda(n,s,a,rept(rept(" ",s)&rept("*",a)&"
",n)))

```

The output is shown in `A1:A3`, with newlines in cells. The text string between `&"` and `",n"` is a newline.
> 2 votes

# Answer
# Retina 0.8.2, 48 bytes

```

42¶423333333111
3
¶34
1
¶010
(.)(.+)
$1$* $2$**

```

Try it online! Explanation:

```

42¶4233333111

```

Start with the encoding for the first two lines plus an encoded encoding for the remaining lines.

```
3
¶34
1
¶010

```

Decode the encoding for the remaining lines. All lines are now singly encoded.

```
(.)(.+)
$1$* $2$**

```

Decode the encoding for each line (first digit is number of spaces, other digit(s) is number of asterisks).
> 2 votes

# Answer
# RProgN 2, 22 bytes

```
00079){3+`**}rT{.]i.};

```

## Explanation

```
00079){3+`**}rT{.]i.};
00079)                 # A Stack of the numbers 0, 0, 0, 7, 9 (Each 3 less than the height of half the columns)
      {     }r         # Replace each number with
       3+              # +3
         `**           # Multiply by "*" (Which repeats "*" x times)
              T        # Transpose
               {    }; # For each row
                .]     # Concatenate back into a string and duplicate
                  i.   # Inverse the duplicate and concatenate, palindromizing
                       # Implicit output the contents of the stack.

```

Try it online!
> 2 votes

# Answer
# 05AB1E, ~~16~~ 14 bytes

```
2Dx7.DTÐ)'*×.c

```

Try it online.

**Explanation:**

```
2              # Push 2
               #  Stack: 2
 D             # Duplicate it
               #  Stack: 2,2
  x            # Double it (without popping)
               #  Stack: 2,2,4
   7           # Push 7
               #  Stack: 2,2,4,7
    .D         # Duplicate the 4 7 times
               #  Stack: 2,2,4,4,4,4,4,4,4
      T        # Push 10
               #  Stack: 2,2,4,4,4,4,4,4,4,10
       Ð       # Triplicate it
               #  Stack: 2,2,4,4,4,4,4,4,4,10,10,10
        )      # Wrap everything on the stack into a list
               #  Stack: [2,2,4,4,4,4,4,4,4,10,10,10]
         '*×  '# Convert each to a string of that many "*"
               #  Stack: ["**","**","****","****",...,"**********"]
            .c # Join by newlines and pad leading spaces to centralize the lines
               #  Stack: "    **\n    **\n   ****\n...\n**********"
               # (after which the result is output implicitly)

```
> 2 votes

# Answer
# Uiua 0.2.0, 28 bytes, 22 characters

```
+@ ×10⋯▽2_7_3-@\0"0xϿ"

```

See it in action
> 2 votes

# Answer
# *Acc!!*, 85 bytes

```
Count i while i-132 {
Write 32+10*0^((i%11*2-9)^2/(((i/11+5)/7)^2*20+2))-i%11/10*22
}

```

Try it online!

### Explanation

Let's start with this 99-byte version:

```
Count r while r-12 {
Count c while c-10 {
Write 32+10*0^((c*2-9)^2/(((r+5)/7)^2*20+2))
}
Write 10
}

```

We have a straightforward nested loop over 12 rows `r` and 10 columns `c`, with a newline written at the end of each row. The math to determine space or asterisk runs as follows:

We want to transform the column numbers such that inner columns map to a smaller value than outer columns; then, for each row, we can apply a cutoff so the inner columns become one character and the outer columns become a different character. *Acc!!* doesn't have an absolute value operator, so we'll use squaring. To preserve symmetry, we double the column number and subtract an odd constant: `(c*2-9)^2`

```
c  c*2-9  (c*2-9)^2
0  -9     81
1  -7     49
2  -5     25
3  -3     9
4  -1     1
5   1     1
6   3     9
9   9     81

```

The column cutoff is also dependent on the row number:

* Rows 0-1: cutoff between 1 and 9
* Rows 2-8: cutoff between 9 and 25
* Rows 9-11: cutoff above 81

First, we shift and int-divide the row numbers to quantize them into the correct chunks:

```
r     (r+5)/7
0-1   0
2-8   1
9-11  2

```

Now a linear function doesn't put the cutoffs in the right range, but a quadratic function does:

```
(r+5)/7  ((r+5)/7)^2*20+2
0        2
1        22
2        82

```

Next, we need to check whether the modified column value is greater than or less than the cutoff. We can do this using int division. But that results in different non-zero values, which isn't good for the ASCII-code math we're going to do. We can convert them to 0 and 1 by exploiting the fact that 0^0 = 1 and 0^x = 0 for any positive x in *Acc!!*.

```
col  cutoff  col/cutoff  0^(col/cutoff)
1    2       0           1
9    2       4           0
25   2       12          0
1    22      0           1
9    22      0           1
25   22      1           0
1    82      0           1
9    82      0           1
25   82      0           1

```

We then multiply that quantity by 10 and add 32, turning 0 into 32 (space) and 1 into 42 (asterisk), and write out the appropriate character.

---

To get from the 99-byte version to the 85-byte version, we first move the newline-printing into the nested loop. We add an 11th column, which according to the existing math would always be a space (ASCII 32); then we subtract 22 if the column index is \>= 10, turning that space into a newline (ASCII 10).

```
... while c-11 {
Write ... - c/10*22

```

Now we can combine the two loops into a single loop whose index `i` runs from 0 to 131. The row number `r` is simply `i/11`, and the column number `c` is `i%11`.
> 2 votes

# Answer
# K (ngn/k), 28 bytes

```
" #"@+&'(12-)\'10\9992002999

```

Try it online!
> 2 votes

# Answer
# PowerShell Core, 36 bytes

```
,"    **"*2
,"   ****"*7
,("*"*10)*3

```

Try it online!

```
,"    **"*2    # Creates an array ("   **", "   **") print it on stdout
,"   ****"*7   # Same as above
,("*"*10)*3    # Builds and string of 10 stars, then same as above

```
> 2 votes

# Answer
# COMMODORE 64 & MSX BASIC - Solution as a one-liner, 80 Bytes

```
0 DATA4,2,2,3,4,7,,10,3:READA,B,C:FORJ=1TOC:PRINTTAB(A):FORI=1TOB:PRINT"*";:NEXT:PRINT:NEXT:GOTO

```

In C64 must be typed in with abbreviations.
> 2 votes

# Answer
# Desmos Graphing Calculator, ~~75~~ 74 bytes

Display to the screen, eh?

```
a=[1...9]
b=0a-4
c=[-2...0]
(0a,a) **
(0a,a-3) ****
(b,c) ****
(-b,c) ****

```

Pasting that in directly will fail because the asterisks are actually part of the label.

Try it on Desmos!
> 2 votes

# Answer
# Wolfram Language (Mathematica), 63 bytes

```
Uncompress@"1:eJxTTMoPCm5nYGBQAAItrRgDQyMUlpYWtZhacICPBwCDVxow"

```

It's a bit cheeky, but it gets the job done.

Try it online!
> 1 votes

# Answer
# C (GCC), ~~126~~ 83 bytes (thanks to ceilingcat)

```
main(y){for(;y<14;puts("********"+(y<=9)*6+3/++y*2))printf("    **"+(y>2)+y/10*3);}

```

Attempt This Online!
> 1 votes

# Answer
# Ruby, 42 bytes

```
puts"    **
"*2,"   ****
"*7,("*"*10+$/)*3

```

Attempt This Online!
> 0 votes

# Answer
# Python 3.8 (pre-release), 63 bytes

```
for i in[[4,2]]*2+[[3,4]]*7+[[0,10]]*3:print(" "*i[0]+"*"*i[1])

```

Try it online!
> 0 votes

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


title: Matrix with 1 to L(n), in all n columns

text:
# Question
Title: Matrix with 1 to L(n), in all n columns
## Challenge:

Take a list, **L** containing positive integers as input:

```
3 5 2 1 6

```

and create a matrix where the n'th column contains the vector **1:L(n)**, where shorter rows are padded with zeros.

### Test cases:

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

1
-
1

1   2   3   4   3   2   1
-------------------------
1   1   1   1   1   1   1
0   2   2   2   2   2   0
0   0   3   3   3   0   0
0   0   0   4   0   0   0

```

### Rules:

* Optional input and output formats
    + List of lists is an acceptable output format
* The matrix must be as small as possible (you may not pad it with more zeros than needed)
* Shortest code in each language wins
* Explanations are highly encouraged

# Answer
> 20 votes
# , ~~40~~ 38 bytes

```
function(l)outer(m<-1:max(l),l,"<=")*m

```

Try it online!

Explanation:

`outer` applies its third argument (the function) to all combinations of elements of its first two arguments, generating a matrix of `TRUE` and `FALSE` where each column has `TRUE` where `1:max(l)` is less than or equal to the corresponding element of `l`, for the example where `l=c(3,5,2,1,6)`:

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

```

Then supposing the resultant matrix is `A`, then `A*m` -\> `A[i,j]=A[i,j]*i` which coerces `TRUE` to 1 and `FALSE` to 0, producing the desired result.

# Answer
> 7 votes
# MATL, 8 bytes

```
"@:]Xho!

```

Try it online!

### Explanation

```
"      % Implicit input, L. For each k in L
  @    %   Push k
  :    %   Range [1 2 ... k]
]      % End
Xh     % Collect all stack contents in a cell array
o      % Convert to double matrix. The content of each cell is
       % right-padded with zeros if needed
!      % Transpose. Implicitly display

```

# Answer
> 6 votes
# Python 3, 54 bytes

```
lambda x:[[-~i*(i<a)for a in x]for i in range(max(x))]

```

Try it online!

# Answer
> 6 votes
# Mathematica, 20 bytes

```
PadRight@Range@#&

```

Contains U+F3C7 (Mathematica's builtin `Transpose` function)

Try it on Wolfram Sandbox

### Usage

```
PadRight@Range@#&[{3, 5, 2, 1, 6}]

```

> ```
> {
>  {1, 1, 1, 1, 1},
>  {2, 2, 2, 0, 2},
>  {3, 3, 0, 0, 3},
>  {0, 4, 0, 0, 4},
>  {0, 5, 0, 0, 5},
>  {0, 0, 0, 0, 6}
> }
>
> ```

### Explanation

```
PadRight@Range@#&

         Range@#    (* Generate {1..n} for all elements of input *)
PadRight@           (* Right-pad 0s so that all lists are equal length *)
                   (* Transpose the result *)

```

# Answer
> 5 votes
# Octave, 26 bytes

```
@(x)((y=1:max(x))'<=x).*y'

```

Anonymous function that inputs a row vector and outputs a matrix.

**Try it online!**

### Explanation

Consider input `x = [3 5 2 1 6]`. This is a row vector of size 1×5.

`1:max(x)` gives the row vector `[1 2 3 4 5 6]`, which is assigned to variable `y`.

The transpose of that, i.e. the column vector `[1; 2; 3; 4; 5; 6]`, is `<=`-compared (element-wise with broadcast) with the input `[3 5 2 1 6]`. The result is the 6×5 matrix

```
[1 1 1 1 1;
 1 1 1 0 1;
 1 1 0 0 1;
 0 1 0 0 1;
 0 1 0 0 1;
 0 0 0 0 1]

```

Finally, multiplying (element-wise with broadcast) by the column vector `[1; 2; 3; 4; 5; 6]`, obtained as `y` transposed, gives the desired result:

```
[1 1 1 1 1;
 2 2 2 0 2;
 3 3 0 0 3;
 0 4 0 0 4;
 0 5 0 0 5;
 0 0 0 0 6]

```

# Answer
> 4 votes
# 05AB1E, 4 bytes

```
€L0ζ

```

Try it online! or as a nicely formatted test suite

```
€L   # For each: get the range 1..input
  0ζ # zip, padding with 0s

```

# Answer
> 3 votes
# Husk, 4 bytes

Returns a list of lists

```
T0mḣ

```

Try it online!

### Explanation

```
  m    Map over the input
   ḣ   Range from 1 to n
T0     Transpose, padding with 0s

```

# Answer
> 3 votes
# Jelly, 3 bytes

```
Rz0

```

Try it online!

## Explanation

```
Rz0  Input: array A
R    Range, vectorizes to each integer
 z0  Transpose and fill with 0

```

# Answer
> 3 votes
# Pyth, 6 bytes

```
.tSMQZ

```

**Try it here!** or **Verify all the test cases (with pretty-print)!**

---

# Explanation

```
.tSMQZ   - Full program.

  SMQ    - Get the inclusive unary ranges for each.
.t       - Transpose, padding with copies of...
     Z   - ... Zero.
         - Implicit print.

```

A non-built-in transpose version would be:

```
mm*hd<dkQeS

```

This works as follows:

```
mm*hd<dkQeS   - Full program.

m        eS   - Map over [0, max(input)) with a variable d.
 m      Q     - Map over the input with a variable k.
   hd         - d + 1.
  *           - Multiplied by 1 if...
     <dk      - ... d is smaller than k, else 0.
              - Output implicitly.

```

# Answer
> 3 votes
# Actually, 17 bytes

```
;M╗♂R⌠╜;0@α(+H⌡M┬

```

Try it online!

Explanation:

```
;M╗♂R⌠╜;0@α(+H⌡M┬
;M╗                store the maximal element (M) of the input in register 0
   ♂R              range(1, n+1) for each n in input
     ⌠╜;0@α(+H⌡M   for each range:
      ╜;0@α          push a list containing M 0s
           (+        append to range
             H       take first M elements
                ┬  transpose

```

# Answer
> 2 votes
# Pyke, 3 bytes

This uses the new feature of Pyke, hex encodings... The best part is that we tie Jelly! Raw bytes:

```
4D 53 AC

```

Try it here!

The ASCII-Pyke equivalent would be 4 bytes:

```
MS.,

```

# How?

```
4D 53 AC   - Full program.

4D         - Map.
   53      - Inclusive range.
      AC   - Transpose with zeroes.
           - Output implicitly.

-------------------------------------

MS.,   - Full program.

M      - Map.
 S     - Inclusive range.
  .,   - Transpose with zeroes.
       - Output implicitly.

```

Here is a pretty-print version with ASCII, and here is one with hex encodings.

# Answer
> 2 votes
# Perl 5, ~~62~~ 57 + 1 (`-a`) = 58 bytes

```
$,=$";say map$i*($_-->0),@F while++$i&&(sort{$b-$a}@F)[0]

```

Try it online!

# Answer
> 2 votes
# Perl 6, 39 bytes

```
{zip (1 X..$_).map:{|@_,|(0 xx.max-1)}}

```

Try it

## Expanded:

```
{                # bare block lambda with implicit parameter ｢$_｣

  zip

    (1 X.. $_)   # turn each input into a Range that starts with 1

    .map:        # map each of those Ranges using the following code

    {            # bare block lambda with implicit parameter ｢@_｣
                 # (｢@_｣ takes precedence over ｢$_｣ when it is seen)

      |@_,       # slip the input into a new list

      |(         # slip this into the list

        0        # a ｢0｣
        xx       # list repeated by

          .max   # the max of ｢$_｣ (implicit method call)
          - 1    # minus 1 (so that zip doesn't add an extra row)
      )
    }
}

```

Note that `zip` terminates once the shortest input list is exhausted.

# Answer
> 2 votes
## C#, 136 bytes

---

### Data

* **Input** `Int32[]` `i` An array of ints
* **Output** `Int32[,]` A bidimentional array.

---

### Golfed

```
i=>{int m=System.Linq.Enumerable.Max(i),l=i.Length,x,y;var o=new int[m,l];for(y=0;y<m;y++)for(x=0;x<l;)o[y,x]=i[x++]>y?y+1:0;return o;};

```

---

### Ungolfed

```
i => {
    int
        m = System.Linq.Enumerable.Max( i ),
        l = i.Length,
        x, y;

    var o = new int[ m, l ];

    for( y = 0; y < m; y++ )
        for( x = 0; x < l; )
            o[ y, x ] = i[ x++ ] > y ? y + 1 : 0;

    return o;
};

```

---

### Ungolfed readable

```
// Take an array of Int32
i => {

    // Store the max value of the array, the length and declare some vars to save some bytes
    int
        m = System.Linq.Enumerable.Max( i ),
        l = i.Length,
        x, y;

    // Create the bidimensional array to output
    var o = new int[ m, l ];

    // Cycle line by line...
    for( y = 0; y < m; y++ )

        // ... and column by column...
        for( x = 0; x < l; )

            // And set the value of the line in the array if it's lower than the the value at the index of the input array
            o[ y, x ] = i[ x++ ] > y ? y + 1 : 0;

    // Return the bidimentional array.
    return o;
};

```

---

### Full code

```
using System;
using System.Collections.Generic;

namespace TestBench {
    public class Program {
        // Methods
        static void Main( string[] args ) {
            Func<Int32[], Int32[,]> f = i => {
                int
                    m = System.Linq.Enumerable.Max( i ),
                    l = i.Length,
                    x, y;
                var o = new int[ m, l ];
                for( y = 0; y < m; y++ )
                    for( x = 0; x < l; )
                        o[ y, x ] = i[ x++ ] > y ? y + 1 : 0;
                return o;
            };

            List<Int32[]>
                testCases = new List<Int32[]>() {
                    new[] { 1, 2, 5, 6, 4 },
                    new[] { 3, 5, 2, 1, 6 },
                    new[] { 1, 2, 3, 4, 3, 2, 1 },
                };

            foreach( Int32[] testCase in testCases ) {
                Console.WriteLine( " INPUT: " );
                PrintArray( testCase );

                Console.WriteLine( "OUTPUT: " );
                PrintMatrix( f( testCase ) );
            }

            Console.ReadLine();
        }

        public static void PrintArray<TSource>( TSource[] array ) {
            PrintArray( array, o => o.ToString() );
        }
        public static void PrintArray<TSource>( TSource[] array, Func<TSource, String> valueFetcher ) {
            List<String>
                output = new List<String>();

            for( Int32 index = 0; index < array.Length; index++ ) {
                output.Add( valueFetcher( array[ index ] ) );
            }

            Console.WriteLine( $"[ {String.Join( ", ", output )} ]" );
        }

        public static void PrintMatrix<TSource>( TSource[,] array ) {
            PrintMatrix( array, o => o.ToString() );
        }
        public static void PrintMatrix<TSource>( TSource[,] array, Func<TSource, String> valueFetcher ) {
            List<String>
                output = new List<String>();

            for( Int32 xIndex = 0; xIndex < array.GetLength( 0 ); xIndex++ ) {
                List<String>
                    inner = new List<String>();

                for( Int32 yIndex = 0; yIndex < array.GetLength( 1 ); yIndex++ ) {
                    inner.Add( valueFetcher( array[ xIndex, yIndex ] ) );
                }

                output.Add( $"[ {String.Join( ", ", inner )} ]" );
            }

            Console.WriteLine( $"[\n   {String.Join( ",\n   ", output )}\n]" );
        }
    }
}

```

---

### Releases

* **v1.0** \- `136 bytes` \- Initial solution.

---

### Notes

* None

# Answer
> 2 votes
# K (ngn/k), 17 bytes

```
{a*~x</:a:1+!|/x}

```

Try it online!

# Answer
> 1 votes
# C (gcc), 142 bytes

```
i,j,k;main(c,v)char**v;{for(;++i<c;k=k<*v[i]?*v[i]:k)printf("%c ",*v[i]);for(i=48;puts(""),i++<k;)for(j=1;j<c;)printf("%c ",i<=*v[j++]?i:48);}

```

Try it online!

# Answer
> 1 votes
# Proton, 38 bytes

```
a=>[[i<j?-~i:0for j:a]for i:0..max(a)]

```

Try it online!

# Answer
> 1 votes
# Add++, 37 bytes

```
D,g,@@*,bL_1+0XA$p$+bUp
L~*,€RAbM€gBc

```

Try it online!

# Answer
> 1 votes
# JavaScript (Node.js), 55 bytes

```
x=>f=(t=1,s,e=x.map(y=>y<t?0:s|=t))=>s?[e,...f(++t)]:[]

```

Try it online!

# JavaScript (Node.js), 63 bytes

```
x=>[...Array(Math.max(...x,t=0))].map(_=>x.map(y=>y<t?0:t,++t))

```

Try it online!

# Answer
> 1 votes
# Java 10, 115 bytes

```
a->{int l=a.length,m=0;for(int j:a)m=j>m?j:m;var r=new int[m][l];for(;l-->0;)for(m=0;m<a[l];r[m][l]=++m);return r;}

```

**Explanation:**

Try it online.

```
a->{                  // Method with integer-array parameter and integer-matrix return-type
  int l=a.length,     //  Length of the array
      m=0;            //  Largest integer in the array, 0 for now
  for(int j:a)        //  Loop over the array
    m=j>m?            //   If the current item is larger than `m`:
       j              //    Set `m` to this item as new max
      :               //   Else:
       m;             //    Leave `m` the same
  var r=new int[m][l];//  Result-matrix of size `m` by `l`, filled with zeroes by default
  for(;l-->0;)        //  Loop over the columns
    for(m=0;m<a[l];   //   Inner loop over the rows
      r[m][l]=++m);   //    Set the cell at position `m,l` to `m+1`
  return r;}          //  Return the result-matrix

```

# Answer
> 1 votes
# Uiua, 8 bytes

```
+1⍉⬚¯1∵⇡

```

Try it!

```
+1⍉⬚¯1∵⇡
      ∵⇡  # range of each
   ⬚¯1    # filling with -1
  ⍉       # transpose
+1        # increment

```

# Answer
> 1 votes
# Japt, 6 bytes

Would be 4 if Japt's transpose padded with `0` instead of `null`.

```
mõ zÔÕ

```

Try it

# Answer
> 1 votes
# TI-Basic, 48 bytes

```
Ans→A
List►matr(1 or Ans,[A]
[A]
For(I,2,max(ʟA
List►matr(I(I≤ʟA),[B]
augment(Ans,[B]
End
Ansᵀ

```

Takes input in `Ans`. Similar method to this answer.

# Answer
> 1 votes
# K (ngn/k), 20 bytes

```
{+(1+!'x),'&'-x-|/x}

```

Try it online!

# Answer
> 1 votes
# Scala, 76 bytes

Golfed version. Try it online!

```
l=>l.flatMap(v=>(1 to l.max).map(i=>if(i<=v)i else 0)).grouped(l.max).toList

```

Ungolfed version. Try it online!

```
object Main {
  def f(l: List[Int]): List[List[Int]] = {
    val m = (1 to l.max).toList
    l.flatMap { value =>
      m.map { i =>
        if (i <= value) i else 0
      }
    }.grouped(m.size).toList
  }

  def main(args: Array[String]): Unit = {
    println(f(List(3, 5, 2, 1, 6)))
  }
}

```

# Answer
> 1 votes
# , 10 bytes

```
0|:>:@i."0

```

No surprises

Attempt This Online!

```
0|:>:@i."0
      i."0   NB. create 0..n-1 range for each atom
   >:@       NB. then increment
0|:          NB. transpose

```

# Answer
> 1 votes
# Nekomata, 8 bytes

```
ṀR$ᵒ{≤0I

```

Attempt This Online!

Longer than other answers, because Nekomata doesn't have a padding builtin yet. I'll add one in some future version.

```
ṀR$ᵒ{≤0I
Ṁ           Maximum
 R          Range from 1 to that
  $         Swap
   ᵒ{       Make a 2D array by the following function
     ≤      If left <= right, return left
      0I    Otherwise, return 0

```

---

# Nekomata, 8 bytes

```
R:∑0*ᵚ+Ť

```

Attempt This Online!

```
R:∑0*ᵚ+Ť
R           Range from 1 to input
 :          Duplicate
  ∑         Sum
   0*       Multiply by 0
     ᵚ+     Add this to each element of the other array
       Ť    Transpose

```

# Answer
> 0 votes
# APL (Dyalog Classic), 5 bytes

```
⍉∘↑⍳¨

```

Anonymous tacit function. Did you know that APL's Mix function automatically pads with zeros?

Try it online!

---
Tags: code-golf, matrix
---