title: Short drawing programme

text:
# Question
Title: Short drawing programme
You just invited a liberal arts major to your house and you're telling him/her

> "You know, I am a great programmer and I can do x and y and z..."

S/he quickly gets bored and asks you:

> "If you really are a great programmer, can you make a programme to let me draw, I just need to draw lines on the screen by using the mouse, and selecting different colours in any manner".

Your code may import standard libraries. Your code may require the colours to be selected via the keyboard.

This is ; shortest code wins.

# Bullet points

* The lines are drawn by moving the mouse around while pressing the left button.
* Bresenham's Line Algorithm is not necessary any built-in algorithm will do the trick
* If the user can change the line thickness in any way you get a *** 0.8** bonus but it is not obligatory.
* I guess it should be nicer to implement the line-drawing ourselves, but if you want you can import a library for that just say it in the code description.
* The minimum is 5 different colours (red,green,blue,white,black). If you make them change randomly you get a penalty of \*1.2. You may change them in any way you may want (both buttons and key presses are OK).
* Drawing them pressing the mouse between to points or freehand would be best (i.e. as you do in paint) and gives you a bonus of \*0.7 , but any other method is okay: (example) click two points and draw a line between those points?
* The drawing canvas has to be **600x400**
* Changing the colour should change the colour only of the lines that will be drawn in the future.
* Implementing a "Clear All " command is not obligatory but if you implement that you get **\*0.9** bonus.

# Answer
> 9 votes
## HTML + jQuery + CSS - 507 x (0.7 x 0.8 x 0.9) = 255.528

Not as short as I thought it would be, but I like the result.

**Features:**

* Click-and-drag drawing mode. (**0.7**)
* Seven colors (black + rainbow).
* Variable brush width (slider control). (**0.8**)
* Clear all function. (**0.9**)

**Live Demo:** http://jsfiddle.net/onsLkh8y/9/

---

### HTML - 84 bytes

```
<input id="r" type="range" min="1" max="9"><canvas id="c" width="600" height="400"/>

```

---

### CSS - 35 bytes

```
#c{border:1px solid;cursor:pointer}

```

---

### jQuery - 388 / 446 bytes

**W3C compliant browsers (e.g. Chrome) - 388 bytes**

```
var t=c.getContext('2d');$.each('black0red0orange0yellow0green0blue0purple0clear'.split(0),function(k,v){
$(r).before($('<button>'+v+'</button>').click(function(){k>6?t.clearRect(0,0,600,400):t.strokeStyle=v}))})
$(c).mousedown(function(e){t.lineWidth=$(r).val();t.beginPath();t.moveTo(e.offsetX,e.offsetY)})
.mousemove(function(e){if(e.which==1){t.lineTo(e.offsetX,e.offsetY);t.stroke()}})

```

**Cross-Browser version (fixes for Firefox, Safari, IE) - 446 bytes**

```
var t=c.getContext('2d');$.each('black0red0orange0yellow0green0blue0purple0clear'.split(0),function(k,v){
$(r).before($('<button>'+v+'</button>').click(function(){k>6?t.clearRect(0,0,600,400):t.strokeStyle=v}))})
var d,p=$(c).offset();$(c).mousedown(function(e){d=t.lineWidth=$(r).val();t.beginPath()t.moveTo(e.pageX-p.left,
e.pageY-p.top)}).mousemove(function(e){if(d){t.lineTo(e.pageX-p.left,e.pageY-p.top);t.stroke()}}).mouseup(function(){d=0})

```

**Fixes:**

* FireFox - `event.offset[X|Y]` are undefined.
* Safari - `event.which` and `event.buttons` are not meaningfully defined on `mousemove`.
* Internet Explorer - works with both of the above fixes, although using `e.buttons` would have been sufficient.

# Answer
> 10 votes
# Processing - 93 · 0.9 = 83.7

With next to no overhead for drawing, but a very verbose syntax, in Processing the best score is probably reached without any nice features and only one bonus:

```
void setup(){
size(600,400);
}
void draw(){
if(mousePressed)line(mouseX,mouseY,pmouseX,pmouseY);
}

```

Score: **93 · 0.9 = 83.7** (Newlines are for readability only and are not counted in the score.)

However, it's much more fun with all the bonuses in place:

```
void setup(){
size(600,400);
}
int i,x,y;
void draw(){
stroke(7*i%256,5*i%256,i%256);
strokeWeight(i%9);
if(keyPressed)i++;
if(!mousePressed){x=mouseX;y=mouseY;if(x<0)background(0);}
}
void mouseReleased(){
line(x,y,mouseX,mouseY);
}

```

Score: **221 · 0.8 · 0.7 · 0.9 = 111.4**

It's used like this:

* Click and drag the mouse to draw a straight line.
* While clicked, drag the mouse off the left side of the window and release the mouse button to clear the screen.
* Holding down any key will cycle through the red, green and blue values of the drawing colour and through different stroke thicknesses. Since the cycling periods are different, practically all combinations can be reached (with a bit of trying).

## Edit:

Since freehand drawing gives the 0.7 bonus as well, here is yet another solution:

```
void setup(){
size(600,400);
}
int i;
void draw(){
stroke(7*i%256,5*i%256,i%256);
strokeWeight(i%9);
if(keyPressed)i++;
if(key>9)background(0);
if(mousePressed)line(mouseX,mouseY,pmouseX,pmouseY);
}

```

Score: **188 · 0.8 · 0.7 · 0.9 = 94.8**

It's used like this:

* Click and drag to draw freehand lines.
* Hold the tab key to change the colour and stroke thickness. This can also be done while drawing (see picture).
* Hit any key but tab and then tab to clear the screen.

# Answer
> 9 votes
# Python 2.7 - ~~339~~ ~~197~~ 324 * (0.7 * 0.8 * 0.9) = 163

Edit: I discovered pygame can draw lines with variable width so here is an update.

An experiment in using the PyGame modules.

A simple paint program that draws lines from the MOUSEDOWN event (value 5) to the MOUSEUP event (value 6). It uses the pygame.gfxdraw.line() function. Pressing the TAB key will cycle through 8 colours. Pressing the BACKSPACE key will clear the display to a carefully crafted paper white colour. The ENTER key will cycle the brush size through 0-7 pixels in width.

I am new at code-golf so I may have missed some methods of reducing the code size.

```
import pygame as A,pygame.draw as G
P=A.display
D=P.set_mode((600,400))
C=(0,255)
S=[(r,g,b) for r in C for g in C for b in C]
w=n=1
while n:
 e=A.event.wait()
 t=e.type
 if t==12:n=0
 if t==2:
  if e.key==9:n+=1
  if e.key==13:w+=1
  if e.key==8:D.fill(S[7])
 if t==5:p=e.pos
 if t==6:G.line(D,S[n%8],p,e.pos,w%8)
 P.flip()

```

## Sample picture 1:

## Sample picture 2:

# Answer
> 5 votes
**C# 519 x 0.7 x 0.8 x 0.9 = 261.6** Using the DrawLine method.

**Golfed:**

```
using System;using System.Drawing;using System.Windows.Forms;class f:Form{[STAThread]static void Main(){f F=new f{Width=600,Height=400};Point s=default(Point);sbyte[]c={0,0,0,1};F.MouseDown+=(_,e)=>{s=new Point(e.X,e.Y);};F.MouseUp+=(_,e)=>{F.CreateGraphics().DrawLine(new Pen(Color.FromArgb(255,c[0],c[1],c[2]),c[3]),s.X,s.Y,e.X,e.Y);};F.KeyPress+=(a,e)=>{unchecked{switch(e.KeyChar){case'r':c[0]++;break;case'g':c[1]++;break;case'b':c[2]++;break;case't':c[3]++;break;case'c':F.Invalidate();break;}}};F.ShowDialog();}}

```

**Readable:**

```
using System;
using System.Drawing;
using System.Windows.Forms;

class f : Form
{
    [STAThread]
    static void Main()
    {
        f F = new f { Width = 600, Height = 400 };
        Point s = default(Point);
        sbyte[] c = { 0, 0, 0, 1 };
        F.MouseDown += (_, e) => { s = new Point(e.X, e.Y); };
        F.MouseUp += (_, e) => { F.CreateGraphics().DrawLine(new Pen(Color.FromArgb(255, c[0], c[1], c[2]), c[3]), s.X, s.Y, e.X, e.Y); };
        F.KeyPress += (a, e) =>
        {
            unchecked
            {
                switch (e.KeyChar)
                {
                    case 'r': c[0]++; break;
                    case 'g': c[1]++; break;
                    case 'b': c[2]++; break;
                    case 't': c[3]++; break;
                    case 'c': F.Invalidate();break;
                }

            }
        };
        F.ShowDialog();
    }
}

```

By holding **r**, **g** or **b** on your keyboard it changes the color of the next line by incrementing an sbyte-array at the corresponding index. It will start at 0 again when overflowing. So this gives us plenty colors. Same goes for thickness of the line which is increased by holding **t**. Pressing **c** clears the form.

# Answer
> 5 votes
# Mathematica - 333 x 0.7 x 0.8 x 0.9 = 168

```
l = {}; c = Black; s = .01;
ColorSetter@Dynamic@c
Dynamic@s~Slider~{0, .02}
Button["Clear", l = {}]
"/" Checkbox@Dynamic@b
EventHandler[
 Dynamic@Graphics@{White, Rectangle@{600, 400}, l},
 {"MouseDown" :>
   AppendTo[l, p = {}; {c, Thickness@s, Line@Dynamic@p}],
  "MouseDragged" :> (p =
     Append[p, MousePosition@"Graphics"][[If[b, {1, -1}, All]]]),
  "MouseUp" :> (l[[-1, 3]] = Line@p)
  }
 ]

```

# Answer
> 4 votes
# Tcl/Tk, 252

# x 0,8 x 0,7 x 0,9

# = 127,008

~~253 x 0,8 x 0,7 x 0,9= 127,512~~

~~254 x 0,8 x 0,7 x 0,9= 128,016~~

~~255 x 0,8 x 0,7 x 0,9= 128,52~~

```
grid [canvas .c -w 600 -he 400]
set c red
incr t
lmap k {1
B1-Motion
3
MouseWheel
2} s {{set L [.c cr l %x %y %x %y -f $c -w $t]}
{.c coo $L "[.c coo $L] %x %y"}
{set c [tk_chooseColor]}
{if $t|%D>0 {incr t [expr %D/120]}}
{.c de all}} {bind . <$k> $s}

```
~~Tcl/Tk, 267 x 0,8 x 0,7 x 0,9 = 134,568
```
grid [canvas .c -w 600 -he 400]
set c red
set t 0
bind .c <1> {set L [.c cr l %x %y %x %y -f $c -w $t]}
bind .c <B1-Motion> {.c coo $L "[.c coo $L] %x %y"}
bind .c <3> {set c [tk_chooseColor]}
bind .c <MouseWheel> {if $t||%D>0 {incr t [expr %D/120]}}
bind .c <2> {.c de all}

```~~

To use it:

* Left mouse button behaves as question requests
* The initial color is red. Right mouse shows a dialog which allows the user to choose the color which will be used the next time. Always press OK button, otherwise color will be undefined. I could fix this, but it would consume bytes
* To adjust the thickness of the line that will be used next time, you can rotate the mouse wheel: Up=thicker, Down=thinner
* To clear the image press the middle mouse button

**A simple test:**

# Answer
> 2 votes
# DarkBASIC Pro - 318 x 0.7 x 0.9 = 200.34

The most interesting thing here is using some bitwise logic on the current keyboard scancode to change the color. I use two different bits from the scancode for each channel - so almost any 6-bit color is possible.

* Hold down any key on your keyboard to use a color (on my American keyboard: White=F5, Black=no key, Red=2, Green=- (minus), Blue=b)
* Right-click to clear

Here is a compiled EXE: Download

```
#constant a set current bitmap
set display mode 800,400,32
create bitmap 1,800,400
do
s=scancode()
ink rgb((s&&3)*85,((s/4)&&3)*85,((s>>4)&&3)*85),0
m=mousex()
n=mousey()
o=mouseclick()
if o*(d=0) then d=1:x=m:y=n
a 1
if (o=0)*d then d=0:line x,y,m,n
if o=2 then cls
a 0
cls
copy bitmap 1,0
if d then line x,y,m,n
loop

```

# Answer
> 1 votes
# BBC BASIC - 141 no bonuses

My first programming language and generally never used by me anymore :)

```
SYS "SetWindowPos",@hwnd%,0,0,0,600,400,6:VDU 26
1 MOUSE X,Y,b
IF b=4 THEN GOTO 4
GOTO 1
4 MOUSE x,y,b
IF b=0 THEN LINE X,Y,x,y:GOTO 1
GOTO 4

```

# Answer
> 1 votes
# Python 2.7 - 384 * .8 * .7 = 215.04

```
from Tkinter import*;o=1
a='0f';C=['#'+r+g+b for r in a for g in a for b in a]
def i(a):global o;o+=1
def d(a):global o;o-=1
def I(a):global u;u+=1
def D(a):global u;u-=1
m=Tk();u=0;c=Canvas(width=600,height=400);c.bind("<B1-Motion>",lambda x:c.create_rectangle((x.x,x.y,x.x+o,x.y+o),fill=C[u],outline=C[u]));m.bind("q",i);m.bind("w",d);m.bind("x",D);m.bind("z",I);c.pack();mainloop()

```

## With all bonuses: 462 * .9 * .8 * .7 = 232.848

```
from Tkinter import*;o=1
a='0f';C=['#'+r+g+b for r in a for g in a for b in a]
def i(a):global o;o+=1
def d(a):global o;o-=1
def I(a):global u;u+=1
def D(a):global u;u-=1
m=Tk();u=0;c=Canvas(width=600,height=400);c.bind("<B1-Motion>",lambda x:c.create_rectangle((x.x,x.y,x.x+o,x.y+o),fill=C[u],outline=C[u]));m.bind("q",i);m.bind("w",d);m.bind("x",D);m.bind("z",I);m.bind("m",lambda _:c.create_rectangle((0,0,602,402),fill=C[7],outline=C[5]));c.pack();mainloop()

```

# Answer
> 1 votes
# APL (dzaima/APL), 65 bytes, no bonuses

```
P5.size←2⌿600
P5.draw←{P5.LM.p:P5.G.ln P5.mx P5.my P5.pmx P5.pmy}

```

A straightforward port of the existing processing answer.

## Explanation

```
P5.size←2⌿600                                        set canvas to 600x600 pixels
P5.draw←{                                         } do the following every frame:
P5.draw←{P5.LM.p:                                 } if the mouse is held down:
                 P5.G.ln                            draw a line from
                         P5.mx P5.my                current mouse position
                                     P5.pmx P5.pmy  to previous mouse position

```

---
Tags: code-golf, graphical-output
---


title: Draw a range of mountain ranges

text:
# Question
Title: Draw a range of mountain ranges
Inspired by Fibonacci domino tiling, this problem is about generating ASCII art representing another famous combinatorial sequence.

A *n-step mountain diagram* is a drawing of a mountain range, using exactly *n* '/' and *n* '\\' characters, such that characters sketch a continuous curve which never dips below its initial "altitude". For example,

```
   /\/\
/\/    \

```

and

```
   /\
/\/  \/\

```

are both 4-step mountain diagrams, but

```
/\  /\/\
  \/

```

is not.

**Input**

The program should accept an integer *n* from stdin or as the parameter to a function.

**Output**

Print all *n*-step mountain diagrams to stdout. The diagrams can be in any order, but should be separated by some sort of whitespace. You can decide if different diagrams will be output horizontally, vertically, etc.

As in the domino tiling problem, you can use whatever whitespace you want. This includes extra newlines before or after the printed output.

**Example**

Some sample valid outputs for *n*=3:

Valid output A:

```
                                        /\
         /\             /\             /  \    /\/\
/\/\/\  /  \/\       /\/  \           /    \  /    \

```

Valid output B:

```
   /\
/\/  \

 /\/\
/    \

/\/\/\

  /\
 /  \
/    \

 /\
/  \/\

```

Valid output C:

```
  /\
 /  \       /\
/    \   /\/  \
                  /\/\
 /\              /    \
/  \/\   /\/\/\

```

This is code golf; shortest program (in bytes) wins.

# Answer
# Python 2: 151 chars

```
N=2*input()
for i in range(2**N):
 L=[];c=1;exec"b=i%2;c+=2*b-1;L+=[[' ']*N];L[-1][b-c]='\/'[b];i=i/2*(c>0);"*N
 for x in(c==1)*zip(*L):print"".join(x)

#Output for n=3:

  /\
 /  \
/    \

 /\/\
/    \

   /\
/\/  \

 /\
/  \/\

/\/\/\

```

Wow, this is a mess.

The first idea is to use the numbers `0 to 2**N-1` to encode all sequences of `N` up-moves and down-moves in their bits. We read off these bits one by one by repeated `%2` and `/2`, iterated in an `exec` loop.

We store the running mountain range sideways in a transposed list of strings `L`. Each time, we generate a new a row of spaces are replace one space in the new row with `/` or `\` depending on whether an up-move or down-move happened.

The index of that space is `c` spaces from the end, where `c` is the running height. Doing it from the front would make the mountains upside down. We further shift it by `b` to align upward and downward moves , getting `[b-c]`. Starting `c` at 1 rather than 0 fixes an off-by-one error.

To eliminate cases where `c` dips below the start value `1`, when this happens, we set `i` to `0`, which causes all further moves to be downward, making `c` become more negative. Then, when we check whether `c` ended at `1`, we also check whether `c` ever fell below it. We only `print` the mountain range if `c` is `1`.

To print, we do `zip(*L)` to transpose the range from vertical to horizontal, and print each joined string. A lot of trouble in this answer came from Python treats strings as immutable, so we worked with them as lists of characters and only joined them into strings for printing.

Thanks to @flornquake for help and improvements.
> 10 votes

# Answer
## APL (88)

```
{{⍉↑'\/'[1+⍵=1]/⍨¨¯1+2×K=⊂⌽⍳⌈/K←(⍵≠1)++\⍵}¨Z/⍨{(0=+/⍵)∧∧/0≤+\⍵}¨Z←↓⍉¯1+2×(N/2)⊤⍳2*N←2×⍵}

```

Output for `n=3`:

```
      {{⍉↑'\/'[1+⍵=1]/⍨¨¯1+2×K=⊂⌽⍳⌈/K←(⍵≠1)++\⍵}¨Z/⍨{(0=+/⍵)∧∧/0≤+\⍵}¨Z←↓⍉¯1+2×(N/2)⊤⍳2*N←2×⍵}3
 /\/\/\     /\    /\      /\/\     /\
         /\/  \  /  \/\  /    \   /  \
                                 /    \

```

Explanation:

* `(N/2)⊤⍳2*N←2×⍵`: get a bitfield for each number from `0` to `2^⍵`.
* `Z←↓⍉¯1+2×`: multiply by 2 and subtract 1, giving `1` for up and `-1` for down. Store a vector of vectors, each vector containing the representation for one number, in `Z`.
* `{`...`}¨Z`: for each element of `Z`:
    + `∧/0≤+\⍵`: check that the running sum never falls below `0` (doesn't go below ground level),
    + `(0=+/⍵)`: and that the total sum is `0` (ends up back at ground level).
* `{`...`}¨Z/⍨`: select those elements from `Z` for which that is true. For each of them:
    + `K←(⍵≠1)++\⍵`: find the height for each character, and store in `K`. Raise each `\` up one, so that they line up with the `/`s properly. This makes the ground height `1`.
    + `¯1+2×K=⊂⌽⍳⌈/K`: for each column, make a list `[1..max(K)]`, and mark the position of the character in that column with `1` and the rest as `-1`. (Replicating by -1 fills that position with a space.)
    + `'\/'[1+⍵=1]/⍨¨`: find the correct character for each column, and replicate it by the list for that column.
    + `⍉↑`: turn the result into a matrix and put it right-side-up
> 7 votes

# Answer
# Python, ~~261~~ ~~241~~ 236 characters

```
import itertools as I
n=input()
S={}
for q in I.permutations((-1,1)*n):
 s=0;B=[[' ']*n*2 for _ in range(n+2)];o=0
 for i in q:
    B[n-s+(i==-1)][o]=' /\\'[i];s+=i;o+=1
    if s<0:break
 else:
    for l in (B,[])[q in S]:print''.join(l)
 S[q]=1

```

It starts taking a while for `n=5` and up...

```
$ echo 1 | py mountrange.py

/\

Laxori@Laxori-PC /cygdrive/c/Programmin
$ echo 2 | py mountrange.py

/\/\

 /\
/  \

Laxori@Laxori-PC /cygdrive/c/Programmin
$ echo 3 | py mountrange.py

/\/\/\

   /\
/\/  \

 /\
/  \/\

 /\/\
/    \

  /\
 /  \
/    \

Laxori@Laxori-PC /cygdrive/c/Programmin
$ echo 4 | py mountrange.py

/\/\/\/\

     /\
/\/\/  \

   /\
/\/  \/\

   /\/\
/\/    \

    /\
   /  \
/\/    \

 /\
/  \/\/\

 /\  /\
/  \/  \

 /\/\
/    \/\

 /\/\/\
/      \

    /\
 /\/  \
/      \

  /\
 /  \
/    \/\

  /\
 /  \/\
/      \

  /\/\
 /    \
/      \

   /\
  /  \
 /    \
/      \

```
> 2 votes

# Answer
# JavaScript (ES6) 159 ~~163~~

Just like my answer for Fibonacci Domino Tiling, I examine all the sequences of n+n bits, with 1 marking a '/' and 0 marking a '\\' (just for output, '2' is later added to mark a newline). While building tha ascii pattern I check the balance - same numbers of 0 and 1, and never going below the starting base line - and output what obey the rules.

Output done with 'alert', that is standard for JS codegolf but quite annoying, and maybe against the rules. Using console.log the character count goes to 165.

```
F=n=>{
  for(i=0;++i<1<<n+n;l||alert((o+'').replace(/,\d?/g,r=>'\\/\n '[r[1]||3])))
    for(p=l=o=[],j=i;l+1&&p++-n-n;j/=2)
      b=j&1,
      l-=1-b-b,
      (o[k=b+n-l]=o[k]||[2])[p]=b;
}

```

**Less golfed**

```
F=n=>{
  m = n+n
  outer:
  for (i=1; i < 1<<m; i+=2)
  {
    o=[]
    l=0;
    p=1;
    for (j = 1; j <1<<m; j+=j,p++)
    {
      if (i&j)
      {
        q=o[n-l]||[]
        q[p]=1;
        o[n-l]=q
        ++l;
      }
      else
      {
        --l;
        if (l<0) continue outer;
        q=o[n-l]||[]
        q[p]=0;
        o[n-l]=q
      }
    }
    if (l==0) console.log(o.join('\n').replace(/,\d?/g,r=>'\\/'[r[1]]||' '));
  }
}

```

**Test** in FireFox/FireBug console.

```
F(4)

```

*Output*

```
   /\
  /  \
 /    \
/      \

  /\/\
 /    \
/      \

    /\
 /\/  \
/      \

    /\
   /  \
/\/    \

  /\
 /  \/\
/      \

 /\/\/\
/      \

   /\/\
/\/    \

 /\  /\
/  \/  \

     /\
/\/\/  \

  /\
 /  \
/    \/\

 /\/\
/    \/\

   /\
/\/  \/\

 /\
/  \/\/\

/\/\/\/\

```
> 2 votes

# Answer
# CJam, 84 bytes

```
q~:Q{Q[XW]*mr1\{\_@+}%_{*}*{(\{_Q\-)S*@2$m0<" /""\\"?+QS*+Q)<\}%);z{N\++}*o}{;}?1}g

```

Note that this program prints the mountains in an infinite loop so the online interpreter will not help you; invoke at the command line using

```
java -jar cjam-0.6.2.jar mountain.cjam <<< 5

```

or to try online use

```
q~:Q{Q[XW]*mr1\{\_@+}%_{*}*{(\{_Q\-)S*@2$m0<" /""\\"?+QS*+Q)<\}%);z{N\++}*o}{;}?}fZ

```

and just hit the run button a bunch of times in succession and imagine the output is concatenated.

The basic idea is that we know a mountain range of size Q has Q of each upward and downward transitions.

```
 Q[XW]*mr                                   #shuffled list of Q 1s and -1s
1        {\_@+}%                            #height map after each transition
                _{*}*                       #if it passes through 0 it's invalid

```

Then if it's valid we print it, if not we pop it from the stack so it doesn't overflow.

The print routing basically builds each column as Q - height spaces, then the symbol, then enough more spaces to hit Q+1 total characters, and then we transpose and print the lines with newlines between them.

```
z{N\++}*o                                   #transpose, insert newlines, print

```
> 1 votes

# Answer
# C,179

excluding unnecessary whitespace.

A similar strategy to edc65. I run through all the `n*2`-bit binary values, considering `/`=1 and `\`=0.

I format a single string containing `n` linebreaks every `n*3` characters. As written the string contains 1000 characters, so there is usually a lot of whitespace printed after the mountain. (This can be fixed by adding `s[n*n*3]=0` before the `puts`.) Anyway, this enables me to output the whole mountain with a single `puts` after checking that it complies with the rules.

I will try converting it to a function and reducing to a single `for` loop later.

```
i,n,x,y,q,r;
main(){
  scanf("%d",&n);
  for(i=1<<n*2;i--;){                              //run though all n*2-digit binary numbers
    char s[]={[0 ...999]=32};                      //fill an array with spaces. This syntax is allowed by GCC
    y=n;                                           //start y one square below the grid (note: r is initialised to 0 by default.)
    for(x=n*2;x--;)                                //for each digit of i
      q=i>>x&1,
      y+=q+r-1,                                    //move up if the current and last digit are 0, down if they are 1, and stay on the same line if they are different.
      y<n?s[y*n*3]=10,s[y*n*3+x+1]=92-45*q:(x=0),  //if y is within the grid, put a newline (ASCII 10)at the beginning of the row and write \ or / (ASCII 92 or 47) to the correct square. Otherwise abort the x loop.
      r=q;                                         //store the current bit of i to r as it will be needed on the next iteration
    n-1-y||puts(s);                                //if y is on the bottom row of the grid, output the mountain
  }
}

```

**Output** (note the massive amount of whitespace to the right)

```
$ ./a
4

 /\
/  \/\/\

   /\
/\/  \/\

 /\/\
/    \/\

  /\
 /  \
/    \/\

     /\
/\/\/  \

 /\  /\
/  \/  \

   /\/\
/\/    \

 /\/\/\
/      \

  /\
 /  \/\
/      \

    /\
   /  \
/\/    \

    /\
 /\/  \
/      \

  /\/\
 /    \
/      \

   /\
  /  \
 /    \
/      \

```
> 0 votes

# Answer
# Haskell, 140 bytes

After several attempts failed to be very golfable, I ended up with this Haskell implementation. I'm happy just to be within a factor of 2 of the APL solution!

**Golfed solution:**

```
e=' ':e
m=[[]]:[[('/':e):map(' ':)x++('\\':e):y|k<-[0..n],x<-m!!(n-k),y<-m!!k]|n<-[0..]]
f n=putStr$unlines[map(!!(n-k))a|a<-m!!n,k<-[1..n]]

```

**Ungolfed and commented:**

The program builds the set of *n*-step mountain diagrams recursively. Each diagram is represented by a list of infinitely-long strings, representing the mountain drawn sideways followed by spaces extending to infinity. This ensures that all diagrams have the same height, which makes the recursion easier. The mountain printer accepts a parameter which clips the height to a finite value.

```
import Data.List (transpose)

-- Elementary picture slices, extending to infinity.
empty = ' ' : empty
up    = '/' : empty
down  = '\\': empty

-- A function which draws a mountain picture to stdout, clipping
-- its height to n.
printMtn n = putStr . unlines . reverse . take n . transpose

{-- Combine mountain pictures x and y by

              x
 x # y  ==   / \y

--}
x # y = up : raised x ++ down : y
    where raised = map (' ':)

-- Given two sets X,Y of mountain pictures, compute the set X <> Y of all
-- combined pictures x#y for x in X, y in Y.
xs <> ys = [ x # y | x <- xs, y <- ys ]

-- Compute the (++,<>)-convolution of a list with itself, e.g.:
--   autoConvolve [x0,x1,x2] == (x2 <> x0) ++ (x1 <> x1) ++ (x0 <> x2)
autoConvolve xs = concat $ zipWith (<>) (reverse xs) xs

{--
    mtns is a list whose nth entry is the list of all n-step mountain diagrams.
    It is defined recursively by:
        --  The only 0-step mountain diagram is empty.
        --  Each (n+1)-step diagram can be uniquely drawn as x#y for
            some k-step diagram x and (n-k)-step diagram y.
--}
mtns = [[]] : [autoConvolve (prefix n) | n <- [1..]]
    where prefix n = take n mtns

-- The driver function: apply the height n mountain printer to each
-- n-step mountain diagram.  Whitespace is guaranteed by the order
-- in which the diagrams appear.
test n = mapM_ (printMtn n) $ mtns!!n

```

**Sample usage:**

```
$ ghci mtn3.hs
GHCi, version 7.6.3: http://www.haskell.org/ghc/  :? for help
Loading package ghc-prim ... linking ... done.
Loading package integer-gmp ... linking ... done.
Loading package base ... linking ... done.
[1 of 1] Compiling Main             ( mtn3.hs, interpreted )
Ok, modules loaded: Main.
λ> f 3
  /\
 /  \
/    \

 /\/\
/    \

 /\
/  \/\

   /\
/\/  \

/\/\/\
λ>

```
> 0 votes

# Answer
# GolfScript 103 (demo)

```
2*:§2\?,{2base.,§\-[0]*\+:a 1\{.2*@(.@+@@+}%:l$)\;),-1%{a,,{.l=2$=\a=1$+*' \\/'= }%\;n+}%\1=*l$(\;0>*}/

```

The program takes an integer parameter tries to render as mountains all binary representations of the numbers from 0 to 2^(n-1). It does not render invalid combinations (ex: the ones that go below level 0).
> 0 votes

# Answer
# Husk, 54 bytes

```
mȯ¶↔T' §zoFz:,mömR' ∫Ẋo±+:_1†o!"/¦">0uf(Λ≥0∫)†?I←IPṘḋ2

```

Try it online!

Does surprisingly well in this challenge.

## Explanation

`ḋ2` array \[0,1\]

repeat each \\$n\\$ times : `3 → [1,1,1,0,0,0]`

`†?I←I` decrement the zeroes

`f(Λ≥0∫)` filter out the non-ranges using cumulative sum

`u` uniquify

`§zoFz:,` apply the following two functions a & b to the above result and zip them together

`mömR' ∫Ẋo±+:_1` Function a: convert unequal pairs to 0's and create the required amount of spaces

`†o!"/¦">0` Function b: convert 1 to / and -1 to \

These are now joined to create the mountains.

`↔T'` Transpose each mountain, filling with spaces then reverse

`mȯ¶`  join with newlines

Each mountain is then auto-displayed with newlines.
> 0 votes

---
Tags: code-golf, ascii-art, combinatorics
---


title: Wuxings in Positive Action

text:
# Question
Title: Wuxings in Positive Action
# Background

Wuxings(五行) are the five "elements" in Chinese philosophy. They are **Fire**(火), **Water**(水), **Wood**(木), **Metal**(金), and **Soil**(土). You can find them on East Asian calendar, where some days (Tuesday through Saturday) are named by the Wuxings.

Some Korean names are given according to Wuxings, so that father's name will have a positive effect to his children. Let's simulate that.

# Positive actions

* **Fire** fertilizes **Soil**.
* **Soil** incubates **Metal**.
* **Metal** is a container for **Water**.
* **Water** nourishes **Wood**.
* **Wood** fuels **Fire**.

# Negative actions

These are irrelevent to this challenge, but I'm showing them anyway.

* **Fire** melts **Metal**.
* **Metal** chops **Wood**.
* **Wood** penetrates **Soil**.
* **Soil** blocks **Water**.
* **Water** extinguishes **Fire**.

# Ideographs

Some ideographs have a Wuxing as its radical. Here, only the **CJK Ideographs**(U+4E00–U+9FFF), a Unicode block, will be considered as of Unicode 1.0.1.

* 火(U+706B)–爩(U+7229) have **Fire** as the radical.
* 水(U+6C34)–灪(U+706A) have **Water** as the radical.
* 木(U+6728)–欟(U+6B1F) have **Wood** as the radical.
* 金(U+91D1)–钄(U+9484) have **Metal** as the radical.
* 土(U+571F)–壪(U+58EA) have **Soil** as the radical.
* All other characters fall in *don't care* situation.

# Notes

* Some characters, in Unicode's own dictionary, disagree with the categorization above. For example, 泵(U+6CF5) actually doesn't have Water as its radical, but rather "石". For another example, 渠(U+6E20) has ambiguous radical, Water or Wood. Such characters also fall in *don't care* situation.
* After Unicode 1.0.1, Unicode added more characters that has a Wuxing as their radical to the block and other blocks. For example, 龦(U+9FA6) also has Fire as its radical. This detail shall be ignored in this challenge, and such characters also fall in *don't care* situation.

# Objective

Given an ideograph having a Wuxing \\$W\\$ as its radical, output **any** ideograph whose radical will be positively acted by \\$W\\$.

# Examples

Given 溒(U+6E92), it has Water as its radical, so output any ideograph having Wood as its radical, since Water nourishes Wood. For example, 杜(U+675C).

Given 坽(U+577D), it has Soil as its radical, so output any ideograph having Metal as its radical, since Soil incubates Metal. For example, 鉺(U+927A).

# Answer
> 5 votes
# Jelly, 18 bytes

```
“Ọ{ƊɠṪƲ‘ɓ:Ḣ<Sịɗ‘×Ḣ

```

A monadic Link accepting an ordinal which yields an ordinal as below:

```
Input                           Output
Fire   (28779 火 - 29225 爩)    22444  垬  (Soil)
Soil   (22303 土 - 22762 壪)    37467  鉛  (Metal)
Metal  (37329 金 - 38020 钄)    27874  波  (Water)
Water  (27700 水 - 28778 灪)    26426  机  (Wood)
Wood   (26408 木 - 27423 欟)    28960  焠  (Fire)

```

**Try it online!** Or see all valid cases.

### How?

Integer dividing by \\$181\\$:

1. keeps the ranges distinct
2. reduces all values to less than \\$256\\$
3. has more than one result for each range
4. has a single result greater than \\$181\\$

This allows us to place all our magic numbers into a single list of code-page indices, using these for the integer division, the category identification, a lookup of the new category, and a final multiplication:

```
“Ọ{ƊɠṪƲ‘ɓ:Ḣ<Sịɗ‘×Ḣ - Link: ordinal, n       e.g. n = 27700 (木 - minimal Water)
“Ọ{ƊɠṪƲ‘           - code-page indices (call this M) [181,123,145,159,206,153]
        ɓ          - new dyadic chain - f(n,M):
         :         -   integer divide                [27700//181, 27700//123,...]
          Ḣ        -   head (call this x)            27700//181 = 153
              ɗ    -   last three links as a dyad - f(x, M):
           <       -     (x) less than? (M)          [1, 0, 0, 1, 1, 0]
            S      -     sum                         3
             ị     -     index into (M)              145
               ‘   -   increment                     146
                ×  -   multiply (M)                  [146×181, 146×123, ...]
                 Ḣ -   head                          146×181 = 26426 (机 - a Wood)

```

# Answer
> 9 votes
# JavaScript (Node.js), 39 bytes

I/O: Unicode codepoints as integers.

```
n=>Buffer("99944,777I")[n/543%62&15]<<9

```

Try it online!

## How?

### Step 1

We first look for some divisor \\$d\\$ such that the following element sets \\$S\_k\\$ are disjoint:

$$S\_k=\left\\{\left\lfloor\dfrac{n}{d}\right\rfloor,\\:C\_{min}(k)\le n\le C\_{max}(k)\right\\}$$

where \\$C\_{min}(k)\\$ and \\$C\_{max}(k)\\$ are the codepoint bounds of the \\$k\\$-th element.

Because the Unicode range of **Water** (U+6C34 to U+706A) is immediately followed by the Unicode range of **Fire** (U+706B to U+7229), there are not many possible options for \\$d\\$: it must be a proper divisor of \\$28779\\$ (0x706B), i.e. \\$d\in\\{1, 3, 53, 159, 181, 543, 9593\\}\\$. The best value in there that actually works is \\$d=543\\$.

### Step 2

We then look for some modulo chain that takes \\$n\\$ as input and turns it into an index corresponding to the counterpart element, using \\$n/543\\$. Instead of rounding the result towards zero, we force the last operation to a bitwise AND rather than a modulo.

A quick brute-force search leads to:

$$f(n)=((n/543)\bmod 62)\operatorname{and}15$$

### Step 3

Finally, we look for some multiplier \\$m\\$ such that there exists some \\$q\_k\\$ for each \\$k\\$ that satisfies:

$$C\_{min}(k)\le q\_k\times m\le C\_{max}(k)$$

One possible golf-friendly value is \\$m=512\\$, leading to the following table:

```
 element | hexa range      | q  | q*512 | as hexa
---------+-----------------+----+-------+---------
  Soil   | 0x571F - 0x58EA | 44 | 22528 | 0x5800
  Wood   | 0x6728 - 0x6B1F | 52 | 26624 | 0x6800
  Water  | 0x6C34 - 0x706A | 55 | 28160 | 0x6E00
  Fire   | 0x706B - 0x7229 | 57 | 29184 | 0x7200
  Metal  | 0x91D1 - 0x9484 | 73 | 37376 | 0x9200

```

The values of \\$q\\$ are encoded as the ASCII codes of `,479I`.

# Answer
> 6 votes
# Haskell, 51 bytes

```
w x="金火林土水"!!sum[1|c<-"朧氳灪釐",x>c]

```

Try it online!

# Answer
> 3 votes
# Charcoal, ~~28~~ 25 bytes

```
℅×⊘φ℅§6-L888   :::6÷℅Ｓ⁵⁴³

```

Try it online! Link is to verbose version of code. Explanation: Takes the ordinal of the input, integer divides by 543, cyclically indexes into the lookup table, takes the ordinal of that character, multiplies by 500, and converts back to Unicode.

I tried to reduce the size of the lookup table but although subtracting `3` and dividing by `654` allowed me to reduce it by 2 bytes it cost 3 bytes to subtract `3`, so it didn't help.

# Answer
> 2 votes
# Python 3.8 (pre-release), <sup>~~99~~</sup> 91 bytes

```
lambda c:{k:v for v,r in zip("水土木火金","钅爪火欠士")for k in range(ord(r))}[c]

```

Try it online!

-8 bytes thanks to @ovs

Input as an integer representing a unicode codepoint, output as a length-1 string.

---

# Python 3.8 (pre-release), 40 bytes

```
lambda n:b"MMMFF<JJJc"[n//543%62&15]*378

```

Try it online!

Shameless copy of @Arnauld's answer

---
Tags: code-golf, unicode
---


title: Total resistance from unit resistors

text:
# Question
Title: Total resistance from unit resistors
This problem is based on, A337517, the most recent OEIS sequence with the keyword "nice".

> \\$a(n)\\$ is the number of distinct resistances that can be produced from a circuit with exactly \\$n\\$ unit resistors.

The sequence begins `1, 2, 4, 9, 23, 57, 151, 427, 1263, 3823, 11724, 36048, 110953, 342079`.

The goal of this challenge is to write a program that takes a positive integer `n` and outputs the possible resistances that can be formed with \\$n\\$ unit resistors, written as fractions (or floats, ordered pairs representing fractions, or in another essentially similar format) as in the following:

```
f(3) = [3/1, 3/2, 2/3, 1/3]
     = [(3,1), (3,2), (2,3), (1,3)]
     = [[3,1], [3,2], [2,3], [1,3]]

```

This is a challenge, so shortest code wins. Your program needs to be able to handle inputs up to \\$n = 6\\$ on TIO.

### Examples

* With \\$n = 1\\$ resistor, the only possibility is a circuit with \\$1 \Omega\\$ total resistance.
* With \\$n = 2\\$ resistors, there are only \\$a(2) = 2\\$ possibilities:
    1. Resistors in sequence resulting in \\$2 \Omega\\$ total resistance.
    2. Resistors in parallel resulting in \\$\frac 12 \Omega\\$ total resistance.
* With \\$n = 3\\$ resistors, there are \\$a(3) = 4\\$ possibilities with resistances \\$3 \Omega, \frac 32 \Omega, \frac 23 \Omega\\$, and \\$\frac 13 \Omega\\$:
    1.
    2.
    3.
    4.

# Answer
> 9 votes
# Python 2, 734 bytes

```
import fractions as F,itertools as I
r=range
s=set
P=lambda G,p=[0]:[x for a,b in G if(p[-1]==a)*(1-(b in p))for x in(P(G,p+[b])if b-1else[p+[b]])]
def R(G):
 G+=tuple((b,a)for a,b in G);B=s(b for a,b in G);n=1+max(B)
 if s(G)-s(x for p in P(G)for e in zip(p,p[1:])for x in[e,e[::-1]])or len(B)-n:return 0
 M=[[0]*(n+1)for _ in B];M[0][0],M[0][n],M[1][1]=[F.Fraction(1)]*3
 for a,b in G:M[a][a]+=a>1;M[a][b]-=a>1
 for i in r(n):
	for j in r(i,n):
	 if M[j][i]:break
	M[i],M[j]=M[j],M[i];M[i]=[x/M[i][i]for x in M[i]]
	for j in r(n):M[j]=[a-(j!=i)*b*M[j][i]for a,b in zip(M[j],M[i])]
 return 1/sum(M[a][n]-M[b][n]for a,b in G if a==0)
f=lambda n:s(map(R,I.combinations_with_replacement([(a,b)for a in r(n)for b in r(a,n+1)],n)))-s([0])

```

Try it online!

I probably missed a bunch of golfing opportunities, but it's under 1000 bytes at least! I could have used SymPy for row reduction but went for a pure python answer instead.

Graphs are represented as lists of edges.

`P` generates all paths from vertex 0 to 1, used to determine if any resistors are unused (if they don't appear in any path).

`R` accepts a graph and returns the resistance between vertex 0 and 1, or `0` if the graph is invalid (it has unused edges/resistors or unused vertices). It does this by solving a system of linear equations of the voltages at each vertex.

`f` enumerates all graphs and generates the distinct resistances as a `set`. `0` from invalid graphs is removed.

Here are the results for 1 to 6 (as output by the footer in TIO):

```
f(1) = set([Fraction(1, 1)])
f(2) = set([Fraction(1, 2), Fraction(2, 1)])
f(3) = set([Fraction(3, 2), Fraction(3, 1), Fraction(1, 3), Fraction(2, 3)])
f(4) = set([Fraction(1, 4), Fraction(3, 4), Fraction(4, 1), Fraction(5, 2), Fraction(1, 1), Fraction(4, 3), Fraction(2, 5), Fraction(3, 5), Fraction(5, 3)])
f(5) = set([Fraction(3, 8), Fraction(7, 4), Fraction(4, 7), Fraction(5, 1), Fraction(5, 8), Fraction(7, 3), Fraction(5, 6), Fraction(2, 1), Fraction(3, 7), Fraction(8, 5), Fraction(1, 2), Fraction(6, 7), Fraction(7, 6), Fraction(1, 5), Fraction(1, 1), Fraction(5, 4), Fraction(4, 5), Fraction(7, 5), Fraction(6, 5), Fraction(7, 2), Fraction(2, 7), Fraction(8, 3), Fraction(5, 7)])
f(6) = set([Fraction(1, 2), Fraction(5, 9), Fraction(2, 1), Fraction(1, 3), Fraction(8, 13), Fraction(6, 1), Fraction(1, 1), Fraction(7, 12), Fraction(3, 11), Fraction(13, 5), Fraction(12, 5), Fraction(3, 1), Fraction(1, 6), Fraction(7, 11), Fraction(10, 3), Fraction(3, 4), Fraction(11, 13), Fraction(11, 10), Fraction(4, 9), Fraction(2, 9), Fraction(11, 5), Fraction(10, 7), Fraction(3, 10), Fraction(5, 6), Fraction(3, 2), Fraction(13, 7), Fraction(13, 11), Fraction(7, 10), Fraction(7, 9), Fraction(13, 8), Fraction(10, 9), Fraction(5, 4), Fraction(11, 8), Fraction(5, 11), Fraction(4, 5), Fraction(8, 11), Fraction(6, 11), Fraction(5, 13), Fraction(9, 10), Fraction(2, 3), Fraction(11, 4), Fraction(6, 5), Fraction(9, 4), Fraction(11, 7), Fraction(7, 13), Fraction(13, 6), Fraction(11, 3), Fraction(4, 3), Fraction(6, 13), Fraction(12, 7), Fraction(9, 5), Fraction(10, 11), Fraction(9, 7), Fraction(9, 2), Fraction(5, 12), Fraction(11, 6), Fraction(4, 11)])
```

---
Tags: code-golf, math, sequence, combinatorics, electrical-engineering
---


title: Is this a BST pre-order traversal?

text:
# Question
Title: Is this a BST pre-order traversal?
# Background

A **binary tree** is a rooted tree whose every node has at most two children.

A **labelled binary tree** is a binary tree whose every node is labelled with a positive integer; moreover, all labels are **distinct**.

A **BST** (binary search tree) is a labelled binary tree in which the label of each node is greater than the labels of all the nodes in its left subtree, and smaller than the labels of all the nodes in its right subtree. For instance, the following is a BST:

The **pre-order traversal** of a labelled binary tree is defined by the following pseudo-code.

```
function preorder(node)
    if node is null then
        return
    else
        print(node.label)
        preorder(node.left)
        preorder(node.right)

```

See the following image to get a better intuition:

The vertices of this binary tree are printed in the following order:

```
F, B, A, D, C, E, G, I, H

```

You can read more about BSTs here, and more about pre-order traversal here.

# Challenge

Given a list of integers \\$a\\$, your task is to determine whether there is a BST whose pre-order traversal prints exactly \\$a\\$.

## Input

* A non-empty **list** of distinct positive integers \\$a\\$.
* Optionally, the length of \\$a\\$.

## Output

* A **truthy** value if \\$a\\$ is the pre-order traversal of some BST.
* A **falsey** value otherwise.

# Rules

* **Standard rules** for valid submissions, I/O, loopholes apply.
* This is , so **shortest solution** (in bytes) wins. As usual, don't let ridiculously short solutions in golfy languages discourage you from posting a longer answer in your language of choice.
* This is not a rule, but your answer will be better received if it includes a link to test the solution and an explanation of how it works.

# Examples

```
Input                   ---->   Output

[1]                     ---->   True
[1,2,3,4]               ---->   True
[5,1,4,2,3]             ---->   True
[5,4,3,2,1,6,7,8,9]     ---->   True
[4,2,1,3,6,5,7]         ---->   True
[8,3,1,6,4,7,10,14,13]  ---->   True
[2,3,1]                 ---->   False
[6,3,2,4,5,1,8,7,9]     ---->   False
[1,2,3,4,5,7,8,6]       ---->   False
[3,1,4,2]               ---->   False

```

Check out this link (courtesy of Kevin Cruijssen) to have a visual look at the examples.

# Answer
> 12 votes
# JavaScript (Node.js), 49 bytes

```
a=>!a.some((p,i)=>a.some((q,j)=>q>p&a[j+=j>i]<p))

```

Try it online!

Using the fact that for array \\$a\_0 ... a\_{n-1}\\$, \\$a\\$ is the pre-order traversal of some BST iff \\$ \forall 0\le i\<j\<n; a\_i\<a\_{j-1} \implies a\_i\ 9 votes
# Jelly, 7 bytes

```
ŒPŒ¿€4ḟ

```

Try it online!

Returns `[4]` for traversals, otherwise `[]`.

Essentially uses tsh's algorithm: the "disqualifying" condition for a pre-order traversal is a subsequence of 3 elements that looks like **\[mid, high, low\]**. (For example, \[20, 30, 10\].)

We equivalently check for any subsequences of *any* length that have index **4** in their permutation lists, which are all lists sorted like **\[a1 … ak c d b\]** where the **ai** are sorted and **ai \< b \< c \< d**. (Each such list is disqualifying if we look at the last three elements, and each disqualifying list is obviously of this form.)

```
ŒP          All subsequences.
  Œ¿€       Permutation index of each.
     4ḟ     Set difference of {4} and this list.

```

# Proof

> ## A pre-order traversal contains no disqualifying subsequences
>
> Base case: **traversal(•)** is the empty list. ✓
>
> Induction: **traversal(t)** is: **t.root** ++ **traversal(t.left)** ++ **traversal(t.right)**.
>
> Let **\[a, b, c\]** be a subsequence hereof. We'll show **c \< a \
> * If **t.root = a**, then **c \< a \ * If **a, b, c ∈ t.left** or **a, b, c ∈ t.right**, use the induction hypothesis.
> * If **a ∈ t.left** and **c ∈ t.right** then **c \> a**.

#

> ## A list of distinct integers without disqualifying subsequences is the pre-order traversal of a BST
>
> If the list is empty, it's the traversal of the trivial BST •.
>
> If the list is **head** followed by **tail**:
>
> * Let **less** be the longest prefix of **tail** of elements less than **head**, and let **more** be the rest of the list.
> * Then **more\[1\] \> head**, and all other **more\[i\]** are greater than **head** too (otherwise **\[head, more\[1\], more\[i\]\]** would be a disqualifying subsequence).
> * Recurse: turn **less** and **more** into BSTs.
> * Now our list is the traversal of
>
> ```
>                  head
>                 /    \
>          BST(less)   BST(more),
>
> ```
>
> and this tree is a valid BST.

# Answer
> 5 votes
# Java 10, 94 bytes

```
a->{var r=0>1;for(int j=a.length-1,i;j-->0;)for(i=0;i<j;)r|=a[j]>a[i]&a[j+1]<a[i++];return!r;}

```

Port of *@tsh*' JavaScript answer.

Try it online.

**Explanation:**

```
a->{                      // Method with integer-array parameter and boolean return-type
  var r=0>1;              //  Result-boolean, starting at false
  for(int j=a.length-1,i;j-->0;)
                          //  Loop `j` in the range (length-1, 0]:
    for(i=0;i<j;)         //   Inner loop `i` in the range [0, j):
      r|=                 //    If any are true, change the result to true as well:
         a[j]>a[i]        //     The `j`'th item is larger than the `i`'th item
         &a[j+1]<a[i++];  //     And the `j+1`'th item is smaller than the `i`'th item
  return!r;}              //  After the nested loop, check if the boolean is still false

```

# Answer
> 5 votes
# Ruby, ~~46 40~~ 38 bytes

```
f=->r{a,*b=r;!a||b==b&[*0..a]|b&&f[b]}

```

Try it online!

This works by recursively taking the first element `a` as a pivot, and checking if the rest of the array can be split in two (using intersection and union: first remove all elements \>a, then add them again on the right and check if something has changed).

# Answer
> 3 votes
# Retina 0.8.2, 31 bytes

```
\d+
$*
M`\b((1+)1+,).*\1\2\b
^0

```

Try it online! Link includes test cases. Uses @tsh's algorithm. Explanation:

```
\d+
$*

```

Convert to unary.

```
M`\b((1+)1+,).*\1\2\b

```

Find numbers that lie between two subsequent consecutive descending numbers.

```
^0

```

Check that the number of matches is zero.

# Answer
> 3 votes
# 05AB1E, ~~15~~ 10 bytes

```
ŒεD{3.IÊ}P

```

Port of *@Lynn*'s Jelly answer.
-5 bytes thanks to *@Emigna*.

Try it online or verify all test cases.

**Explanation:**"

```
Œ             # Take all sublists of the (implicit) input-list
              #  i.e. [2,3,1] → [[2],[2,3],[2,3,1],[3],[3,1],[1]]
              #  i.e. [1,2,3,4]
              #   → [[1],[1,2],[1,2,3],[1,2,3,4],[2],[2,3],[2,3,4],[3],[3,4],[4]]
 ε      }     # Map each to:
  D           #  Duplicate the current sublist on the stack
   {          #  Sort the copy
              #   i.e. [2,3,1] → [1,2,3]
              #   i.e. [2,3,4] → [2,3,4]
    3.I       #  Get the 4th (3rd 0-indexed) permutation of this list
              #   i.e. [1,2,3] → [2,3,1]
              #   i.e. [2,3,4] → [3,4,2]
       Ê      #  Check that the lists are NOT equal
              #   i.e. [2,3,1] and [2,3,1] → 0 (falsey)
              #   i.e. [2,3,4] and [3,4,2] → 1 (truthy)
         P    # Check whether all are truthy (and output implicitly)
              #  i.e. [1,1,0,1,1,1] → 0 (falsey)
              #  i.e. [1,1,1,1,1,1,1,1,1,1] → 1 (truthy)

```

# Answer
> 3 votes
# Perl 6, 38 bytes

```
!*.combinations(3).grep:{[>] .[1,0,2]}

```

Try it online!

### Explanation

```
 *.combinations(3)  # All combinations of 3 elements a,b,c
!                 .grep:{            }  # Return false if check succeeds for any combination
                         [>] .[1,0,2]   # Check whether b>a>c, that is b>a and c<a

```

# Answer
> 3 votes
# Haskell, 50 bytes

```
f[]=1<3
f(x:r)|(a,b)<-span(<x)r=all(>x)b&&f a&&f b

```

Try it online!

# Answer
> 3 votes
# Scala (68 67 Bytes)

```
def%(i:Seq[Int])= !i.combinations(3).exists(c=>c(0)<c(1)&c(0)>c(2))

```

Try it online

Port of @nwellnhof's answer.

# Scala (122 103 bytes)

```
def f(i:Seq[Int]):Boolean=if(i.size<1)1>0 else{val(s,t)=i.tail.span(_<i(0));t.forall(_>i(0))&f(s)&f(t)}

```

Thanks to @Laikoni for the suggestions to make both solutions shorter.

Try it online

### Explanation:

1. slice (using Scala's `span`) the array using array's head as the slicing criteria.
2. Confirm that the first slice of the array is less than the head and the second slice is greater than the head.
3. recursively check that each slice also satisfies (2)

# Answer
> 2 votes
# Haskell, 41 bytes

```
f(h:t)=t==[]||all(>h)(snd$span(<h)t)&&f t

```

Try it online!

Uses Lynn's observation that it suffices to check that there's no subsequence of the for **mid..high..low**. This means that for each element `h`, the list of elements `t` that comes after is a block of elements `<h` followed by a block of elements `>h` (both blocks may be empty). So, the code checks that after we drop the prefix of elements `<h` in `t`, the remaining elements are all `>h`. Recursing checks this for each initial element `h` until the list is length 1.

A potential simplification is that it suffices to check for subpatterns **mid..high,low** where the last two are consecutive. Unfortunately, Haskell's doesn't have an short way to extract the last two elements, as can be done from the front with a pattern match `a:b:c`. I found a shorter solution that checks for **mid,high..low**, but this fails to reject inputs like `[3,1,4,2]`.

Formatted test cases taken from Laikoni.

# Answer
> 1 votes
# Japt, 14 bytes

```
d@sY ð_§XÃxÈ-Y

```

Japt Interpreter

Outputs `false` for BST, `true` for no BST.

Explanation:

```
d@                Run on each item X, return true if any aren't 0:
  sY                  Ignore the numbers before this index
     ð_§XÃ            Get the indexes of numbers less than or equal to X
                          If it is a BST, this list will be e.g. [0,1,2...]
            -Y        Subtract the position within the index list from each index
                          eg. [0,1,2] -> [0,0,0] , [0,1,4] -> [0,0,2]
          xÈ          Sum the resulting array

```

# Answer
> 1 votes
# Scala

All approaches are implementations of the rule shown by tsh.

# 109

```
l.zipWithIndex.foldLeft(1>0){case(r,(v,i))=>r&l.zip(l.tail).slice(i+1,l.size).forall(x=>l(i)>x._1|l(i)<x._2)}

```

# 101

```
(for(i<-l.indices)yield l.zip(l.tail).slice(i+1,l.size).forall(x =>l(i)>x._1|l(i)<x._2)).forall(x=>x)

```

# 98

```
l.indices.foldLeft(1>0)((r,i)=>r&(l.zip(l.tail).slice(i+1,l.size).forall(x=>l(i)>x._1|l(i)<x._2)))

```

# 78

```
(for(i<-l.indices;j<-i+1 to l.size-2)yield l(i)>l(j)|l(i)<l(j+1)).forall(x=>x)

```

If it must be a function and not just an expression then each line have to start with (17 bytes)

```
def%(l:Seq[Int])=

```

# Answer
> 1 votes
# Husk, 10 bytes

```
Λo≠4Ṡ€oPOQ

```

Try it online!

Same idea as Kevin Cruijssen's answer.

# Answer
> 0 votes
# Oracle SQL, 177 bytes

```
with r(i,v)as(select rownum,value(t)from table(a)t)
select nvl(min(case when r.v<p.l and r.v>p.v then 0end),1)from r,(select i,lag(v)over(order by i)l,v from r)p where r.i+1<p.i

```

Since there is no boolean type in Oracle SQL, query returns either 1 or 0.

# Oracle SQL 12c, 210 bytes

```
with function f(n ku$_objnumset,i int)return int as begin return n(i);end;
select min(case when f(c,1)>f(c,2)or f(c,1)<f(c,3)then 1else 0end)from(select value(t)c from table(powermultiset_by_cardinality(a,3))t)

```

It's not possible access element of the array in SQL the same way as in PL/SQL - i.e. a(i), thus function `f` was declared in `with clause` for that purpose. Otherwise solution would have been much shorter.

Other limitations

* throws an exception for arrays shorter than 3 elements (instead of returning 1)
* there is an assumption that powermultiset\_by\_cardinality preserves order even though it's not explicitly stated in the documentation

**sqlplus** listing

```
SQL> set heading off
SQL> with r(i,v)as(select rownum,value(t)from table(ku$_objnumset(6,3,2,4,5,1,8,7,9))t)
  2  select nvl(min(case when r.v<p.l and r.v>p.v then 0end),1)from r,
  3  (select i,lag(v)over(order by i)l,v from r)p where r.i+1<p.i
  4  /

                                            0

SQL> with function f(n ku$_objnumset,i int)return int as begin return n(i);end;
  2  select min(case when f(c,1)>f(c,2)or f(c,1)<f(c,3)then 1else 0end)
  3  from(select value(t)c from table(powermultiset_by_cardinality(ku$_objnumset(6,3,2,4,5,1,8,7,9),3))t)
  4  /

                                                     0

SQL> with r(i,v)as(select rownum,value(t)from table(ku$_objnumset(8,3,1,6,4,7,10,14,13))t)
  2  select nvl(min(case when r.v<p.l and r.v>p.v then 0end),1)from r,
  3  (select i,lag(v)over(order by i)l,v from r)p where r.i+1<p.i
  4  /

                                            1

SQL> with function f(n ku$_objnumset,i int)return int as begin return n(i);end;
  2  select min(case when f(c,1)>f(c,2)or f(c,1)<f(c,3)then 1else 0end)
  3  from(select value(t)c from table(powermultiset_by_cardinality(ku$_objnumset(8,3,1,6,4,7,10,14,13),3))t)
  4  /

                                                     1

```

Online verification apex.oracle.com

**Update**

# Oracle SQL, 155 bytes

```
with r(i,v)as(select rownum,value(t)from table(a)t)select nvl(min(case when a.v<b.v and a.v>c.v then 0end),1)r from r a,r b,r c where a.i<b.i and b.i+1=c.i

```

# Answer
> 0 votes
# **C, 823 bytes** (not counting whitespace characters); 923 bytes (including whitespace)

```
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct tree
{struct tree * left;struct tree * right;int val;}tree;static int * test_p = 0;
void insert_root(tree ** root, int in)
{if (*root == NULL){*root = (tree *)calloc(1,sizeof(tree));(*root)->val = in;return;}else if (in < (*root)->val){insert_root(&((*root)->left),in);}else{insert_root(&((*root)->right),in);}}
void preorder(tree * root)
{if ( root == 0x0 ) { return; }*test_p++ = root->val;preorder(root->left);preorder(root->right);}
int main(int argc, char ** argv)
{int test_list[argc-1];memset(test_list,0,argc*sizeof(int));test_p = test_list;tree * root = (tree *)calloc(1,sizeof(tree));root->val = strtol(argv[1],0x0,10);int i = 1;while ( argv[++i] != 0x0 ){insert_root(&root,strtol(argv[i],0x0,10));}preorder(root);test_p = test_list;i = 1;while ( ( i < argc ) ){if ( *test_p != strtol(argv[i],0x0,10) ){return 0;}test_p++;i++;}return 1;}

```

The readable version of the program is below:

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

typedef struct tree
{
    struct tree * left;

    struct tree * right;

    int val;

} tree;

static int * test_p = 0;

void insert_root(tree ** root, int in)
{
  if (*root == NULL)
  {
    *root = (tree *)calloc(1,sizeof(tree));

    (*root)->val = in;

    return;
  }

  else if (in < (*root)->val)
  {
    insert_root(&((*root)->left),in);
  }

  else
  {
    insert_root(&((*root)->right),in);
  }
}

void preorder(tree * root)
{
    if ( root == 0x0 ) {  return; }

        *test_p++ = root->val;

        preorder(root->left);

        preorder(root->right);

}

int main(int argc, char ** argv)
{
    int test_list[argc-1];

    memset(test_list,0,argc*sizeof(int));

    test_p = test_list;

    tree * root = (tree *)calloc(1,sizeof(tree));

    root->val = strtol(argv[1],0x0,10);

    int i = 1;

    while ( argv[++i] != 0x0 )
    {
        insert_root(&root,strtol(argv[i],0x0,10));
    }

    preorder(root);

    test_p = test_list;

    i = 1;

    while ( ( i < argc ) )
    {
        if ( *test_p != strtol(argv[i],0x0,10) )
        {
            return 0;
        }

        test_p++;

        i++;
    }

    return 1;
}

```

The main method in this program reads the list of numbers that are (allegedly) a legitimate preorder traversal.

The function insert\_root that is called inserts the integers into a binary search tree where previous nodes contain lesser values and next nodes contain larger int values.

The function preorder(root) traverses the tree in a preorder traversal and simultaneously concatenates each integer the algorithm comes across to the int array **test\_list**.

A final while loop tests if each of the int values in the **stdin** list and those in **test\_list** are equivalent at each index. If there is a list element from **stdin** that fails to match the corresponding element in test\_list at the respective index, the main function **returns 0.** Else the main method **returns 1**.

To determine what main returned, type **echo $status** into the bash terminal. BASH will either print out a 1 or a 0.

# Answer
> 0 votes
# Husk, 9 bytes

```
¬ṁ§=Oṙ2Ṗ3

```

Try it online!

Uses 'disqualifying condition' of any subsequence mid...high...low from tsh's and Lynn's answers.

```
¬ṁ§=Oṙ2Ṗ3
       Ṗ3   # consider all subsequences of length 3:
     ṙ2     # check whether rotating 2 to the left
  §=O       # is the same as sorting;
¬ṁ          # total of subsequences that satisfy this should be zero

```

---
Tags: code-golf, decision-problem, binary-tree
---


title: Gluing tetrahedra together

text:
# Question
Title: Gluing tetrahedra together
(This challenge exists to extend sequence A276272 in the On-Line Encyclopedia of Integer Sequences, and perhaps create a new OEIS sequence1.)

This is a , which will have you write code to compute as many terms of this sequence as possible.

---

### Background

A *polytet* is a kind of polyform which is constructed by gluing regular tetrahedra together face-to-face in such a way that none of the interiors of the tetrahedra overlap. These are counted up to rotation in 3-space but *not* reflection, so if a particular shape is chiral it is counted twice: once for itself and once for its mirror image.

* \\$A267272(1) = 1\\$ because there is one such configuration you can make out one tetrahedron.
* \\$A267272(2) = 1\\$ because due to symmetry of the tetrahedra, gluing to a face is the same as any other face. This gives you the triangular bipyramid.
* \\$A267272(3) = 1\\$ because the triangular bipyramid itself is symmetric, so adding a tetrahedron to any face results in a biaugmented tetrahedron.
* \\$A267272(4) = 4\\$ because there are three distinct ways to add a tetrahedron to the biaugmented tetrahedron, and one is chiral (so it's counted twice). These are shown in the animated GIFs above.
* \\$A267272(5) = 10\\$ as shown in George Sicherman's catalog. Three are chiral and four are achiral.

---

### Rules

Run your code for as long as you'd like. The winner of this challenge will be the user who posts the most terms of the sequence, along with their code. If two users post the same number of terms, then whoever posts their last term earliest wins.

(Once more terms are computed, then whoever computed the code can add the new terms to the OEIS or I can add them and list the contributor if he or she desires.)

---

1 A sequence which (presumably) isn't already in the OEIS is the number of polytets up to reflection (i.e. chiral compounds are counted once, not twice). The first few values of this alternative sequence can be found in the George Sicherman link.

# Answer
> 9 votes
# Rust, 11 (hopefully correct) terms

```

use ::std::ops::{Add, Sub, Mul};
use ::std::rc::Rc;
use ::std::hash::{Hash, Hasher};
use ::std::collections::HashSet;
use ::std::iter;
use ::std::fmt::{self, Formatter, Display};
use ::std::time::Instant;

type Coord = i128;

#[derive(Copy, Clone, PartialEq, Eq, Debug)]
struct Vec3([Coord; 3]);

impl Vec3 {
    fn dot(self, other: Vec3) -> Coord {
        self.0.iter().zip(other.0.iter()).map(|(a, b)| a * b).sum()
    }
}

impl Display for Vec3 {
    fn fmt(&self, f: &mut Formatter) -> fmt::Result {
        write!(f, "({}, {}, {})", self.0[0], self.0[1], self.0[2])
    }
}

impl Mul<Vec3> for Coord {
    type Output = Vec3;

    fn mul(self, mut vec: Vec3) -> Vec3 {
        for i in &mut vec.0 {
            *i *= self;
        }
        vec
    }
}

impl Add for Vec3 {
    type Output = Vec3;

    fn add(mut self, other: Vec3) -> Vec3 {
        for (i, n) in self.0.iter_mut().enumerate() {
            *n += other.0[i];
        }
        self
    }
}

impl Sub for Vec3 {
    type Output = Vec3;

    fn sub(self, other: Vec3) -> Vec3 {
        self + (-1 * other)
    }
}

#[derive(Clone, Debug)]
struct Tetrahedron([Vec3; 4]);

impl Default for Tetrahedron {
    fn default() -> Tetrahedron {
        Tetrahedron([
            Vec3([-1, -1, -1]),
            Vec3([-1,  1,  1]),
            Vec3([ 1, -1,  1]),
            Vec3([ 1,  1, -1]),
        ])
    }
}

impl Display for Tetrahedron {
    fn fmt(&self, f: &mut Formatter) -> fmt::Result {
        write!(f, "Tetrahedron({}, {}, {}, {})", self.0[0], self.0[1], self.0[2], self.0[3])
    }
}

impl Tetrahedron {
    fn collides(&self, other: &Tetrahedron) -> bool {
        let mut othervecs = [3 * self.0[1], 3 * self.0[2], 3 * self.0[3]];
        let sum = self.0[0] + self.0[1] + self.0[2] + self.0[3];
        let mut same = 0;

        for (i, &vec) in self.0.iter().enumerate() {
            let sum = sum - vec;
            let vec = 3 * vec;
            let through = vec - sum;
            for (j, &u) in other.0.iter().enumerate() {
                let u = 3 * u;
                if u == vec { same += 1 }
                let up = (sum - u).dot(through);
                for &v in &other.0[j+1..] {
                    let v = 3 * v;
                    let edge = v - u;
                    let ep = edge.dot(through);

                    if up.signum() != ep.signum() || up.abs() >= ep.abs() {
                        continue
                    }

                    let intersection = ep * u + up * edge;
                    if othervecs.iter().enumerate().all(|(i, &ov)| {
                        let mid = othervecs[(i+1)%3] + othervecs[(i+2)%3];
                        let ov = 2 * ov - mid;
                        (2 * intersection - ep * mid).dot(ep * ov) > 0
                    }) {
                        return true
                    }
                }
            }

            if i != 3 { othervecs[i] = vec; }
        }
        if same == 4 { panic!("EQUAL TETRAHEDRA IN .collides()"); }
        false
    }

    // Mirroring also scales by 3
    fn mirror(&self, i: usize) -> Tetrahedron {
        let mut sum = Vec3([0; 3]);
        for (j, &vec) in self.0.iter().enumerate() {
            if j != i { sum = sum + vec; }
        }

        let mut copy = self.clone();
        copy.scale();

        copy.0[i] = 2 * sum - copy.0[i];
        copy.swap(i, 3);
        copy.rotate_left(i);

        copy
    }

    fn scale(&mut self) {
        for vec in self.0.iter_mut() {
            *vec = 3 * *vec;
        }
    }

    fn rotate_left(&mut self, n: usize) {
        self.0[..3].rotate_left(n)
    }

    fn swap(&mut self, a: usize, b: usize) {
        self.0.swap(a, b)
    }

    fn reverse(&mut self) {
        self.0.reverse()
    }
}

type EndpointIter<'a> = Box<dyn Iterator<Item = Endpoint> + 'a>;

#[derive(Debug, Clone)]
struct Endpoint {
    tree: Rc<TetraTree>,
    hedron: Rc<Tetrahedron>,
}

impl Endpoint {
    fn iter_endpoints(&self) -> EndpointIter {
        let mut hedron = Rc::clone(&self.hedron);
        //Rc::make_mut(&mut hedron).swap(0, 3);
        Rc::make_mut(&mut hedron).reverse();

        Box::new(self.clone().into_iter_directions()
            .chain(self.tree.iter_endpoints(
                Rc::new(TetraTree {
                    subtrees: [None, None, None],
                    hedron,
                })
            ))
        )
    }

    fn into_iter_directions(self) -> EndpointIter<'static> {
        Box::new(iter::successors(Some(self), |this| {
            let mut this = this.clone();
            Rc::make_mut(&mut this.tree).rotate_left(1);
            Rc::make_mut(&mut this.hedron).0[1..].rotate_left(1);
            Some(this)
        }).take(3))
    }

    fn iter_extensions(&self) -> EndpointIter {
        let mut tree = self.tree.as_ref().clone();
        tree.scale();

        let mut hedron = self.hedron.as_ref().clone();
        //hedron.swap(0, 3);
        hedron.reverse();
        hedron.scale();

        Box::new(Endpoint {
            tree: Rc::new(tree),
            hedron: Rc::clone(&self.hedron),
        }.into_iter_directions().filter_map(|endpoint| {
            let mut new = endpoint.hedron.mirror(3);
            new.swap(0, 3);
            if endpoint.tree.collides(&new) {
                None
            } else {
                let mut hedron = endpoint.hedron;
                Rc::make_mut(&mut hedron).scale();

                Some(Endpoint {
                    tree: Rc::new(TetraTree {
                        subtrees: [Some(endpoint.tree), None, None],
                        hedron,
                    }),
                    hedron: Rc::new(new),
                })
            }
        }).chain(self.tree.iter_extensions(Rc::new(TetraTree {
            subtrees: [None, None, None],
            hedron: Rc::new(hedron),
        }))))
    }

    fn iter_tetrahedra<'a>(&'a self)
      -> Box<dyn Iterator<Item = &Tetrahedron> + 'a> {
        Box::new(
          iter::once(self.hedron.as_ref()).chain(self.tree.iter_tetrahedra())
        )
    }
}

impl Default for Endpoint {
    fn default() -> Endpoint {
        Endpoint::from(Tetrahedron::default())
    }
}

impl From<Tetrahedron> for Endpoint {
    fn from(mut hedron: Tetrahedron) -> Endpoint {
        let mirrored = hedron.mirror(0);
        hedron.scale();

        Endpoint {
            tree: Rc::new(TetraTree {
                subtrees: [None, None, None],
                hedron: Rc::new(mirrored),
            }),
            hedron: Rc::new(hedron),
        }
    }
}

impl Hash for Endpoint {
    fn hash<H: Hasher>(&self, hasher: &mut H) {
        let mut stuff: Vec<_> = self.tree.hash_helper(1).collect();
        stuff.push(self.tree.len());
        stuff.sort();
        stuff.hash(hasher);
    }
}

impl PartialEq for Endpoint {
    fn eq(&self, other: &Endpoint) -> bool {
        self.iter_endpoints().any(|ep| ep.tree == other.tree)
    }
}

impl Eq for Endpoint {}

#[derive(Debug, Clone)]
struct TetraTree {
    subtrees: [Option<Rc<TetraTree>>; 3],
    hedron: Rc<Tetrahedron>,
}

impl TetraTree {
    fn iter_endpoints<'x>(&'x self, behind: Rc<TetraTree>) -> EndpointIter<'x> {
        let mut iterator = self.subtrees.iter().enumerate()
          .filter_map(|(i, opt)| opt.as_ref().map(|some| (i, some)));

        if let Some(first) = iterator.next() {
            let closure = move |(i, subtree): (usize, &'x Rc<TetraTree>)| -> EndpointIter<'x> {
                let mut behind = behind.as_ref().clone();
                behind.rotate_left(3-i);

                let mut this = self.clone();
                this.rotate_left(i);

                Rc::make_mut(&mut this.hedron).reverse();

                this.subtrees.swap(1, 2);
                this.subtrees[0] = Some(Rc::new(behind));

                for (j, subtree) in this.subtrees.iter_mut().enumerate().skip(1)
                  .filter_map(|(j, s)| s.as_mut().map(|s| (j, s))) {
                    Rc::make_mut(subtree).rotate_left(j);
                }

                subtree.iter_endpoints(Rc::new(this))
            };
            Box::new(closure(first).chain(iterator.flat_map(closure)))
        } else {
            let mut hedron = self.hedron.as_ref().clone();
            //hedron.swap(0, 3);
            hedron.reverse();
            Endpoint {
                tree: Rc::clone(&behind),
                hedron: Rc::new(hedron),
            }.into_iter_directions()
        }
    }

    fn rotate_left(&mut self, i: usize) {
        self.subtrees.rotate_left(i);
        Rc::make_mut(&mut self.hedron).rotate_left(i);
    }

    fn collides(&self, hedron: &Tetrahedron) -> bool {
        self.hedron.collides(hedron) ||
          self.subtrees.iter()
            .filter_map(Option::as_ref)
            .any(|subtree| subtree.collides(hedron))
    }

    fn scale(&mut self) {
        for subtree in self.subtrees.iter_mut().filter_map(Option::as_mut) {
            Rc::make_mut(subtree).scale();
        }
        Rc::make_mut(&mut self.hedron).scale();
    }

    fn iter_extensions(&self, behind: Rc<TetraTree>) -> EndpointIter {
        Box::new(self.subtrees.iter().enumerate().flat_map(move |(i, next)| {
            let mut behind = behind.as_ref().clone();
            behind.rotate_left(3-i);

            let mut this = self.clone();
            this.rotate_left(i);

            let hedron = Rc::make_mut(&mut this.hedron);
            hedron.reverse();

            this.subtrees.swap(1, 2);
            this.subtrees[0] = Some(Rc::new(behind));

            for (j, subtree) in this.subtrees.iter_mut().enumerate().skip(1)
              .filter_map(|(j, s)| s.as_mut().map(|s| (j, s))) {
                let subtree = Rc::make_mut(subtree);
                subtree.scale();
                subtree.rotate_left(j);
            }

            if let Some(next) = next {
                hedron.scale();
                next.iter_extensions(Rc::new(this))
            } else {
                let mut mirrored = hedron.mirror(3);
                mirrored.swap(0, 3);
                hedron.scale();

                if this.collides(&mirrored) {
                    Box::new(iter::empty()) as EndpointIter
                } else {
                    Box::new(iter::once(Endpoint {
                        tree: Rc::new(this),
                        hedron: Rc::new(mirrored),
                    }))
                }
            }
        }))
    }

    fn iter_tetrahedra<'a>(&'a self)
      -> Box<dyn Iterator<Item = &Tetrahedron> + 'a> {
        Box::new(iter::once(self.hedron.as_ref()).chain(
          self.subtrees.iter()
            .filter_map(Option::as_deref)
            .flat_map(TetraTree::iter_tetrahedra)
        ))
    }

    fn len(&self) -> usize {
        1usize + self.subtrees.iter()
              .filter_map(Option::as_deref).map(TetraTree::len).sum::<usize>()
    }

    fn hash_helper<'a>(&'a self, behind: usize)
      -> Box<dyn Iterator<Item = usize> + 'a> {
        let sub: Vec<_> = self.subtrees.iter().filter_map(Option::as_deref)
          .map(|a| (a, a.len())).collect();
        let sum = sub.iter()
          .map(|&(_, len)| len).sum::<usize>() + behind + 1;
        Box::new(iter::once(behind).chain(
            sub.into_iter().flat_map(move |(sub, len)|
                        iter::once(len).chain(sub.hash_helper(sum - len)))
        ))
    }
}

impl PartialEq for TetraTree {
    fn eq(&self, rhs: &TetraTree) -> bool {
        self.subtrees == rhs.subtrees
    }
}

impl Eq for TetraTree {}

fn main() {
    let verbose = std::env::args().skip(1).any(|arg| arg == "-v");
    let begin = Instant::now();

    println!("1: 1 [{}ms]", begin.elapsed().as_millis());
    if verbose {
        println!("{}\n--", Tetrahedron::default());
    }

    let mut polytets = HashSet::new();
    polytets.insert(Endpoint::default());

    for i in 2.. {
        println!("{}: {} [{}ms]", i, polytets.len(), begin.elapsed().as_millis());

        if verbose {
            for polytet in &polytets {
                for hedron in polytet.iter_tetrahedra() {
                    println!("{}", hedron);
                }
                println!("--");
            }
        }

        polytets = polytets.iter()
          .flat_map(Endpoint::iter_extensions)
          .collect();
    }
}

```

Try it online! The footer contains some compatability implementations because TIO's Rust is a little old. (This has already been reported and added to the list.)

Output:

```
1: 1 [0ms]
2: 1 [0ms]
3: 1 [2ms]
4: 4 [8ms]
5: 10 [35ms]
6: 39 [139ms]
7: 164 [738ms]
8: 767 [4328ms]
9: 3656 [31298ms]
10: 18186 [287871ms]
11: 91532 [3154716ms]

```

As you can see, it also reports how long it took. (These are cumulated times.) You can use the `-v` option to list all tetrahedra for each polytet.

I don't really have a good way of verifying the results beyond A267272(5). I hope it works, but I'm not sure.

The idea is that we store the polytet as a tree of tetrahedra that also encodes orientation. But for collision detection we need actual tetrahedra. We start with the tetrahedron with vertices (-1, -1, -1), (-1, 1, 1), (1, -1, 1), (1, 1, -1) and scale all tetrahedra by 3 for every term. This avoids the need for fractions.

Can probably be made faster, but I don't know how.

---
Tags: code-challenge, geometry, combinatorics, polyomino
---


title: Square a Number my Way

text:
# Question
Title: Square a Number my Way
People keep telling me that the square of a number is the number multiplied by itself. This is obviously false. The correct way to square a number is to make it into a square, by stacking it on top of itself a number of times equal to the number of digits it has, and then reading all the numbers from the resultant square, both horizontally (from left to right only) and vertically (from up to down only), and then adding them together. So, for the number 123, you first create the square:

```
123
123
123

```

Then you take all of the rows and columns from the square, and add them together:

```
123+123+123+111+222+333

```

Which gives us a result of `1035`.

For negative numbers, you stack normally (remember that you only count the number of *digits*, so the negative sign is not included in the length), and then read the horizontal numbers normally (with negative signs), and then ignore the negative signs for the vertical numbers. So, for the number `-144` we get the square:

```
-144
-144
-144

```

Which gives us `-144-144-144+111+444+444`, which equals `567`

For numbers with only one digit, the square is always equal to the number doubled (read once horizontally and once vertically). So `4` gives us

```
4

```

Which gives us `4+4`, which equals `8`.

For numbers with decimal parts, stack normally (remember that only *digits* are counted in the number of times you stack the number, and therefore the decimal point is not counted), and ignore the decimal symbols when reading the vertical numbers. For example, the number `244.2` gives us

```
244.2
244.2
244.2
244.2

```

Which gives us `244.2+244.2+244.2+244.2+2222+4444+4444+2222`, which equals `14308.8`.

Fractional or complex numbers cannot be squared.

## Your Task:

I'm tired of squaring numbers my way by hand, so I've decided to automate the process. Write me a program or function that takes a float or string, whichever you prefer, as input and returns the result of squaring it my way.

## Examples:

```
123    -> 1035
388    -> 3273
9999   -> 79992
0      -> 0
8      -> 16
-6     -> 0
-25    -> 27
-144   -> 567
123.45 -> 167282.25
244.2  -> 14308.8
2      -> 4
-0.45  -> 997.65
0.45   -> 1000.35

```

## Scoring:

My hands are getting cramped from writing out all those squares, and my computer doesn't support copy/paste, so the entry with the least amount of code for me to type (measured in bytes for some reason?) wins!

# Answer
> 8 votes
# 05AB1E, 7 bytes

```
þSDg×+O

```

Try it online!

Explanation

```
þSDg×+O Implicit input
þ       Keep digits
 S      Get chars
  D     Duplicate
   g    Length
    ×   Repeat string(s)
     +  Add (implicit input added to all elements)
      O Sum

```

# Answer
> 7 votes
# Jelly,  ~~13~~  12 bytes

```
fØDẋ€L$ŒV+VS

```

A monadic link accepting a list of characters (a well-formed decimal number, the single leading zero being a requirement for **-1 \< n \< 1**) and returning a number.

**Try it online!**

14 bytes to accept and return numbers (input limited at **+/-10<sup>-5</sup>** by `ŒṘ`): `ŒṘfØDẋ€L$ŒV+⁸S`.

### How?

```
fØDẋ€L$ŒV+VS - Link: list of characters         e.g. "-0.45"
 ØD          - yield digit characters                "0123456789"
f            - filter keep                           "045"
      $      - last two links as a monad:
     L       -   length (number of digit characters) 3
   ẋ€        -   repeat list for €ach digit          ["000","444","555"]
       ŒV    - evaluate as Python code (vectorises)  [0,444,555]
          V  - evaluate (the input) as Jelly code    -0.45
         +   - addition (vectorises)                 [-0.45,443.55,554.55]
           S - sum                                   997.65

```

# Answer
> 6 votes
## Haskell, ~~59~~ 56 bytes

```
f s|l<-filter(>'.')s=0.0+sum(read<$>(s<$l)++[c<$l|c<-l])

```

The input is taken as a string.

Try it online!

How it works

```
l<-filter(>'.')s      -- let l be the string of all the numbers of the input string
f s   = 0.0 + sum     -- the result is the sum of (add 0.0 to fix the type to float)
   read<$>            -- turn every string of the following list into a number
   s<$l               -- length of l times the input string followed by
   [c<$l|c<-l]        -- length of l times c for each c in l

```

# Answer
> 5 votes
# Japt v2, 16 bytes

```
o\d
l
¬xpV +V*Ng

```

Test it online!

### Explanation

```
o\d    First line: Set U to the result.
o      Keep only the chars in the input that are
 \d      digits. (literally /\d/g)

l    Second line: Set V to the result.
l    U.length

¬xpV +V*Ng    Last line: implicitly output the result.
¬             Split U into chars.
 x            Sum after
  pV            repeating each V times.
     +V*Ng    Add V * first input (the sum of the horizontals) to the result.

```

# Answer
> 4 votes
# C# (.NET Core), ~~150~~ ~~141~~ 133 bytes

~~*Saved 9 bytes thanks to @TheLethalCoder*~~
*Saved another 8 bytes thanks to @TheLethalCoder*

```
a=>{var c=(a+"").Replace(".","").Replace("-","");int i=0,l=c.Length;var r=a*l;for(;i<l;)r+=int.Parse(new string(c[i++],l));return r;}

```

Try it online!

Takes a string as an input and outputs the 'squared' number as a float.

---

This code follows the following algorithm:

1. Create a new string from the input, but without the decimal points and symbols, so we can get our length and the numbers for the columns from there.
2. Calculate the input times the length of the string we created at point 1.
3. For each column in our 'square', create a new string with the column number and the row length and add it to our result.

Example:

Input: `-135.5`

1. If we replace decimal points and symbols we get the string `1355`, which has a length of `4`.
2. The input times 4: `-135.5 * 4 = -542`.
3. Now we create new strings for each column, parse them and add them to our result:
`1111`, `3333`, `5555`, `5555`.

If we sum these numbers up we get `15012`, which is exactly what our program will output.

# Answer
> 3 votes
# JavaScript, ~~75~~ 62 bytes

```
a=>(b=a.match(/\d/g)).map(b=>a+=+b.repeat(c),a*=c=b.length)&&a

```

Try it online

*-2 bytes thanks to Arnauld*
*-5 bytes thanks to Shaggy* (I though the function must receive a number, but now I see that lot of other answers receive string too)

# Answer
> 3 votes
# Python 3, ~~95 94 87 85~~ 84 bytes

```
def f(i):l=[x for x in i if"/"<x];k=len(l);print(k*float(i)+sum(int(x*k)for x in l))

```

Test Suite.

# Python 3, 78 bytes

```
lambda x:sum(float(i*len(z))for z in[[i for i in str(x)if"/"<i]]for i in[x]+z)

```

Test Suite.

The second approach is a port to Python 3 inspired by @officialaimm's solution.

# Answer
> 3 votes
# Python 2, ~~81~~ 74 bytes

***-7 bytes thanks to @Mr. Xcoder***: `'/'<i`

* Takes in integer or float, returns float.

```
lambda x:sum(float(i*len(z))for z in[[i for i in`x`if"/"<i]]for i in[x]+z)

```

Try it online!

## Explanation:

Say `123.45` is given as input. `[i for i in`x`if"/"<x]` gives a list of stringified integers `['1','2','3','4','5']` (which is also `z`). Now we iterate through `[x]+z` i.e. `[123.45,'1','2','3','4','5']`, multiplying each element by `len(z)`, here `5` and converting each to a Float (so that strings also convert accordingly), yielding `[617.25,11111.0,22222.0,33333.0,44444.0,55555.0]`. Finally we calculate the `sum(...)` and obtain `167282.25`.

# Answer
> 3 votes
# Brachylog, 23 bytes

```
{∋ịṫ}ᶠ⟨≡zl⟩j₎ᵐ;[?]zcịᵐ+

```

Try it online!

Brachylog doesn't go well with floats...

Explanation:

```
{∋ịṫ}ᶠ⟨≡zl⟩j₎ᵐ;[?]zcịᵐ+ Takes string (quoted) input, with '-' for the negative sign
     ᶠ                  Return all outputs (digit filter)
{   }                    Predicate (is digit?)
 ∋                        An element of ? (input)
  ị                       Convert to number (fails if '-' or '.')
   ṫ                      Convert back to string (needed later on)
      ⟨   ⟩             Fork
       ≡                 Identity
         l               Length
                        with
        z                Zip
             ᵐ          Map
            ₎            Subscript (optional argument)
           j              Juxtapose (repeat) (this is where we need strings)
              ;         Pair with literal
               [ ]       List
                ?         ?
                  z     Zip
                   c    Concatenate (concatenate elements)
                     ᵐ  Map
                    ị    Convert to number
                      + Add (sum elements)

```

# Answer
> 3 votes
## Husk, 15 bytes

```
§+ȯṁrfΛ±TṁrSR#±

```

Takes a string and returns a number. Try it online!

## Explanation

It's a bit annoying that the built-in parsing function `r` gives parse errors on invalid inputs instead of returning a default value, which means that I have to explicitly filter out the columns that consist of non-digits. If it returned 0 on malformed inputs, I could drop `fΛ±` and save 3 bytes.

```
§+ȯṁrfΛ±TṁrSR#±  Implicit input, e.g. "-23"
             #±  Count of digits: 2
           SR    Repeat that many times: ["-23","-23"]
         ṁr      Read each row (parse as number) and take sum of results: -46
  ȯṁrfΛ±T        This part is also applied to the result of SR.
        T        Transpose: ["--","22","33"]
     fΛ±         Keep the rows that contain only digits: ["22","33"]
   ṁr            Parse each row as number and take sum: 55
§+               Add the two sums: 9

```

# Answer
> 3 votes
# Perl 5, ~~37~~ 33 + 1 (-p) = ~~38~~ 34 bytes

```
$_*=@n=/\d/g;for$\(@n){$_+=$\x@n}

```

Try it online!

*Used some tricks from Dom's code to shave 4 bytes*

**Explained:**

```
@n=/\d/g;    # extract digits from input
$_*=@n;      # multiply input by number of digits
for$\(@n){   # for each digit:
  $_+=       # add to the input
  $\x@n}     # this digit, repeated as many times as there were digits
             # taking advantage of Perl's ability to switch between strings
             # and numbers at any point

```

# Answer
> 2 votes
# Jelly, 17 bytes

```
ŒṘfØDẋ€L©$ŒV;ẋ®$S

```

Try it online!

# Answer
> 2 votes
# Pyth, 18 bytes

```
s+RvQsM*RF_lB@jkUT

```

Try it here.

# Answer
> 2 votes
# Pyth, ~~21~~ 20 bytes

```
K@jkUTQ+smv*lKdK*lKv

```

Test suite.

Uses a completely different approach from @EriktheOutgolfer's answer, which helped me golf 1 byte in chat, from 22 to 21.

---

# Explanation

```
K@jkUTQ+s.ev*lKbK*lKv

K@jkUTQ                   - Filters the digits and assigns them to a variable K.
         m                - Map. Iterated through the digits with a variable d
           v              - Evaluate (convert to float).
            *lKd          - Multiplies each String digit by the length of K.
        s                 - Sum
       +                  - Sum
                 *lKvQ    - Multipies the number  by the length of the digits String

```

# Answer
> 2 votes
# Octave, ~~100~~ 82 bytes

Thanks a lot @TomCarpenter for teaching me that assignments have a return value and saving me `18` bytes!

```
@(v)(n=nnz(s=strrep(num2str(abs(v)),'.','')-'0'))*v+sum(sum(s'*logspace(0,n-1,n)))

```

Try it online!

### Ungolfed/Explanation

```
function f=g(v)
  s=strrep(num2str(abs(v)),'.','')-'0';  % number to vector of digits (ignore . and -)
  n=nnz(s);                              % length of that vector
  f=n*v+sum(sum(s'*logspace(0,n-1,n)))   % add the number n times and sum the columns of the square
end

```

The way this works is that we basically need to add the number itself `n` times and then add the sum of the columns. Summing `s' * logspace(0,n-1,n)` achieves the sum of columns, for example if `v=-123.4` that matrix will be:

```
[ 1     10    100   1000;
  2     20    200   2000;
  3     30    300   3000;
  4     40    400   4000 ]

```

So we just need to `sum` it up and we're done.

# Answer
> 1 votes
# PHP, ~~78~~ 88 +1 bytes

```
for($e=preg_match_all("#\d#",$n=$argn);~$c=$n[$i++];)$s+=str_repeat($c,$e);echo$s+$n*$e;

```

Run as pipe with `-nR`.

May yield warnings in PHP 7.1. Repace `$c,$e` with `$c>0?$c:0,$e` to fix.

# Answer
> 1 votes
# Swift 4, ~~139~~ 134 bytes

```
func f(s:String){let k=s.filter{"/"<$0};print(Float(s)!*Float(k.count)+k.map{Float(String(repeating:$0,count:k.count))!}.reduce(0,+))}

```

Test Suite.

---

# Explanation

* `func f(s:String)` \- Defines a function `f` with an explicit String parameter `s`.
* `let k=s.filter{"/"<$0}` \- Filters the digits: I noticed that both `-` and `.` have smaller ASCII-values than all the digits, and `/` is between `.`, `-` and `0`. Hence, I just checked if `"/"` is smaller than the current character, as I did in my Python answer.
* `print(...)` \- Prints the result.
* `Float(s)!*Float(k.count)` \- Converts both the String and the number of digits to Float and multiplies them (Swift does not allow Float and Int multiplication :()). So it adds the number `x` times, where `x` is the number of digits it contains.
* `k.map{Int(String(repeating:$0,count:k.count))!` \- `k.map{}` maps over `k` with the current value `$0`. `String(repeating:$0,count:k.count)` takes each digit, creates a String of `x` identical digits and `Float(...)!` converts it to a Floating-point number.
* `.reduce(0,+)` \- Gets the sum of the list above.
* And finally `+` sums the two results.

---

# Let's take an example!

Say our String is `"0.45"`. First off, we filter the digits, so we are left with `0, 4, 5`. We convert `"0.45"` to Float and multiply by the number of digits: `0.45 * 3 = 1.35`. Then we take each digit and turn it into a String repeating that digit until it fills the width of the square (how many digits there are): `0, 4, 5 -> 000, 444, 555`. We sum this, `000 + 444 + 555 = 999`. Then we just add the results together: `1.35 + 999 = 1000.35`.

# Answer
> 1 votes
# C#, ~~139~~ 137 bytes

```
using System.Linq;n=>{var d=(n+"").Where(char.IsDigit);return d.Sum(i=>int.Parse(new string(i,d.Count())))+new int[d.Count()].Sum(_=>n);}

```

*Saved 2 bytes thanks to @Ian H.*

Try it online!

Full/Formatted version:

```
namespace System.Linq
{
    class P
    {
        static void Main()
        {
            Func<double, double> f = n =>
            {
                var d = (n + "").Where(char.IsDigit);
                return d.Sum(i => int.Parse(new string(i, d.Count()))) + new int[d.Count()].Sum(_ => n);
            };

            Console.WriteLine(f(123));
            Console.WriteLine(f(-144));
            Console.WriteLine(f(4));
            Console.WriteLine(f(244.2));

            Console.ReadLine();
        }
    }
}

```

# Answer
> 1 votes
# Mathematica, 107 bytes

```
(t=Length[s=#&@@RealDigits[#]//.{a___, 0}:>{a}];If[IntegerPart@#==0,t++];t#+Tr[FromDigits@Table[#,t]&/@s])&

```

# Answer
> 0 votes
# Python 3, 68 ~~70~~ ~~73~~ ~~77~~ bytes

```
lambda n:sum(float(n)+int(_*sum(x>"/"for x in n))for _ in n if"/"<_)

```

Try it online!

Loops over every digit character and repeats it by the number of digit characters overall, makes that into an integer, and adds that to `n`. This way `n` gets added `d` times, the horizontal part of the sum, along with the digit repetition, which is the vertical part. Originally used `str.isdigit` but `>"/"`, thanks to others in this thread, saved a lot of bytes. Saves two bytes by taking `n` as a string, but the output is messier.

```
lambda n:sum(n+int(_*sum(x>"/"for x in str(n)))for _ in str(n)if"/"<_)

```

Try it online!

# Answer
> 0 votes
# Japt v2.0a0 `-x`, 10 bytes

Takes input as a string.

```
f\d çU
cUy

```

Try it or run all test cases

```
f\d çU\ncUy     :Implicit input of string U                    > "-0.45"
f               :Match (returns an array)
 \d             :  RegEx /\d/g                                 > ["0","4","5"]
    çU          :Fill with U                                   > ["-0.45","-0.45","-0.45"]
      \n        :Reassign to U
        c       :Concatenate
         Uy     :  U transposed                                > ["-0.45","-0.45","-0.45","---","000","...","444","555"]
                :Implicit output of sum of resulting array     > 997.65

```

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


title: Weakened Binary Walls

text:
# Question
Title: Weakened Binary Walls
Inspired by Create a binary wall

Given a list of positive integers, we can write them out all above each other like so, for `[2, 6, 9, 4]` as an example:

```
0010
0110
1001
0100

```

We can imagine this as a wall:

```
..#.
.##.
#..#
.#..

```

However, this is a very weak wall, and it has collapsed! Each `1` (`#`) falls down until it hits the "ground" or another `1` (`#`). The `0`s (`.`s) are present in spots left by moved `1`s.

This becomes the following:

```
....
....
.##.
####

```

Which translates back to:

```
0000
0000
0110
1111

```

Which, as a list of numbers, is `[0, 0, 6, 15]`.

# Another test case

```
[10, 17, 19, 23]

```

This becomes:

```
01010
10001
10011
10111

```

which becomes:

```
00000
10011
10011
11111

```

translating back to:

```
[0, 19, 19, 31]

```

# Challenge

Given a list of positive integers, apply this transformation to the list. Input/Output as lists of positive integers in any reasonable format. Standard loopholes apply.

This is a , so the shortest answer in bytes wins!

# Answer
> 29 votes
# MATL, 4 bytes

```
BSXB

```

Try it at MATL Online

**Explanation**

```
    % Implicitly grab input as an array
    %   STACK: [10, 17, 19, 23]
B   % Convert each element to binary where each decimal number results in a row
    %   STACK: [0 1 0 1 0;
    %           1 0 0 0 1;
    %           1 0 0 1 1;
    %           1 0 1 1 1]
S   % Sort each column, placing all of the 1's at the bottom of each column
    %   STACK: [0 0 0 0 0;
    %           1 0 0 1 1;
    %           1 0 0 1 1;
    %           1 1 1 1 1]
XB  % Convert each row from its binary representation to its decimal number
    %   STACK: [0, 19, 19, 31]
    % Implicitly display the result

```

# Answer
> 6 votes
# Python, 68 bytes

```
f=lambda a:a and[x|y&a[0]for x,y in zip([0]+f(a[1:]),f(a[1:])+[-1])]

```

Try it online!

# Answer
> 6 votes
## JavaScript (ES6), 50 bytes

```
f=a=>a.map(_=>a.map((e,i)=>a[a[i]|=a[--i],i]&=e))&&a

```

Explanation: Suppose two rows of the wall were like this:

```
0011
0101

```

The result needs to be this:

```
0001
0111

```

In other words, the first row becomes the AND of the two rows and the second row becomes the OR of the two rows. This just needs to be repeated enough times for all the bits to fall to the bottom.

# Answer
> 4 votes
# Jelly, 9 bytes

```
BUz0Ṣ€ZUḄ

```

Try it online!

# Answer
> 4 votes
# Python 3.5, 60 bytes

```
def f(a,*t):
 if t:b,*r=f(*t);t=f(a|b,*r);a&=b
 return(a,*t)

```

Try it online!

Takes input like `f(2, 6, 9, 4)`. Assumes input is non-empty. Uses a lot of tuple unpacking.

# Answer
> 3 votes
# Japt, 16 bytes

```
m¤z3 ®¬n qÃz mn2

```

Try it online! using the `-Q` flag to format the array result.

## Explanation

```
m¤z3 ®¬n qÃz mn2    Implicit: U = input array.
                        [10, 17, 19, 23]
m¤z3                Map U to binary strings and rotate the array left 90°
                         1010       0111
                        10001   ->  1011
                        10011       0001
                        10111       1000
                                     111
®¬n qÃ              Sort each binary string, putting 0s and spaces at the start
                        0111
                        0111
                        0001
                        0001
                         111
z mn2               Rotate right 90° and convert each back to a number
                         0000       0
                        10011   ->  19
                        10011       19
                        11111       31
                    Implicit output of resulting array

```

# Answer
> 3 votes
# Octave, ~~29~~ 25 bytes

*4 bytes saved thanks to @Stewie*

```
@(x)bi2de(sort(de2bi(x)))

```

# Answer
> 3 votes
# Mathematica, 64 bytes

```
#~FromDigits~2&/@(Sort/@(PadLeft[#~IntegerDigits~2&/@#]))&

```

 is `\[Transpose]`

This converts the input (a list of numbers) to a list of lists of digits, pads it to be a square matrix, transposes it, sorts the rows so the 1's "fall" to the bottom, transposes back, then converts back into numbers.

# Answer
> 2 votes
# , 13 bytes

```
/:~"1&.|:&.#:

```

Try it online!

## Explanation

```
/:~"1&.|:&.#:  Input: array M
           #:  Convert each in M to binary with left-padding
       |:&     Transpose
/:~"1&         Sort each row
     &.|:      Inverse of transpose (which is just transpose)
         &.#:  Inverse of converting to binary

```

# Answer
> 2 votes
# 05AB1E, 9 bytes

```
bí0ζR€{øC

```

Try it online!

Kinda different algorithm from Magic's.

# Answer
> 2 votes
# Dyalog APL (23 characters)

```
{2⊥¨↓⍉↑{⍵[⍋⍵]}¨↓2⊥⍣¯1⊢⍵}

```
1. Convert the input arguments into a binary matrix
2. Split the matrix into columns
3. Sort the columns into ascending order
4. Convert the sorted rows back into decimal

## Example

```
  {2⊥¨↓⍉↑{⍵[⍋⍵]}¨↓2⊥⍣¯1⊢⍵}10 17 19 23
      0 19 19 31

```

Thanks to Zacharý for correcting me on this one.

# Answer
> 2 votes
# Dyalog APL, ~~24~~ ~~21~~ 19 bytes

```
2⊥↑{⍵[⍋⍵]}¨↓2⊥⍣¯1⊢⎕

```

Try it online! (modified so TryAPL accepts it as valid)

### How?

* evaluated input (arrays are space separated)
* `2⊥⍣¯1⊢` converts each each of the arguments to binary (transposed of what is in the question)
* turns a 2D array into a vector of vectors
* `{⍵[⍋⍵]}¨` sorts each of the elements of the vector
* turns the vector of vectors into a 2D array again
* `2⊥` convert from binary (since it sort of transposes it, we arrive at the correct result)

# Answer
> 1 votes
# JavaScript, ~~127~~ 125 bytes

```
a=>a[m='map'](_=>b[m]((n,i)=>n&&(b[i]--,d|=1<<i),d=0)&&d,b=[...Array(32)][m]((_,c)=>a[m](e=>d+=!!(2**c&e),d=0)&&d)).reverse()

```

Try it online

*-2 bytes thanks to Cows quack*

# Answer
> 1 votes
## Python 2, 142 bytes

... and still golfing... hopefully –– Any help appreciated!

```
def c(l):b=[bin(n)[2:]for n in l];print[int(n,2)for n in map(''.join,zip(*map(sorted,zip(*['0'*(len(max(b,key=len))-len(x))+x for x in b]))))]

```

A big chunk of this is for padding the numbers with zeroes.

More readable:

```
def collapse(nums):
    bins = [bin(n)[2:] for n in nums]
    bins = [('0'*(len(max(bins, key = len)) - len(x))) + x for x in bins]
    print [int(n, 2) for n in map(''.join, zip(*map(sorted, zip(*bins))))]

```

This creates an array of the binary string representations, pads it, rotates it 90º clockwise, sorts each row, rotates it back 90º, and then creates integers out of each row.

# Answer
> 1 votes
# Japt, 9 bytes

```
m¤ù yñ mÍ

```

Try it

```
m¤ù yñ mÍ     :Implicit input of array
m             :Map
 ¤            :  To binary strings
  ù           :Left pad each with spaces to the length of the longest
    y         :Transpose
     ñ        :Sort each and transpose back
       m      :Map
        Í     :  To decimal

```

# Answer
> 1 votes
# Husk, 11 bytes

```
mḋTmOT0mo↔ḋ

```

Try it online!

---
Tags: code-golf, number, binary, binary-matrix
---