text:
Tower building challenge
I have recently thought of a wonderful relatively old mobile game, called Tower Bloxx. Alhough I'm not really old myself, but it reminded me of childhood and school :)
So this my challenge is a kind of a reference to that good game!
I have (hopefully) looked into any tower question on PPCG and this won't be a dupe.

Definition
Given N - number of blocks, build a tower of N blocks with the following pattern. The horizontal coordinate is changed with every block.
In order to avoid misinterpretations, here's the "table" of correlations between the n-th block and its horizontal coordinate.
There're no random things there, the coordinate for each block is strictly defined.
These horizontal coordinates are all listed relative to the first block and they are in fact just for readability of the following test cases.
N    X (coord)
------
1    0
2    2
3   -2
4    0
5   -2
6    2
7    goto N=1

On top of the last block, you must smash a roof.

Input
Positive integer (N).
Output:
N blocks stacked on top of each other and the roof. Each block is horizontally moved compared to the first block (to either -2, 0, or 2 points), as described in the table.
The block structure:
  *********
  * ----- *
  * |   | *
  * |   | *
  * ----- *
  *********

Once they are stacked together, the top of the lower block intersects with the bottom of the higher block:
    *********
    * ----- *
    * |   | *
    * |   | *
    * ----- *
  ***********
  * ----- *
  * |   | *
  * |   | *
  * ----- *
  *********

The roof that should be stacked on top of the last, n-th block is:
      *
     ***
    ** **
   **   **

The block with the roof atop looks like this:
      *
     ***
    ** **
   **   **
  *********
  * ----- *
  * |   | *
  * |   | *
  * ----- *
  *********

Test cases below.
Input: 1. Output:
      *
     ***
    ** **
   **   **
  *********
  * ----- *
  * |   | *
  * |   | *
  * ----- *
  *********

Input: 2. Output:
        *
       ***
      ** **
     **   **
    *********
    * ----- *
    * |   | *
    * |   | *
    * ----- *
  ***********
  * ----- *
  * |   | *
  * |   | *
  * ----- *
  *********

Input: 3. Output:
    *
   ***
  ** **
 **   **
*********
* ----- *
* |   | *
* |   | *
* ----- *
*************
    * ----- *
    * |   | *
    * |   | *
    * ----- *
  ***********
  * ----- *
  * |   | *
  * |   | *
  * ----- *
  *********

Input: 4. Output:
      *
     ***
    ** **
   **   **
  *********
  * ----- *
  * |   | *
  * |   | *
  * ----- *
***********
* ----- *
* |   | *
* |   | *
* ----- *
*************
    * ----- *
    * |   | *
    * |   | *
    * ----- *
  ***********
  * ----- *
  * |   | *
  * |   | *
  * ----- *
  *********

Input: 10. Output:
      *
     ***
    ** **
   **   **
  *********
  * ----- *
  * |   | *
  * |   | *
  * ----- *
***********
* ----- *
* |   | *
* |   | *
* ----- *
*************
    * ----- *
    * |   | *
    * |   | *
    * ----- *
  ***********
  * ----- *
  * |   | *
  * |   | *
  * ----- *
  ***********
    * ----- *
    * |   | *
    * |   | *
    * ----- *
*************
* ----- *
* |   | *
* |   | *
* ----- *
***********
  * ----- *
  * |   | *
  * |   | *
  * ----- *
***********
* ----- *
* |   | *
* |   | *
* ----- *
*************
    * ----- *
    * |   | *
    * |   | *
    * ----- *
  ***********
  * ----- *
  * |   | *
  * |   | *
  * ----- *
  *********

Scoring
Code golf, shortest wins!

Trailing invisible stuff is allowed.

Are the coordinates relative to the first block or the previous block? Because first you said „first“ and then „previous“.

@O.O.B The coordinates stated in tables are just for readability, and they are relative to the first block. Each next block is moved relative to the previous block. I see no conflict in wording.

In fact, I believe anyone can see the pattern by looking just in the test cases without seeing the table and anything else.

While the test cases are unambiguous, the wording „Each block is horizontally moved compared to the previous block, as described in the table.“ is misleading imo.

@o.O edited.

can the outputs not have the leading spaces (keeping everything shaped as is) or are they required?

@dzaima the spaces are here because it is easier with them, look at the further test cases, starting from the third, and you'll understand why

@dzaima not required. Sorry for misunderstanding your comment.

I remember the game! I've played it myself. Now you made me need to play it. Good thing I've got a j2me phone for such occasions.

Charcoal, 48 bytes
ＦＮ«Ｍ×Ｘ±¹ιＩ§224ι←Ｂ⁹±⁶*↗↗↑↓²→⁵↖↑²←⁵↖»ＧＨ<⁵*Ｍ⁷←ＧＨ<⁴*

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

Draw N Blox.
Ｍ×Ｘ±¹ιＩ§224ι←

Adjust the horizontal position before drawing each Blox.
Ｂ⁹±⁶*

Draw the outer wall of the Blox.
↗↗↑↓²→⁵↖↑²←⁵↖»

Draw the inner wall of the Blox.
ＧＨ<⁵*Ｍ⁷←ＧＨ<⁴*

Raise the roof.

JavaScript (ES6), 206 bytes
Saved 2 bytes thanks to @kamoroso94
f=(n,k=0)=>n--?f(n,k+1)+`${n?`
`:23456}0110`.replace(/./g,c=>' '.repeat('240204'[k%6])+'* ----- ,* |   | ,    ,   **,  ** *, **   *,********'.split`,`[c]+`*
`)+(k%6<2?'  ':'')+'*'.repeat(k?k%3<2?11:13:9):''

Try it online!

 23456  doesn't need to have backticks around it, save two bytes.

@kamoroso94 Thanks, nice catch!

@kamoroso94 Also, use \\23456\\`to have backticks in code:`23456``.

SOGL V0.12, 53 bytes
ø.∫"│“3─wι«@*ο"²¹EiΕbK⁷‘╬$.F=?"¦○⌠Q°‘5nΓ;+}┼JGKh╬8;++

Try it Here!

Python 2, 258 bytes
n=input()
l=[[4,2,4,0,2,0][(n-i)%6]for i in[0]+range(n)+[n-1]]
for i,v in enumerate(l[:-1]):s=v*' ';a,b=s+'* ----- *',s+'* |   | *';x,y=sorted([l[i+1],v]);print'\n'.join(([a,b,b,a]if i else[s+'    *',s+'   ***',s+'  ** **',s+' **   **'])+[' '*x+'*'*(9+y-x)])

Try it online!

JavaScript (Node.js), 238 bytes
n=>{for(l=n>2&&2,s=i="";i<n;l=A)
s=(y=(p=" "[r="repeat"](A="240204"[i++%6]-(n<3)*2))+`* ----- *
`)+(x=p+`* |   | *
`)+x+y+" "[r](l>A?A:l)+"*"[r](9+Math.abs(A-l))+`
`+s
return p+`    *
${p}   ***
${p}  ** **
${p} **   **
${p}*********
`+s}

Try it online!


text:
Output a binary path from a number
For an integer n that satisfies n > 0, write its value as a right-descending path based on its binary representation.
Rules

The first (most significant) set bit is always in the top-left corner.
When the next bit is set (a 1), draw a character ("filled") on the next line in the same column as the previous character drawn. Try to use spaces ("empty") to fill, but any character will do as long as it's always the same.
When the next bit is unset (a 0), draw a character ("filled") on the same line immediately to the the right of the previous character drawn.
Your code must support numbers with at least 20 significant bits.
Write a full program, a function, a lambda, etc. but no snippet.
No leading spaces (or "empty" char) / lines allowed
Any number of trailing spaces (or "empty" char) / lines allowed
Any kind of 1D input is accepted: number, string, array of booleans, etc. Keep the order of bits untouched though.
Any kind of visual 2D output is accepted: on stdout, a string (with any two distinct values representing "filled" and "empty"), you can even output a matrix if you want. A list of numbers seems hard to reconcile with the "no heading spaces" rule, but I'm open to it if you find a way to use it. Note: if you chose to print or return a string, the characters used must be ASCII characters in the codepoints range [32-126].
Standard loopholes are banned.
This is codegolf so the shortest code wins.

Examples
Input: 1
*

Input: 2
**

Input: 3
*
*

Input: 4
***

Input: 5
**
 *

Input: 6
*
**

Input: 7
*
*
*

Input: 25
*
***
  *

Input: 699050
**
 **
  **
   **
    **
     **
      **
       **
        **
         **

Input: 1047552
*
*
*
*
*
*
*
*
*
***********

Input: 525311
**********
         *
         *
         *
         *
         *
         *
         *
         *
         *
         *

Sandbox

Does "allowed input array of booleans" mean that taking the input in the form of the number's binary representation as an array is allowed?

@Nit Any kind of 1D input. So if the number is 5, you may have an input array similar to [1,0,1], yes.

So how free is that format really ? I'd like to take a number as the binary digits with the first 1 moved to the end, so since 9 is 1001 I'd like my input to be 0011. Is that OK?

Having the first bit being 1 first is part of the challenge, and (re-)moving that bit would be trivializing the challenge so I'm afraid I'll have to say you no, @TonHospel . You can remove it from your input in the program, though.

Would graphical output be acceptable?

@12Me21 yes, as long as it's 2D.

Jelly, 8 bytes
¬œṗ+\Ṭz0

A monadic link accepting a number as a list of ones and zeros (e.g. 13 is [1,1,0,1]) returning a list of lists of ones and zeros where the first list is the first row.
Try it online! or see a formatted test-suite
How?
¬œṗ+\Ṭz0 - Link: list L           e.g. [1,1,0,0,1,1,0,1] (i.e. 205)
¬        - logical NOT L               [0,0,1,1,0,0,1,0]
    \    - cumulative reduce L by:
   +     -   addition                  [1,2,2,2,3,4,4,5]
 œṗ      - partition @ truthy indices  [[1,2],[2],[2,3,4],[4,5]]
     Ṭ   - un-truth (vectorises)       [[1,1],[0,1],[0,1,1,1],[0,0,0,1,1]]
      z0 - transpose with filler 0     [[1,0,0,0],[1,1,1,0],[0,0,1,0],[0,0,1,1],[0,0,0,1]]
         -                        i.e.  1000
                                        1110
                                        0010
                                        0011
                                        0001

MATL, 14 bytes
J_iB^YsJ+'o-'&XG

Produces graphical output as a path starting at coordinates (0,0). Try it at MATL Online! Or see some offline examples below:

Input 7:

Output:

Input 699050:

Output:

If you prefer, you can see the path as complex coordinates for 9 bytes:
J_iB^YsJ+

Try it online!
###Explanation
J_      % Push -1j (minus imaginary unit)
i       % Push input number
B       % Convert to binary. Gives an array of 0 and 1 digits
^       % Power, element-wise. A 0 digit gives 1, a 1 digit gives -1j
Ys      % Cumulative sum. Produces the path in the complex plane
J+      % Add 1j, element-wise. This makes the complex path start at 0
'o-'    % Push this string, which defines plot makers
&XG     % Plot

MATL, 10 bytes
YsG~YsQ1Z?

Inputs an array of binary digits. Outputs a matrix.
Try it online!
Explanation
Ys    % Implicit input: array of binary digits. Cumulative sum. This gives the
      % row coordinates
G     % Push input again
~     % Negate: change 0 to 1 and 1 to 0
Ys    % Cumulative sum
Q     % Add 1. This gives the column coordinates
1Z?   % Matrix containing 1 at those row and column coordinates and 0 otherwise.
      % Implicit display

Python 2, 100 99 81 78 73 66 bytes
a='';x=0
for c in input():a+=('\n'+' '*x)*c+'*';x+=1-c
print a[1:]

Try it online!
Recursive version:
Python 2, 71 69 67 bytes
f=lambda n,x=0:n and('\n'[:x]+' '*x)*n[0]+'*'+f(n[1:],x+1-n[0])or''

Try it online!

05AB1E, 18 17 14 bytes
γ€gć¸s>«1IÔ·ÌΛ

Try it online!
Explanation
γ€g             # Push the input as the array as chuncks of consecutive elements, map with length
   ć¸s>«        # Increment each value except the first one
        1I      # Push 1 and the input
          Ô     # Push connected uniquified input (first elements of each chunck of consecutive elements in the input)
           ·Ì   # Map each with 2 * a + 2
             Λ  # Draw canvas :-)

3 bytes thanks to @Emigna

05AB1E canvas's explanation

γ€gć¸s>«1IÔ·ÌΛ should save 4 bytes.

@Emigna Brilliant, thanks ! Totally forgot that there was an a+2 builtin o:

I realize these weren't possible yet when you posted your answer, but you can save 3 bytes now in the new 05AB1E version by changing γ€g to Åγ; ć¸s>« to >ć<š and 1I to $: Try it online: Åγ>ć<š$Ô·ÌΛ.

C# (.NET Core), 155 123 120 113 101 bytes
Saved 32 bytes due to input being able to be received as an array of bits.
Saved 7 bytes thanks to @auhmaan.
Saved 10 bytes thanks to @KevinCruijssen.
n=>{var m="";for(int i=0,c=1;i<n.Length;)m+=n[i++]<1?c++%1+"":(i>1?"\n":"")+"0".PadLeft(c);return m;}

Try it online!

Can't you change the +new string(' ',c)+"*" to +"*".PadLeft(c) ( saves 7 bytes ) ?

@auhmaan You're right, thanks!

-4 bytes by printing 0 instead of *: if(n[i++]<1){m+="*";c++;} to if(n[i++]<1)m+=c++%1; and "*".PadLeft(c); to "0".PadLeft(c);

Correction, it's actually -12 bytes because m+= can now be a ternary-if: m+=n[i++]<1?c++%1+"":(i>1?"\n":"")+"0".PadLeft(c);

@Oliver Umm.. now c isn't used at all anymore, and so it also doesn't pad.. (Try any other number like 699050 in your linked TIO.)

Then again, the current answer also fails for 699050..

@KevinCruijssen Thanks, using 0's and the use of the ternary operator is really smart! I also fixed the case for 699060, by simply setting c to one the beginning, I kinda missed that while checking the test cases.

Charcoal, 22 20 19 11 10 bytes
Ｆ⮌Ｓ¿Ｉι↑*←*

Only my second Charcoal answer thus far.
Takes the input as binary-String (i.e. 699050 as 10101010101010101010).
-9 bytes thanks to @Neil suggesting to loop backwards.
Try it online.
Explanation:
Read STDIN as string in reversed order:
Reverse(InputString())
⮌Ｓ

Loop over its binary digits as strings ι:
For(Reverse(InputString()))
Ｆ⮌Ｓ

If ι casted back to a number is 1, print the * upwards, else print the * towards the left.
If(Cast(i)) Print(:Up,"*"); Else Print(:Left,"*");
¿Ｉι↑*←*

This would be half as long if you printed the string in reverse, starting at the end and working up and left.

@Neil Ok, now it should be fixed. Thanks! -8 bytes

Save another byte by removing the {}s.

@Neil Ah, I had hoped the verbose converter would be smart enough to golf those kind of things itself. ;) Including Assign(InputString(), a); to InputString(a); or Print(:Right, "*"); to Print("*");. Thanks! I still have a lot to learn, but it's an amazing language for sure!

Print(:Right, "*") isn't the same as Print("*") because the latter is affected by PivotLeft() and PivotRight().

@Neil Ah of course. Ah well, I should just golf the verbose version as much as possible as well. Removing those brackets from the For-loop is part of the golfing process I guess, same as I golfed Equals(i, "1") to Cast(i) in my answer.

FYI operating on decimal input is still only 17 bytes: ＮθＷθ«¿﹪θ²↑*←*≧÷²θ.

Ah, that's a pretty cool method by taking as number and keeping it a number as long its not 0 yet. Still, even if taking the input as decimal would be mandatory, I could just change InputString() in my current answer to Cast(Base(InputNumber(),2)) and it would still be only 13 bytes. :) Out of curiosity, why is the program flow output when using argument -a not the same as the verbose code with argument -vl? Is there a reason the current -a format was chosen? Or is there another argument-flag that's the inverse of -vl that I'm unaware of?

Oh, I forgot about Base... I don't know of an inverse to -v, I also use -a if I want to understand the succinct code.

Base only costs 1 byte as you don't need the Cast at all: Ｆ⮌↨Ｎ²¿ι↑*←*.

@KevinCruijssen Sorry for the late reply, but to answer your questions: there is no reverse of -v, since Charcoal was designed as a golfing language, and I added verbose mode just to make it easier to type and understand. (I can add one if you want though). -a is short for --ast, I added it (format taken from PyTek btw) to help me understand the succinct code with as little effort as possible :P (and it really helps when you've accidentally messed up argument order). Also, not that -l is a separate option. (also just do -h for help on/descriptions of command-line args)

Haskell, 65 bytes
f(a:b)|a="*":f b|(x:y)<-f b=('*':x):map(' ':)y
f[]=["*"]
f.tail

Try it online!
Takes input as a list of booleans.
Curry PAKCS, 70 bytes
u(a:b)=('*':a):map(' ':)b
f(a:b)|a="*":f b|1>0=u$f b
f[]=["*"]
f .tail

Port of the Haskell answer, but because <- doesn't work in Curry we need to make a helper function u. We also need to add a space between f and . so that Curry parses it as a compose rather than a dot.
This also works in MCC Curry, but doesn't work in Sloth Curry (which is the only one supported by TIO).

Haskell, 74 70 67 62 bytes
tail.("\n"%)
s%(x:r)=([1..x]>>s)++'*':(s++[' '|x<1])%r
s%[]=""

Try it online! Takes a list of zeros and ones as input and returns a newline separated string.
Inspired by xnor's answer.

A little friendly competition.

@user56656 Your turn again :)

Python 2, 59 bytes
s=p='\n'
for x in input():s+=p*x+'*';p+=' '[x:]
print s[2:]

Try it online!
Based off TFeld's solution.

Emojicode, 251 bytes
b2c*eykbi ki1y eyyye cyy ce  ey

Try it online!
This is definitly not a golfed solution, but there isn't a person alive that would consider Emoji-code a golfing language. However, in the process of subjecting myself to the horrors that are emoji-code's syntax in an effore to teach myself this monstrosity of a language, I've been pleasantly surprised by just how powerful and efficient it can be
Explaination:
       Define Class
     Define Method
b2    Convert Input integer to binary string
c*     asterisk string
e     Spacing string
y     output string
kb     translate to iteratable
i k     for-in loop to iterate over each digit
i1     if digit is 1:
y e     don't print initial newline
y     print spaces + asterisks
y     reset output string
ye c     add correct number of spaces and one asterisk
     if digit is 0:
yy c     add an asterisk to the output string
e  e     add another space to the space string

y     print one last output string

     Start Program
  699050     Call Method

JavaScript (ES6), 48 bytes
Same I/O format and same logic as the recursive version below.
a=>a.map((n,i)=>n?i&&p+0:+(p+=' '),p=`
`).join``

Try it online!
Or 42 bytes if this format is acceptable.

Recursive version, 56 bytes
Takes input as an array of integers (0 or 1). Uses 0 for filled and space for empty.
f=([n,...a],p=`
`,x=0)=>1/n?(n?x+0:+(p+=' '))+f(a,p,p):a

Try it online!
Commented
f = (               // f = recursive function taking:
  [n, ...a],        //   n = current bit; a[] = remaining bits
  p = `\n`,         //   p = padding string, initialized to a linefeed
  x = 0             //   x = 0 on the 1st iteration / equal to p after that
) =>                //
  1 / n ?           // if n is defined:
    ( n ?           //   if n = 1:
        x + 0       //     append x + 0 --> either the integer 0 on the first iteration
                    //                      or the padding string followed by a '0'
      :             //   else:
        +(          //     append the integer 0 (whitespace coerced to a number)
          p += ' '  //     and append a space to the padding string
        )           //
    ) + f(a, p, p)  //   append the result of a recursive call with x = p
  :                 // else:
    a               //   append the empty array a[], forcing coercion to a string

Java 10, 100 106 bytes
b->{var s="";int i=0,j;for(var c:b){if(c)for(s+="\n",j=i;j-->0;)s+=0;else++i;s+=1;}return s.substring(1);}

Takes an array of booleans and returns a String (0s are empty, 1s are filled). Try it online here.
Thanks to Olivier Grégoire for helping me golf it a bit more and alerting me to the fact that my output format was not up to the spec.
Ungolfed version:
b -> { // lambda taking an array of booleans as argument
    var s = ""; // the output String
    int i = 0,  // the number of "empty" characters to output
    j;          // iterator variable for outputting the "empty" characters
    for(var c : b) { // iterate over the boolean array (the binary digits)
        if(c) // if it's a '1'
            for(s += "\n", // output a newline
            j = i; j-- > 0;) s += 0; // output the "empty" characters
        else // if it's a '0'
            ++i; // move one to the right on the next line
        s += 1; // output the "filled" character
    }
    return s.substring(1); // output the constructed String, minus the leading newline
}

I golfed 5 bytes: {if(c){s+="\n";for(j=i;j-->0;)s+=0;}else++i;s+=1;}

Even further: {if(c)for(s+="\n",j=i;j-->0;)s+=0;else++i;s+=1;}

Though, you don't print on the first line but on the second one. From the challenge: "No leading spaces (or "empty" char) / lines allowed"

@OlivierGrégoire Thanks. I have edited.

Bash + GNU utilities, 38
dc -e?2op|sed 's/\B1/^K^H*/g;s/[10]/*/g'

Here ^K and ^H are literal vertical-tab and backspace control characters.  These don't render well on browsers, so this script may be recreated as follows:
base64 -d <<< ZGMgLWU/Mm9wfHNlZCAncy9cQjEvCwgqL2c7cy9bMTBdLyovZyc= > binpath.sh

Run in a terminal.  Input is via STDIN.
This answer may stretch the specifications too far - there are in fact no leading characters on each line of output - all positioning is done with control characters.  If this is too much of a stretch, then the output may be piped to |col -x|tac for an extra 11 bytes.

Batch, 113 bytes
@set s=
:l
@shift
@if %1.==0. set s=%s%+&goto l
@echo %s%+
@if not %s%.==. set s=%s:+= %
@if %1.==1. goto l

Takes a list of bits as command-line arguments. Uses + instead of * because * has a special meaning inside %s:...=...% expansions.

Java (JDK 10), 83 bytes
a->{int m[][]=new int[20][20],r=0,i=0;for(int b:a)m[r+=i<1?0:b][i++-r]=1;return m;}

Try it online!

Supports at most 20 bits.
Input as int[]
Output as int[][]

Japt, 19 17 bytes
Ë?R+Tî +Q:°T©QÃ¬x
Ë?                 // Map over the input and if the current value is 1:
  R+               // Return a new line and
    Tî +           // a space repeated T (with initial value 0) times and
        Q          // a \".
         :         // If the current value is 0:
          °T       // Increment T
            ©Q     // and return \".
              Ã    // When all of that is done,
               ¬   // turn the array into a string
                x  // and trim it, removing the excess new line at the start.

Takes input as an array of bits, for example [1,0,1], outputs " instead of *.
Shaved two bytes off thanks to Oliver.
Try it online!

Nice one. You can replace SpT with Tî - î is similar to p, except it defaults to " ". Also, there's a shortcut for q : ¬

@Oliver Thanks, I didn't know about î, certainly very handy. I often check for chances to use the shortcuts, but I still always miss some of them, thanks a lot for your help.

Haskell, 126 bytes
(#)n=maximum.map(!!n)
f l|s<-scanl1(zipWith(+))$(\a->[1-a,a])<$>l=unlines[[last$' ':['#'|elem[x,y]s]|x<-[0..0#s]]|y<-[1..1#s]]

Input as a list of zeroes and ones. Transforms number into offset by x↦[1-x,x] and calculates the partial sums. Final output is done with two nested list comprehensions.
Try it online!

APL+WIN, 65 or 46 bytes
Prompts for input of the integer
n←+/i←((1+⌊2⍟n)⍴2)⊤n←⎕⋄m←(n,n)⍴' '⋄m[⊂[2](+\i),[1.1]1++\~i]←'*'⋄m

or for numerical vector of the binary representation of the integer
m←(2⍴+/n←⎕)⍴' '⋄m[⊂[2](+\i),[1.1]1++\~i]←'*'⋄m

assuming I have read the comments to certain answers correctly and the latter input is allowed.

R, 59 bytes
function(n,x=sum(n|1))matrix(1:x^2%in%cumsum((n-1)%%x+1),x)

Try it online!
Takes input as an array of bits.
Returns a boolean matrix of TRUE and FALSE representing a * and a , respectively.
Also has some stuff in the footer to print a matrix corresponding to the specs above, for ease of testing.

Pyth, 23 bytes
p\*VtQINp+b*Zd.?=hZ)p\*

Try it here
Explanation
p\*VtQINp+b*Zd.?=hZ)p\*
p\*                       Print the leading *.
   VtQ                    For each bit (excluding the leading 1)...
      IN      .?   )      ... If the bit is set...
        p+b*Zd            ... Print a newline and a bunch of spaces...
                =hZ       ... Otherwise, increase the count of spaces...
                    p\*   ... Then print the next *.

Perl 5 -p, 54 36 bytes
s/./$&?"
".$"x$i.1:++$i&&1/ge;s/.//s

Try it online!
Cut it way down after I realized that the input could be a bit string.

SmileBASIC, 64 59 57 bytes
INPUT N@L
GPSET X,Y
B=N<0X=X+B
Y=Y+(X>B)N=N<<1ON!N GOTO@L

The highest bit (sign bit) is checked, and if it's 1, the X position increases. If the sign bit is less than the X position (that is, the sign bit is 0 and X is not 0) the Y position increases.
The first movement will always be horizontally, so Y movement is blocked until after the first X movement. This ensures that the Y position doesn't increase during the leading 0 bits.
Then N is shifted left, and this repeats until N reaches 0.

Ruby, 63 bytes
->n{s=""
n.to_s(2).gsub(/./){$&==?1?"
"+s+?*:(s+=" ";?*)}[1,n]}

Try it online!

Python 2, 113 Bytes
def f(a):
 o='*';r=[o]
 for i in bin(a)[3:]:
  if'0'<i:r+=[' '*len(r[-1][1:])]
  r[-1]+=o
 print'\n'.join(r)

Not sure if this one counts (it outputs an array of each of the lines), but if so then I'll change my byte count to 103:
def f(a):
 o='*';r=[o]
 for i in bin(a)[3:]:
  if'0'<i:r+=[' '*len(r[-1][1:])]
  r[-1]+=o
 print r

TI-Basic (TI-84 Plus CE), 85 bytes
Prompt L
1→X
1→Y
DelVar [A]
sum(LL
{Ans,1-Ans+dim(LL→dim([A]
1→[A](Y,X
For(I,2,dim(LL
Y+LL(I→Y
X+not(LL(I→X
1→[A](Y,X
End
[A]

Prompts for a boolean list, returns a matrix of 0 and 1.
Goes through the list, incrementing X if the next 'bit' is 0, changing Y otherwise, then adding a 1 to the matrix at that location, and returns the matrix at the end.
TI-Basic is a tokenized lanugage.

1 byte: Prompt , L*6, (newline)*12, 1*5, →*7, X*5, Y*5, sum(, L*5, {, Ans*2, ,*5, -, +*3, dim(*3, (*4, For(, I*3, 2, not(, End = 73 bytes
2 bytes: Delvar , [A]*5 = 12 bytes
Total: 85 bytes

TI-Basic (TI-84 Plus CE), 56 bytes
Prompt L
1→X
1→Y
Output(Y,X,"*
For(I,2,dim(LL
Y+LL(I→Y
X+not(LL(I→X
Output(Y,X,"*
End

Same processs as above, but using graphical output (limited by screen size: 10 rows, 26 columns, so max 10 1s and 25 0s) as it goes, instead of adding to a matrix.

Pyth, 30 bytes
JZFG.BQIsGIJk)p+*ZdN.?pN=hZ)=J

Try it online!
Uses " instead of *.
Python 3 translation:
Q=eval(input())
Z=0
J=Z
for G in "{0:b}".format(Q):
    if int(G):
        if J:
            print()
        print(Z*' '+'"',end='')
    else:
        print('"',end='')
        Z+=1
    J=Q

x86 .COM, 32 bytes
00h: 66 D1 E6 66 0F BD CE BF 24 AD 8E DF 41 66 0F A3
10h: CE 19 DB 81 E3 9E 00 8D 79 02 C6 05 2A E2 EE C3

fun:
shl esi, 1
bsr ecx, esi
mov di, $ad24
mov ds, di
inc cx
lab2:
bt esi, ecx
sbb bx,bx
and bx,158
lea di,[di+2+bx]
mov [di],byte '*'
lab1:loop lab2
ret

APL (Dyalog Classic), 18 bytes
+⌿↑1↑¨⍨-+\,¨∘~⍨0,⎕

Try it online!

source: Stack Exchange

license: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/3.0/

all_licenses: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/4.0/

sort: votes


text:
Expand Sine and Cosine
Trigonometry has LOTS of identities. So many that you can expand most functions into sines and cosines of a few values. The task here is to do that in the fewest bytes possible.
Identity list
Well, the ones we're using here.
sin(-x)=-sin(x)
sin(π)=0
cos(-x)=cos(x)
cos(π)=-1
sin(a+b)=sin(a)*cos(b)+sin(b)*cos(a)
cos(a+b)=cos(a)cos(b)-sin(a)sin(b)

For the sake of golfing, I've omitted the identities that can be derived from these. You are free to encode double-angles and such but it may cost you bytes.
Input

You should take in an expression as a string with an arbitrary number of terms consisting of a coefficient and some sine and cosine functions, each with an exponent and an arbitrary number of arguments.
Coefficients will always be nonzero integers.
Each argument will be a coefficient, followed by either a single latin letter or pi.
You can decide whether to take in pi as pi or π. Either way remember that you're scored in bytes, not characters.

Output
Output the same expression, but…

All trig functions are either sin or cos.
All arguments of trig functions are single variables, with no coefficients.
All like terms are combined.
Terms with a coefficient of 0 are removed.
All factors in the same term that are the same function of the same variable are condensed into a single function with an exponent.

Note: Leading + signs are allowed, but not required. a+-b is allowed, and equivalent to a-b. If there are no terms with nonzero coefficients, then output either 0 or an empty string.
Worked Example
We'll start with sin(-3x)+sin^3(x). The obvious first thing to do would be to deal with the sign using the parity identity, leaving -sin(3x). Next I can expand 3x into x+2x, and apply the sine additive identity recursively:
-(sin(x)cos(2x)+cos(x)sin(2x))+sin^3(x)
-(sin(x)cos(2x)+cos(x)(sin(x)cos(x)+sin(x)cos(x)))+sin^3(x)

Next, some distributive property and like terms:
-sin(x)cos(2x)-2cos^2(x)sin(x)+sin^3(x)

Now, I expand the cos(2x) and apply the same reduction:
-sin(x)(cos(x)cos(x)-sin(x)sin(x))-2cos^2(x)sin(x)+sin^3(x)
-sin(x)cos^2(x)+sin^3(x)-2cos^2(x)sin(x)+sin^3(x)
2sin^3(x)-3sin(x)cos^2(x)

And now, it's finished!
Test Cases
In addition to the following, all of the individual identities (above) are test cases. Correct ordering is neither defined nor required.
cos(2x)+3sin^2(x) => cos^2(x)+2sin^2(x)
sin(-4x) => 4sin^3(x)cos(x)-4sin(x)cos^3(x)
cos(a+2b-c+3π) => 2sin(a)sin(b)cos(b)cos(c)-sin(a)sin(c)cos^2(b)+sin(a)sin(c)sin^2(b)-cos(a)cos^2(b)cos(c)+cos(a)sin^2(b)cos(c)-2cos(a)sin(b)cos(b)sin(c)
sin(x+674868986π)+sin(x+883658433π) => 0 (empty string works too)
sin(x+674868986π)+sin(x+883658434π) => 2sin(x)

…and may the shortest program in bytes win.

May we output (for example) sin(x)^3 rather than sin^3(x)? Can we take pi as PI as well?

This looks very close to a dup of https://codegolf.stackexchange.com/questions/38341/help-me-with-trigonometry

@DigitalTrauma that seems to be about printing a specific answer set, not a generalized and specified input-processing challenge.

@Giuseppe sure, whatever format is best.

I presume it's okay to have a constant (i.e. not a coefficient of sin or cos) in the output, since it's possible to deduce sin^2 + cos^2 = 1 only using the identities given?

@JungHwanMin how so? (Though you will encounter constants, like cos(π).)

cos(0) = cos(pi+(-pi)) = cos(pi)cos(-pi) - sin(pi)sin(-pi) = cos(pi)cos(pi) - 0 = (-1)^2 = 1. So, 1 = cos(0) = cos(x+(-x)) = cos(x)cos(-x) - sin(x)sin(-x) = cos(x)cos(x) + sin(x)sin(x) = cos^2(x) + sin^2(x).

Is it fine to simplify sin^2 + cos^2 to 1?

@JungHwanMin yeah, that's fine, but it's not strictly required. As long as the output has no like terms or factors and is fully expanded, it's fine.

@JungHwanMin It must be, as it stems from applying the last identity with b=-a and then the first and third

"Coefficients and will always be nonzero integers" must be missing a word (or has a word too many). Sorry, should have caught this in sandbox.

@PeterTaylor it's never too late to fix a typo!

Are built-ins allowed? (I am thinking of doing this in Mathematica, with TrigExpand)

@NoOneIsHere yes, but I won't upvote it because it's zero-effort.

This looked very easy to me before I actually read it.

@JungHwanMin Wow. I predicted that it may be possible to deduce sin²x+cos²x=1 while it was in the sandbox, but could not prove it. Now it's indeed true.

"You should take in an expression as a string"<- Is this a strict requirement? For eg. Julia has anExpr type for expressions, can the input be ofExpr type? Also, will the operation between terms in the expression always be addition? Is sin(-3x)-sin^3(x) a possible input?

@sundar yes, that would be a possible input.

Bracmat, 221 bytes
(P=F v a b.!arg:((sin|cos):?F.?v)&(!v:@&(!F.!v)|!F$!v)|!arg:%?a_%?b&(P$!a)_(P$!b)|!arg)&(f=i a b n u.1+(!arg:e^(?n*((i|-i):?i)*?u+?b)&(!i*(sin.!u)+(cos.!u))^!n*f$(e^!b)|!arg:%?a_%?b&(f$!a)_(f$!b)|!arg)+-1)&(Z=.f$(P$!arg))

Try it online!

I have no idea what that's doing but it works... good answer on an otherwise-abandoned question!

Python3, 841 bytes
Longer than I hoped, but the logic is straightforward.
E=enumerate
S,O='sin','cos'
def f(e):
 e=[[(a,b,[([1,-1][j<0]*([1,j]['pi'==C]),C)for j,C in c for _ in range(1,abs(j)+1 if'pi'!=C else 2)],d)for a,b,c,d in i]for i in e]
 P=1
 while P:
  P=0
  for i,a in E(e):
   F=0
   for I,A in E(a):
    if len(A[2])>1:q,*w=A[2];l=[[(A[0],S,[q],1),(1,O,w,1)],[(A[0],S,w,1),(1,O,[q],1)]]if S==A[1]else[[(A[0],O,[q],1),(1,O,w,1)],[(-1*A[0],S,[q],1),(1,S,w,1)]];l=[u+a[:I]+a[I+1:]for u in l];e=e[:i]+e[i+1:]+l;F=1;break
   if F:P=1;break
 r={}
 for i in e:
  R,T={},1
  for a,b,[(C,V)],d in i:
   if C==-1 and'sin'==b:a*=-1
   if'pi'==V:
    if(L:=[[1,-1][abs(C)%2],0][b==S])==0:R,T={},0;break
    else:T*=L*a
   else:R[(b,V)]=R.get((b,V),0)+d;T*=a
  r[M]=r.get(M:=str(sorted(R.items())),0)+T
 return' + '.join(str(b)+''.join(f'{j}{["^"+str(l),""][l==1]}({k})'for(j,k),l in eval(a))for a,b in r.items()if b)

Try it online!

Without changing the algorithm, I get 814 chars. First half:  E=enumerate S,O='sin','cos' def f(e):  e=[[(a,b,[([1,-1][j<0]*[1,j]['pi'==C],C)for j,C in c for _ in range(1,1+abs(j)if'pi'!=C else 2)],d)for a,b,c,d in i]for i in e]  P=1  while P:   P=0   for i,a in E(e):    for I,A in E(a):     if len(A[2])>1:q,*w=A[2];l=[[(A[0],S,[q],1),(1,O,w,1)],[(A[0],S,w,1),(1,O,[q],1)]]if S==A[1]else[[(A[0],O,[q],1),(1,O,w,1)],[(-1*A[0],S,[q],1),(1,S,w,1)]];l=[u+a[:I]+a[I+1:]for u in l];e=e[:i]+e[i+1:]+l;P=1;break    if P:break

Second half: r={}  for i in e:   R,T={},1   for a,b,[(C,V)],d in i:    if C==-1 and S==b:a*=-1    if'pi'==V:     if(L:=(1-2*(abs(C)%2))*(b!=S))==0:R,T={},0;break     else:T*=L*a    else:R[(b,V)]=R.get((b,V),0)+d;T*=a   r[M]=r.get(M:=str(sorted(R.items())),0)+T  return' + '.join(str(b)+''.join(f'{j}{f"^{l}"*(l!=1)}({k})'for(j,k),l in eval(a))for a,b in r.items()if b)

@movatica Thank you very much. I have added the essence of your golfs to the post, will complete it when time allows...

Saving more bytes using exponent to replace conditionals: e=[[(a,b,[([1,-1][j<0]*j**('pi'==C),C)for j,C in c for _ in range(1,1+abs(j)**('pi'!=C))],d)for a,b,c,d in i]for i in e]

... and finally, -1 is a True-value in Python3, allowing to turn around the conditional: if(L:=(1-2*(abs(C)%2))*(b!=S)):T*=L*a     else:R,T={},0;break

all_licenses: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/3.0/


text:
Is it a valid number theory expression?
A number theory expression contains:
There exists at least one non-negative integer (written as E, existential quantifier)
All non-negative integers (written as A, universal quantifier)
+ (addition)
* (multiplication)
= (equality)
>, < (comparison operators)
&(and), |(or), !(not)
(, ) (for grouping)
variable names(all lowercase letters and numbers, not necessary one char long)

However, it has some more limitations:

Arithmetic expressions should be syntactically valid. Here we only treat + as addition, not positive, so + and * should be surrounded by two number expressions
brackets should be well paired
< = > should be surrounded by two number expressions
& | ! are fed with logical expressions
E and A are fed with a variable and an expression
For E and A, there should be a reasonable affected range. (*)

For (*): We write Ax Ey y>x & y=x, Ax Ey y>x & Ey y=x as well as Ax Ey y>x & Ax Ey y=x, which mean Ax (Ey ((y>x) & (y=x))), Ax ((Ey (y>x)) & (Ey (y=x))) and (Ax (Ey (y>x))) & (Ax (Ey (y=x))); however we don't write Ax Ey Ax x=y or Ax Ey x<y & Ex x>y. That means there should be some way to add brackets, so everywhere any variable is at most defined for once, and anywhere that use the variable has it defined.
Input
You'll be given an expression with these chars (invalid chars won't appear), only split when necessary (two variable names together), split after each quantifier variable, or each symbols are separated. No invalid symbol.
Output
Check whether it's a valid number theory expression. Either true/false or multi/one are allowed.
True samples (each symbol separated)
E a E b a < b
E b A x b < x & A x b > x
E b A x b < x & b > x
A b b + b < ( b + b ) * b | E x x < b
E x E y y < x & E x2 y = x2
E 1 A x x * 1 = x & E 2 2 * 2 = 2 + 2 & 2 > 1 & E x x + 1 = x * x * 2
E x E y y = y & y + y * y = y

False samples
E a E b a + b < c
E a E b b * ( a > a ) + b
A a A b ( a = b ) = b
A x A y A z A y x < z
E x E y y < x & E x y = x
E E x x = x
E x ( x < x
E x = x

Undefined behavior samples
E C C = C
AA x x = x
Ex = x

Shortest code in bytes win
Symbol definition: It's a resexpr
numexpr({s},∅) = s
numexpr(a∪b,c∪d) = numexpr(a,c) + numexpr(b,d)
numexpr(a∪b,c∪d) = numexpr(a,c) * numexpr(b,d)
numexpr(a,c) = ( numexpr(a,c) )
boolexpr(a∪b,c∪d) = numexpr(a,c) = numexpr(b,d)
boolexpr(a∪b,c∪d) = numexpr(a,c) < numexpr(b,d)
boolexpr(a∪b,c∪d) = numexpr(a,c) > numexpr(b,d)
boolexpr(a∪b,c∪d) = boolexpr(a,c) & boolexpr(b,d)
boolexpr(a∪b,c∪d) = boolexpr(a,c) | boolexpr(b,d)
boolexpr(a,c) = ! boolexpr(a,c)
boolexpr(a,c) = ( boolexpr(a,c) )
boolexpr(a-{s},c∪{s}) = E s boolexpr(a,c) if s∉c
boolexpr(a-{s},c∪{s}) = A s boolexpr(a,c) if s∉c
resexpr = boolexpr(∅,a)
a,b,c,d mean sets, s mean non-empty strings containing a-z0-9

Notes

You don't need to check whether the expression is true, as it's usually impossible

What does the symbol definition block mean in the challenge context?

@Nit It's like a BNF but with infinite expressions, so I write it in this kind of view. Different expressions can lead to same elementnumexpr(a,c), meaning "or" in BNF

Sandbox undeleted

@orlp I think that parsing and the expression being ambiguous is actually the main part of the challenge.

Holy moly I'm blind... The challenge is about syntax verification, not seeing whether the expression is true... Never mind...

I edited "Calculations should be correct" to "Arithmetic expressions should be syntactically valid", since the first made it sound like you had to confirm the actual truth value of the expression.

What does valid mean? Does it means that the input expression can be parsed to at least one AST, or exactly one AST (no ambiguous)?

@tsh At least one is enough. I here didn't consider logical order(a+b*c)

It says the inputs will only be split when necessary, but in the examples every symbol is separated, so how should we take the input??

@ValueInk only split when necessary (two variable names together), split after each quantifier variable, or each symbols are separated

APL (Dyalog Unicode), 318 317 319 bytesSBCS
∨/{(4=⊃⍵)>≢⊃1⌽⍵}¨{1=≢⍵:⍵⋄⊃,/(⊂⍵)∇{⊃,/,(⍺⍺⍵↑⍺)∘.{c←⊃¨⍺⍵⋄w←⊃,/⊃¨u v←1↓¨⍺⍵
(⊂c)∊t←↓10 2⍴⎕A⍳'AOBAJACKANEADMLDJDGK':⊂(2,u)(1w 0)(3,v)(1u 0)(5(⊃u)⍬)(4w⍬)(6,u)(4,v)(7,v)(4,u)⊃⍨t⍳⊂c
6 4≡c:⊂4,u,¨v
9 1≡c:(2⊃v)↑⊂8,v
8 4≡c:(a∊3⊃⍵)↓⊂4(a~⍨⊃v)((3⊃⍵),a←⊃u)
⍬}⍺⍺⍵↓⍺}¨⍳¯1+≢⍵}{⌈/c←(⊃⍵)∊¨¯1⌽'()!',↓4 3⍴' &|=<>+* AE':8+⊃⍸c⋄1(⊂⍵)1}¨' '(≠⊆⊢)⍞

Try it online!
-1 byte thanks to @Adám.
+2 bytes because the code wrongly accepted E ( a ) a = a. Fixed by adding a "simple" flag to the Num node, which is 1 right after tokenization but becomes 0 after any kind of merging. TQuant Num -> Quant rule is accepted only if "simple" is 1.
Full program. Takes a line of input (each symbol separated with a space) from stdin, and prints 1 if it can be parsed successfully, 0 otherwise.
How it works: the grammar & parsing
I manually dissected all the grammar rules into two-branch rules, e.g. the parenthesizing rule
"(" Num ")" -> Num

became two rules
"(" Num -> NumP
NumP ")" -> Num

with NumP being a new node type. Also, I omitted the last part of the Num node, as it is always an empty set.
(Num ids,?) [+*] -> (NumR ids)
(NumR ids) (Num ids2,?) -> (Num (ids+ids2),0)
"(" (Num ids,?) -> (NumP ids)
(NumP ids) ")" -> (Num ids,0)
(Num ids,?) [=<>] -> (BoolN ids,[])
(BoolN ids,ids3) (Num ids2,?) -> (Bool (ids+ids2),ids3)
(Bool ids,ids2) [&|] -> (BoolR ids,ids2)
(BoolR ids,ids3) (Bool ids2,ids4) -> (Bool (ids+ids2),(ids3+ids4))
"!" (Bool ids,ids2) -> (Bool ids,ids2)
"(" (Bool ids,ids2) -> (BoolP ids,ids2)
(BoolP ids,ids2) ")" -> (Bool ids,ids2)
[EA] (Num id,1) -> (Quant id)
(Quant id) (Bool ids,ids2) -> (Bool (ids-id),(ids2+id)) if id not in ids2

Using these rules, I could tackle the ambiguous parsing problem as follows:

Split the given list of tokens into two chunks.
Recursively get all possible parses for the two chunks.
Test all combinations of parses to gather all possible derived parses.
Repeat 1-3 for all possible splits, and gather all results.

The algorithm is exponential in the number of tokens, so the two longest test cases are excluded from the tests.
Original version with comments
⍝ Constants to classify the grammar node type
Num NumR NumP Bool BoolN BoolR BoolP Quant TQuant TParenL TParenR TNot TBool2 TCmp TNum2←⍳15

⍝ Split given string by spaces, and convert to a list of grammar nodes
tokenize←{
  words←(' '∘≠⊆⊢)⍵  ⍝ split by spaces
  {
    class←(⊃⍵)∊¨'AE' '(' ')' '!' '&|' '=<>' '+*'
    ⌈/class: 8+⊃⍸class  ⍝ Single-char tokens into respective nodes
    Num(⊂⍵)1  ⍝ An identifier is a Num node
  }¨words  ⍝ wrap each word into tokens
}

⍝ Takes two nodes, and gives a new node if valid, ⍬ otherwise
match←{
  class←⊃¨⍺⍵
  Num TNum2≡class: ⊂NumR(2⊃⍺)
  NumR Num≡class: ⊂Num((2⊃⍺),2⊃⍵)0
  TParenL Num≡class: ⊂NumP(2⊃⍵)
  NumP TParenR≡class: ⊂Num(2⊃⍺)0
  Num TCmp≡class: ⊂BoolN(2⊃⍺)⍬
  BoolN Num≡class: ⊂Bool((2⊃⍺),2⊃⍵)⍬
  Bool TBool2≡class: ⊂BoolR(2⊃⍺)(3⊃⍺)
  BoolR Bool≡class: ⊂Bool((2⊃⍺),2⊃⍵)((3⊃⍺),3⊃⍵)
  TNot Bool≡class: ⊂Bool(2⊃⍵)(3⊃⍵)
  TParenL Bool≡class: ⊂BoolP(2⊃⍵)(3⊃⍵)
  BoolP TParenR≡class: ⊂Bool(2⊃⍺)(3⊃⍺)
  ⍝ Valid only if "simple" flag of Num node is 1
  TQuant Num≡class: (3⊃⍵)↑⊂Quant(2⊃⍵)
  ⍝ Valid only if quantified variable is not already quantified
  Quant Bool≡class: (~(2⊃⍺)∊3⊃⍵)↑⊂Bool((2⊃⍵)~2⊃⍺)((3⊃⍵),2⊃⍺)
  ⍬
}

⍝ Given a list of tokens, returns an array of possible parses
⍝ Split in all possible ways and check for at least one split is valid
parse←{
  ⍝ Single token: no need to parse
  1=≢⍵:⍵
  splits←⍳¯1+≢⍵
  ⍝ Concatenate parses based on all possible splits
  ⊃,/(⊂⍵)∇{
    left←⍺⍺ ⍵↑⍺
    right←⍺⍺ ⍵↓⍺
    ⍝ Test all possible combinations of left/right parses
    ⊃,/,left ∘.match right
  }¨splits
}

⍝ Test if one of the parses is Bool with no free variables
test←{
  ∨/{
    Bool≠⊃⍵:0
    0=≢2⊃⍵
  }¨⍵
}

⍝ The solution is the chain of three functions defined above
test∘parse∘tokenize

Try it online!

(' '∘≠⊆⊢)⍞ → ' '(≠⊆⊢)⍞

Is (BoolN ids,ids2) defined for ids2 being not empty?

A slightly earlier accept than I usually do, because I recently don't active here

@l4m2 I guess it's always empty, though it wouldn't improve the byte count very much.

Wrong output at E ( a ) E b a < b. (Tried E(a+a) first, but then the set is {a,a}?)

@l4m2 I'll try to fix it when I have time. That means I have to fix the grammar itself anyway...

@l4m2 Fixed the bug in the grammar. Luckily there was an easy fix.

license: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/4.0/


text:
Largest rectangle in 2d array
Input
The board: A 2D container (matrix, list of lists, etc.) of letters like:
  ["B", "C", "C", "C", "C", "B", "B", "C", "A", "A"],
  ["B", "A", "C", "B", "B", "A", "B", "B", "A", "A"],
  ["B", "C", "B", "C", "A", "A", "A", "B", "C", "B"],
  ["B", "B", "B", "A", "C", "B", "A", "C", "B", "A"],
  ["A", "A", "A", "C", "A", "C", "C", "B", "A", "C"],
  ["A", "B", "B", "A", "A", "C", "B", "C", "C", "C"],
  ["C", "B", "A", "A", "C", "B", "B", "C", "A", "A"]

If you choose a list of lists you may assume that all of the sublists are of the same length.
Rules

To make a valid rectangle you need all rectangle corners with the same 'letter'.
Example, look the sample board with X bellow. You can see 'X' on (1,0) also on (4,0) also on ( 1,3) and on (4,3) then you have the rectange [1,0,4,3] that means from (1,0) to (4,3):

Sample board with X:
  ["B", "X", "C", "C", "X", "B", "B", "C", "A", "A"],
  ["B", "A", "C", "B", "B", "A", "B", "B", "A", "A"],
  ["B", "C", "B", "C", "A", "A", "A", "B", "C", "B"],
  ["B", "X", "B", "A", "X", "B", "A", "C", "B", "A"],
  ["A", "A", "A", "C", "A", "C", "C", "B", "A", "C"],
  ["A", "B", "B", "A", "A", "C", "B", "C", "C", "C"],
  ["C", "B", "A", "A", "C", "B", "B", "C", "A", "A"]

The goal is to find the rectangle or one of the rectangles with the largest area, calculated by (right-left+1)*(bottom-top+1)
If there are multiple rectangles with the same maximum area, output any one. Optionally the one with (top coordinate, left coordinate, right coordinate, bottom coordinate) lexicographically smallest.
Rectangles must have edges parallel to the board's edge.
Each letter is a printable ASCII char from A to Z (both included).

Output
The output should be the left-up and right-down positions of the largest area rectangle corners. For the first sample "board" the big square is the yellow one:

And the answer should be:

[1, 1, 8, 4]

A second example test case
An input of:
["C", "D", "D", "D", "A", "A"],
["B", "D", "C", "D", "A", "A"],
["B", "D", "D", "C", "A", "C"],
["B", "D", "B", "C", "A", "C"]

Should yield one of these three coordinate lists identifying an area six rectangles:

[1, 0, 2, 2]
[1, 0, 3, 1]
[3, 2, 5, 3]

This question is posted on Stack Overflow with title: How to find the largest rectangle in a 2D array formed by four identical corners? and with this rude JS solution (I can say "rude" because is my code ;) :
Ok, is my first post, be tolerant with me please. I will change all you say to improve the quiz.

Hi, welcome to PPCG! This seems to be a good challenge, but seems to lack any winning criterion. Typically, posts here are tagged [code-golf], which means that the shortest code (in bytes) wins.

I thought I would let you know that we have a sandbox that you can use to get feedback on questions before they are posted to the main site.  The sandbox is useful to pretty much everyone here but especially to beginners, who might not know all the rules and expectations we have.

@Arnauld, I ask for help to fix English but I guess the semantic was changed. Can you fix it?

May we use 1-indexing rather than 0 (so long as it is consistent)?

Some answers output the coordinates in sorting order for the "first" rectangle (i.e, top, left, bottom, right) instead of (left, top, right, bottom) as seen in your examples. Is this ok?

Less strict output formats usually encourage more answers, so something like ((left,top),(right,bottom)) should be fine too. I deleted my answer and answer again when the question is completely refined.

I'd suggest a test like ["A","A","B","C","D","E","F"],["G","H","I","J","K","L","G"],["A","A","M","N","O","P","Q"] -> [0,1,6,1] (the two G making an area of seven vs the four A making an area of six)

So now each individual letter counts as a rectangle of area 1 if all else fails?

@Neil, yes. Looks more elegant like this.

@user56656, all answers are awesome, I've read 'What's the “accepted answer”?' but I still have doubts. Can you explain to me which is usually the criteria to 'accept ans answer'? Are you so kind to help to me in this subject?
I would like to avoid any injustice.

Sure, If you are going to accept an answer it should be the shortest overall, this is how most people like things done on the site.  However there is no consequence for not doing so.  There is also a growing opinion that accepting answers is detrimental to the site.  I am of that opinion, and thus I never accept answers on my challenges.  What you do is up to you.

Hi @user56656, thanks about explanation. I agree all your comment.

Python 2, 148 130 bytes
lambda x,e=enumerate:min(((a-c)*(d-b),b,a,d,c)for a,y in e(x)for c,k in e(x)for b,g in e(y)for d,h in e(y)if g==h==k[b]==k[d])[1:]

Try it online!

Hi @ovs, is for you and inconvenient if I change the rule to figure up the area to: (x2-x1+1)×(y2-y1+1) as Angs did suggested?

I would like to relax some rules to encourage more answers. Can I?

@danihp Go ahead.This doesn't invalidate my answer, right?

Nop, your answer is right! Nice.

Retina, 163 162 bytes
Lw$`(?<=(.*\n)*((.)*))(?=(.))((.)*(?<=(.*))\4)((.*\n)*((?>(?<-3>.)*)(?=\4)(?>(?<-6>.)*))\4)?
$.7,$#1,$.2,-$.($5$#9*$5),$.2,$#1,$.7,$.($#1*_$#9*
4{N`
)m`^.*?,

0G`

Try it online! Edit: Saved 1 byte because the trailing ) matching the $.( is implicit. Explanation:
Lw$`(?<=(.*\n)*((.)*))(?=(.))((.)*(?<=(.*))\4)((.*\n)*((?>(?<-3>.)*)(?=\4)(?>(?<-6>.)*))\4)?

This regular expression matches rectangles. The groups are as follows: 1) Top row (as capture count) 2) Left column (as length) 3) Balancing to ensure the left corners align 4) Letter for the corners 5) Width + 1 (as length) 6) Balancing to ensure the right corners align 7) Right column (as length) 8) unused 9) Height (as capture count). The w option ensures that all possible widths of rectangles are matched for each given top left corner. The $ options lists the results using the following substitution pattern.
$.7,$#1,$.2,-$.($5$#9*$5),$.2,$#1,$.7,$.($#1*_$#9*

The substitutions are as follows: The right column, the top row, the left column, the negation of the area of the rectangle (literally calculated as the length of repeating the width string by one more than height number of times), the left column, the top row, the right column, followed by an expression that evaluates to the bottom row (a capture would have cost 12 bytes plus I've run out of single-digit variables). The first four captures represent the sort order in order of priority. As Retina sorts stably, a multicolumn sort can be established by sorting by each sort column in turn from least to greatest priority. (The area must be sorted in descending order, so a single string sort cannot be used.)
4{N`

Four numeric sorts are then performed.
)m`^.*?,

The sort column is then deleted after each sort.
0G`

The first entry is therefore now the desired result.
Note: The restriction on the choice of rectangle of a given area has since been relaxed and the following 144 143-byte version prefers a wider rather than a taller rectangle:
Lw$`(?<=(.*\n)*((.)*))(?=(.))((.)*(?<=(.*))\4)((.*\n)*((?>(?<-3>.)*)(?=\4)(?>(?<-6>.)*))\4)?
-$.($5$#9*$5);$.2,$#1,$.7,$.($#1*_$#9*
N`
0G`
.*;

Try it online!

Fails the lexicographical-min requirement (try the test case I added to the OP for example) (maybe also output can be in the wrong order??) TIO

(...yeah first two values in output are the wrong way around I think)

I just relaxed some restrictions (lexicographical-min requirement ). I hope don't be a problem for you.

...this will now need to match lines and points.

Fixing the lexicographical order cost 20 bytes :-( and I noticed that the area calculation changed, which cost another 2 bytes, but I don't know what @JonathanAllan means about points.

...and now it's been relaxed to make the lex check unnecessary.

(by "points" I meant a single element would now be a 1x1 rectangle)

@JonathanAllan Ugh, in that case, I think I'd better delete my answer, since the regex required to match degenerate rectangles is going to be fiendishly complex.

Can you not just output [0,0,0,0] when nothing matched?

@JonathanAllan That doesn't help for the 1xw and the hx1 rectangles, but I've found a solution anyway, only cost another 20 bytes...

Jelly, (27?)  29  28 bytes
27 if 1-based indexing is allowed - remove trailing ’
Fṙ1s2;Uœị³EaZI‘P
ZLpLŒċÇÞṪF’

A full program.
Try it online! (or see the other test case)
How?
Fṙ1s2;Uœị³EaZI‘P - Link 1, areaOrZero: list of pairs [[b,l],[t,r]]
F                - flatten the input                 [b,l,t,r]
 ṙ1              - rotate left one                   [l,t,r,b]
   s2            - split into twos                   [[l,t],[r,b]]
      U          - upend the input                   [[l,b],[r,t]]
     ;           - concatenate                       [[l,t],[r,b],[l,b],[r,t]]
         ³       - program's input
       œị        - multidimensional index into
          E      - all equal?                       X
            Z    - transpose the input              [[b,t],[l,r]]
           a     - logical AND (vectorises)         (if not X we now have [[0,0],[0,0]]
             I   - incremental differences          [t-b,r-l] (or [0,0] if not X)
              ‘  - increment (vectorises)           [t-b+1,r-l+1] (or [1,1] if not X)
               P - product                          area (or 1 if not X)

ZLpLŒċÇÞṪF’ - Main link: list of lists
Z           - transpose the input
 L          - length
   L        - length of the input
  p         - Cartesian product
    Œċ      - pairs with replacement
       Þ    - (stable) sort by:
      Ç     -   last link (1) as a monad
        Ṫ   - tail (note that the rightmost pre-sort represents the bottom-right 1x1
            -       so cannot be superseded by a non-matching rectangle)
         F  - flatten
          ’ - decrement (vectorises) (to get to 0-based indexing)

Perl 6, 83 73 bytes
{([X] (^$^a[0]X ^$a)xx 2).max:{[eq] $a[.[*;1];.[*;0]]and[*] 1 X-[Z-] $_}}

Try it online!
Returns a list of lists ((x0 y0) (x1 y1)).
Explanation
{
  ([X]                   # Cross product of corner pairs.
    (^$^a[0]             # Range of x coords.
     X                   # Cross product of coords.
     ^$a                 # Range of y coords.
    )xx 2                # Duplicate list.
  ).max:                 # Find maximum of all ((x0 y0) (x1 y1)) lists
  {                      # using the following filter.
    [eq]                 # All letters equal?
      $a[.[*;1];.[*;0]]  # Multidimensional subscript with y and x coord pairs.
    and                  # Stop if false.
    [*]                  # Multiply
      1 X-[Z-] $_        # for each axis 1 - (c0 - c1) == c1 - c0 + 1.
  }
}

JavaScript (ES6), 121 bytes
-1 byte thanks to @l4m2
-1 byte thanks to @tsh
+2 bytes to comply with the new rectangle scoring rule
Takes input as a matrix of strings. Returns 0-indexed coordinates: [x0, y0, x1, y1].
a=>a.map(b=(r,y)=>r.map((v,x)=>a.map((R,Y)=>R.map((V,X)=>V+R[x]+r[X]!=v+v+v|(A=(x+~X)*(y+~Y))<b||(o=[x,y,X,Y],b=A)))))&&o

Try it online!

a=>a.map(b=(r,y)=>r.map((v,x)=>a.map((R,Y)=>R.map((V,X)=>V+R[x]+r[X]!=v+v+v|(A=(X-x)*(Y-y))<=b||(o=[x,y,X,Y],b=A)))))&&o

If there are multiple rectangles with the same maximum area, output any one; maybe (A=...)<=b -> (A=...)<b?

@tsh That's now safe indeed. Thanks!

Haskell, 144 bytes
import Data.Array
o=assocs
f r=snd$maximum[((c-a+1)*(d-b+1),[a,b,c,d])|((a,b),x)<-o r,((c,d),y)<-o r,x==y,r!(a,d)==r!(c,b),x==r!(a,d),a<=c,b<=d]

Try it online!

You can remove b<=d, as long as you keep a<=c.

@ovs actually that wont work either (see the example I added TIO)

@nimi: I could argue that's just a matter of transposing the input.

It's ok for me. You can transposing the input.

Jelly, 24 bytes
XLṭLp`€p/⁺œị€EɗÐfI‘PɗÞ0Ṫ

Try it online!
⁺ proves to be useful.
Output format: [top,bottom],[left,right]. 1-indexing.

APL (Dyalog Classic), 38 bytes
a⊃⍨⊃⍒×/1+-/↑2 2∘⍴¨a←⍸≢¨↑∘.(∩¨)⍨∘.∩¨⍨↓⎕

Try it online!

Java 8, 208 205 bytes
m->{int r=0,R[]={},i=m.length,j,y,z,u,t,T;for(;i-->0;)for(j=m[i].length;j-->0;)for(y=i*j;y-->0;)if((T=m[i][j])==m[u=y/j][z=y%j]&T==m[i][z]&T==m[u][j]&r<(t=(i-u)*(j-z))){r=t;R=new int[]{z,u,j,i};}return R;}

Can definitely be golfed.. I now use the most obvious approach of using four three nested for-loops.
-3 bytes thanks to @ceilingcat combining the inner loops of rows and columns into a single loop.
Explanation:
Try it online.
m->{                         // Method with char-matrix parameter and int-array return-type
  int r=0,                   //  Largest area found, starting at 0
      R[]={},                //  Result coordinates, starting empty
      i=m.length,j,          //  x,y indices of the first corner
      y,z,                   //  x,y indices of the second corner
      u,t,T;                 //  Temp integers to reduce bytes
  for(;i-->0;)               //  Loop `i` over the rows
    for(j=m[i].length;j-->0;)//   Inner loop `j` over the columns
      for(y=i*j;y-->0;)      //    Inner loop over the rows and columns
        if((T=m[i][j])==m[u=y/j][z=y%j]
                             //      If the values at coordinates [i,j] and [y,z] are equal
           &T==m[i][z]       //      as well as the values at [i,j] and [i,z]
           &T==m[u][j]       //      as well as the values at [i,j] and [y,j]
           &r<(t=(i-u)*(j-z))){
                             //      And the current area is larger than the largest
          r=t;               //       Set `r` to this new largest area
          R=new int[]{z,u,j,i};}
                             //       And save the coordinates in `R`
  return R;}                 //  Return the largest rectangle coordinates `R`


text:
Block Rearrangement
So your task is to take a 3x3 block where -'s mean blank spaces, and *'s mean filled spaces, for example:
-**
-*-
*-*

and rearrange the block so that the *'s form an X, like this:
*-*
-*-
*-*

Input:
3x3 squares like above, they can be 3 lines, an array, or however you want.
Output: The shortest amount of moves to rearrange into an X. Each move is flipping 2 characters that are touching, and are horizontal from each other, vertical from each other, or diagonal from each other. If it's not possible, return any impossible output, for example 999 or -4242. 5 is the smallest such number.
Test Cases:
1) Output: 1
-**
-*-
*-*

2) Output: -1
-*-
-*-
*-*

3) Output: 3
---
-**
***

4) Output: 0
*-*
-*-
*-*

You can substitute the blank and non blank characters but be sure to include which is which in your post
Code Golf
Remember this is code golf the shortest code wins!

By flipping 2 characters, did you mean flip from space to * and vice versa, or exchange them?

What if there are more than five *? Can you add some more test cases?

@user202729 for example abc would be acb if you flipped the last 2 characters.

@StewieGriffin "if it's not possible return a -1" more than 5 * or less than 5 makes it impossible.

May we use something other than -1? For example 5 (impossible otherwise), or throwing an error?

Could you include a test case where there are more than 5 *s?

@JonathanAllan sure you can return any impossible input

Jelly, 26 bytes
5ḶḤd3ạŒ!Ṁ€€ḅ1Ṃ
T’d3Ç-L=5Ɗ?

Try it online!

Take a flat list as input.
Too bad that Jelly doesn't have "multidimensional truthy indices"... T€ṭ€"JẎ also works but takes 1 more byte.

Algorithm: There are 5 current block positions and 5 targets (destinations), the algorithm tries each of the 5! matching, and output the minimum sum of [source, destination] Chebyshev distance.

You may take a flat list ("however you want") ...maybe you can even take 0-based indices and have 24?

Haskell, 176 132 126 104 bytes
w=0:1:w
m a|sum a/=5=5|1>0=sum$[a!!4|3<-sum.map(a!!)<$>[[0,1,2],[0,3,6],[2,5,8],[6,7,8]]]++zipWith(*)a w

Try it online!

Takes a list of integers with 1 as the non-blank character. Sums the number of non-zero even-indexed squares, then adds 1 if any of the double move patterns are found (center square and edge column/row completely filled). The last part's a bit wasteful I think, probably could be much improved over this brute-force method. Returns 5 (an impossible output) on an impossible input.

Some tips: the length test can be shortened to sum[1|1<-a]. Function s to :(1-e,n+sum[1|b>e]) which you can inline to save another byte. You can use the otherwise guard in m to save pair of (). Finally, && on top level in a guard can be replaced by ,. ...

... all in all 157 bytes: Try it online!.

You can save another byte by using a sum on a list comprehension to cast a Boolean to int. Try it online!

Actually you can save quite a few bytes because once the pattern guards are gone you can just move the whole thing up into m. Try it online!

Also since every non-1 element of a must be 0 can't you use sum a instead of sum[1|1<-a]? Try it online!

@nimi Your tips are blowing my mind. Thanks for the help both of you.

I just realized since there can't be more than 1 side with all 1s unless the center is 0, you can do 3<- instead of elem 3$.  Also you can use sum.map(a!!) instead of sum<$>map(a!!).

Ok, I know I'm making quite a few comments but I realized that your q could be a bit shorter using zipWith this caused a chain reaction which wound up reducing the whole thing to 104 bytes. Try it online!

Python 2, 194 192 bytes
from itertools import*
f=lambda l,k=0:-(sum(l)!=5)or[1,0]*4!=l[:-1]and k<4and-~min(f(l[:a]+[l[b]]+l[a+1:b]+[l[a]]+l[b+1:],k+1)for a,b in combinations(range(9),2)if max(b/3-a/3,abs(a%3-b%3))<2)

Try it online!

Doesn't work with [0,1,0,1,0,1,1,1,0] (expected: 4, actual: 13).

@Bubbler fixed it

JavaScript (ES6), 123 bytes
Takes input as a 9-bit integer. Solves the puzzle by naively applying the rules, which has been proven not to be the shortest approach.
f=(n,k=b=-1)=>n^341?k>2?b:[3,6,9,10,17,18,20,34,36].map(m=>[1,8,8].map(M=>(x=n&(m*=M))&-x^x||f(n^m,k+1)))|b:!~b|k                            //
  n ^ 341 ?                     // if n does not match the target pattern:
    k > 2 ?                     //   if we've already done more than 3 moves:
      b                         //     we're not going to find a solution -> abort
    :                           //   else:
      [3,6,9,10,17,18,20,34,36] //     for each swap bitmask m
      .map(m =>                 //     and
      [1,8,8]                   //     for each multiplier M:
      .map(M =>                 //       apply the multiplier to m and
        (x = n & (m *= M))      //       apply the final bitmask to n -> this gives x
        & -x                    //       isolate the least significant bit of x
        ^ x ||                  //       if it's the only bit set,
        f(n ^ m, k + 1)         //       then swap the bits and make a recursive call
      )) | b                    //     end of both map() loops; return b
  :                             // else:
    !~b | k < b ? b = k + 1 : b //   this is a solution in k+1 moves: update b

NB: This codes performs some illegal moves beyond the top of the board when m is multiplied by 64. But they are simply ignored, as they can't possibly lead to a shorter solution than the best legal solution.
Below are the 9 base swap bitmasks and the target pattern. The top left corner is the most significant bit.
000  000  001  001  010  010  010  100  100     101
011  110  001  010  001  010  100  010  100     010 (341)
(3)  (6)  (9)  (10) (17) (18) (20) (34) (36)    101

Can you link a hexdump for testing? Also, I didn’t know 9 bit integers were possible in JS

@StanStrum Updated to a shorter version with a more straightforward encoding. (And yes: JS supports bitwise operations for up to 32 bits.)

Jelly, 26 bytes
“ċȤ‘ḤB;U$=a¥;Ḋm2ƊẠ€SɓSn5Nȯ

Try it online!
A monadic link.
How?
Inspired by Bubbler's Python answer; golfed to suit Jelly...
“ċȤ‘ḤB;U$=a¥;Ḋm2ƊẠ€SɓSn5Nȯ - Link: length 9 list of ones & zeros, X
“ċȤ‘                       - list of code-page indices     = [232,154]
    Ḥ                      - double                        = [464,308]
     B                     - to binary     = [[1,1,1,0,1,0,0,0,0],[1,0,0,1,1,0,1,0,0]]
        $                  - last two links as a monad:
       U                   -   upend       = [[0,0,0,0,1,0,1,1,1],[0,0,1,0,1,1,0,0,1]]
      ;                    -   concatenate = [[1,1,1,0,1,0,0,0,0],[1,0,0,1,1,0,1,0,0],[0,0,0,0,1,0,1,1,1],[0,0,1,0,1,1,0,0,1]]
           ¥               - last two links as a dyad:
          a                -   logical AND (vectorises)
         =                 -   equal? (vectorises)
                Ɗ          - last three links as a monad:
             Ḋ             -   dequeue X (remove leftmost element)
               2           -   literal two
              m            -   modulo slice (keeps the "edge-elements")
            ;              - concatenate
                 Ạ€        - all? for €ach (edge-elements: no-op
                           -                else: 1 for any cost-2 element 0 otherwise)
                   S       - sum
                    ɓ      - new dyadic chain ^that on the right; X on the left
                     S     - sum X
                       5   - literal five
                      n    - not equal?
                        N  - negate (-1 if not exactly 5 1s, 0 otherwise)
                         ȯ - logical OR with right

JavaScript, 85 bytes
s=>/^0*(10*){5}$/.test(s)*s.match(/(?=1.(..)*$|^1(..)?11.1|1.11(..)?1$)|$/g).length-1

This is a regex port of Bubbler's answer.
Input as a string of 0 / 1.

f=
s=>/^0*(10*){5}$/.test(s)*s.match(/(?=1.(..)*$|^1(..)?11.1|1.11(..)?1$)|$/g).length-1

document.write('
'+('
'+'<input type=checkbox>'.repeat(3)).repeat(3)+'
');
document.write('Answer: <output id=o></output>');
U=()=>o.value=f(ii.map(i=>i.checked?1:0).join``);
ii=[...document.querySelectorAll('input')];
ii.forEach((i,p)=>{
i.checked=!(p%2);
i.oninput=U;
});
U()
label{display:block;position:relative;overflow:hidden;width:20px;height:20px;}
input{position:absolute;top:-200%;}
input~span{width:100%;height:100%;display:block;border:1px solid black;box-sizing:border-box;}
input:focus~span{border-color:red;}
input:checked~span{background:#ace;}

Stax, 23 22 bytes
Ç╙╤Ü┤└åVτ┐├Y-²▼░█∩¡3ëâ

Run and debug it
This program takes an array of [0, 1] as input, and returns an integer number of moves, or an empty string if no solution is possible.
Consider this indices for the grid
0 1 2
3 4 5
6 7 8

If there are not exactly 5 1s in the input, then there is no solution, so we produce no output.
The centers of each side are the incorrect positions.  These are indices 1, 3, 5, and 7.  Summing the distance for each 1 in these positions will produce the final result.
For each 1 in an incorrect position its distance is either 1 or 2.  It will be 2 iff it's surrounded by other 1s.  For example, if there are 1s at indices [0, 1, 2, 4], then the distance for the incorrect 1 is 2.
With this in mind, consider this pseudo-code for getting the distance contributed to the result by index 1.

Read 4 bits from indices [1, 0, 2, 4].  This puts the incorrect position in the most significant position.
Convert these bits to a number b from 0 to 15.
When 0 <= b <= 7 the distance is 0.  When 8 <= b <= 14 the distance is 1.  When b == 15 the distance is 2.  This can be calculated using integer division by b * 2 / 15.

So the total distance can be calculated by repeating this process 4 times and rotating the grid in between.
1#5=4*  if the number of 1s is 5, then 4, else 0
D       repeat the rest of the program that many times
  x     push the value in the x register, which is initially the input
  3/    split into 3 rows
  rM    rotate 90 degrees
  $X    flatten back into single array, and save the "rotated" array in the X register
  A|2E  get the digits of 2^10 i.e. [1,0,2,4]
  @     read the bits from the current rotation at indices [1,0,2,4]
  :b    convert bits to integer
  H15/  double, then divide by 2
  +     add to running total

Run this one

Check the edit, any impossible value is accepted, not just -1 if that helps you

Yes. That saved 2 bytes.

Excel, 86 81 Bytes
=SUM(B1,A2,B3,C2)+B2*(AND(A1:A3)+AND(A1:C1)+AND(C1:C3)+AND(A3:C3))/(SUM(A1:C3)=5)

Old: When the 'impossible' output was -1
=IF(SUM(A1:C3)=5,SUM(B1,A2,B3,C2)+B2*(AND(A1:A3)+AND(A1:C1)+AND(C1:C3)+AND(A3:C3)),-1)

Uses 1 for filled and 0 for empty, input in range A1:C3.  Possible to golf further if we can return values other than -1 for "impossible".  Returns a #DIV/0! error on impossible grids
Operates on the same logic as Bubbler's Python answer.

Check the edit, any impossible value is accepted, not just -1


text:
Up go the bits!
Given an integer N perform the following steps: (using 9 as an example).

Receive input N. (9)
Convert N from base10 to base2. (1001)
Increase every bit by 1. (2112)
Treat the result as base3 and convert it back to base10. (68)
Return/Output the result.

Input
May be received in any reasonable number format.
You only need to handle cases where N > 0.

Output
Either return as a number or string, or print to stdout.

Rules

This is code-golf, the shortest code in bytes wins.
Default loopholes are forbidden.

Test Cases
1 -> 2
2 -> 7
5 -> 23
9 -> 68
10 -> 70
20 -> 211
1235 -> 150623
93825 -> 114252161

Python 2, 31 bytes
f=lambda n:n and 3*f(n/2)+n%2+1

Try it online!

Could you explain how this works?

+n%2+1 adds the rightmost binary bit plus 1 to the return value, n/2 right-shifts n by 1 binary bit, 3*f(n/2) recursively adds 3 times this computation on those right-shifted bits, and n and ends the recursion when n is 0

JavaScript (Node.js), 23 bytes
f=x=>x&&x%2+1+3*f(x>>1)

Try it online!

x>>1 is the same as x/2 isn't it?

@mbomb007 I thought and suggested the same just yet, but apparently it becomes Infinity in JS.. Try it online. (You might want to add a TIO-link to you answer, I4m2)

@mbomb007 No. 1>>1=0 while 1/2=0.5

Right, Python 2 uses integer division.

@mbomb007 ... Python?

Yeah. Look at the Python answer. That's the reason n/2 works in that one, and the reason I suggested it here.

Java (JDK 10), 44 bytes
long n(long x){return x<1?0:x%2+1+3*n(x/2);}

Try it online!

Maybe -~ will help?

No, precedence rules.

Same question to you: why long? :) And here I thought my sequence approach was smart.. You blew it out of the park in less than 5 minutes.. >.> :'(

@KevinCruijssen To be fair with you ...

Jelly, 4 bytes
B‘ḅ3

Try it online!

Binary, Increment, To-base, 3. That's really all that needs to be said.

@Adám Technically that's From-base, but yes, this is trivial in most, if not all, golfing languages.

Java 10, 81 52 bytes (Base conversion)
n->n.toString(n,2).chars().reduce(0,(r,c)->r*3+c-47)

Try it online.
-29 bytes thanks to @Holger.
Explanation:
n->{                         // Method with Long as both parameter and return-type
  n.toString(n,2)            //  Convert the input to a Base-2 String
  .chars().reduce(0,(r,c)->  //  Loop over its digits as bytes
    r*3+c-47)                //  Multiply the current result by 3, and add the digit + 1
                             //  (which is equal to increasing each digit by 1,
                             //  and then converting from Base-3 to Base-10)

Java 10, 171 167 151 150 149 bytes (Sequence)
n->{int t=31-n.numberOfLeadingZeros(n);return a(t+1)+b(n-(1<<t));};int a(int n){return--n<1?n+2:3*a(n)+1;}int b(int n){return n<1?0:n+3*b(n/=2)+n*2;}

-16 bytes thanks to @musicman523, changing (int)Math.pow(2,t) to (1<<t).
-1 byte thanks to @Holger, changing (int)(Math.log(n)/Math.log(2)) to 31-n.numberOfLeadingZeros(n).
Try it online.
Explanation:
n->{                         // Method with Integer as both parameter and return-type
  int t=31-n.numberOfLeadingZeros(n);
                             //  2_log(n)
  return a(t+1)              //  Return A060816(2_log(n)+1)
         +b(n-(1<<t));}      //   + A005836(n-2^2_log(n))

// A060816: a(n) = 3*a(n-1) + 1; a(0)=1, a(1)=2
int a(int n){return--n<1?n+2:3*a(n)+1;}

// A005836: a(n+1) = 3*a(floor(n/2)) + n - 2*floor(n/2).
int b(int n){return n<1?0:n+3*b(n/=2)+n*2;}

When we look at the sequence:
2,  7,8,  22,23,25,26,  67,68,70,71,76,77,79,80,  202,203,205,206,211,212,214,215,229,230,232,233,238,239,241,242, ...

We can see multiple subsequences:
A053645(n):
0,  0,1,  0,1,2,3,  0,1,2,3,4,5,6,7,  0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,  ...

A060816(A053645(n)):
2,  7,7,  22,22,22,22,  67,67,67,67,67,67,67,67,  202,202,202,202,202,202,202,202,202,202,202,202,202,202,202,  ...

A005836(A053645(n)+1)
0,  0,1,  0,1,3,4,  0,1,3,4,9,10,12,13,  0,1,3,4,9,10,12,13,27,28,30,31,36,37,39,40,  ...

So the sequence being asked is:
A060816(A053645(n)) + A005836(A053645(n)+1)

I suck at finding patterns, so I'm proud of what I found above.. Having said that, @user202729 found a better and shorter approach in Java within a few minutes.. :'(

Re n.toString(n,2).getBytes() ... I think manual conversion may be shorter.

"Arithmetic sequence" --> still use recursion?

BTW why long and not int?

@user202729 Good question, changed it to int and removed arithmetic

I think in the sequence version you can change out (int)Math.pow(2,t) for 1<<t...and then inline that expression and drop the variable i (152 bytes)

In real life, I’d use 31-Integer.numberOfLeadingZeros(n) instead of (int)(Math.log(n)/Math.log(2)), but it’s not shorter. Unless you use import static in the header, which might stretch the rules too far.

@Holger It actually is shorter, although only by 1 byte. Thanks, I'll edit it in. :)

I just tried to convert your first variant’s loop to a stream solution, with success: n -> n.toString(n,2).chars().reduce(0,(r,c)->r*3+c-47)

05AB1E, 5 bytes
b€>3β

Try it online!
b       binary
 €>     increment each
   3β   base 3

05AB1E, 5 bytes
2в>3β

Try it online!

S works for € too.

J, 7 bytes
3#.1+#:

Try it online!
Thanks Galen Ivanov for -4 bytes! I really need to improve my J golfing skill...

7 bytes: 3#.1+#:
TIO

Also thanks for the template, I need something to learn about : 0.

The template is not mine, I forgot who's its author.

That would be me :)

R, 55 43 bytes
function(n)(n%/%2^(x=0:log2(n))%%2+1)%*%3^x

Try it online!
Uses the standard base conversion trick in R, increments, and then uses a dot product with powers of 3 to convert back to an integer.
Thanks to @user2390246 for dropping 12 bytes!

Because the conversion to binary is not the final output, the order of the digits doesn't matter. So instead of floor(log(n)):0 you can do 0:log(n) and save some bytes: 43 bytes

@user2390246 of course, thank you.

APL (Dyalog), 10 bytes
3⊥1+2⊥⍣¯1⊢

Try it online!
    2⊥⍣¯1  binary
  1+       go guess
3⊥         base 3

Brachylog, 7 bytes
ḃ+₁ᵐ~ḃ₃

Try it online!
Explanation
Not that you really need one, but…
ḃ            To binary
 +₁ᵐ         Map increment
    ~ḃ₃      From ternary

Ruby, 27 bytes
f=->x{x>0?x%2+1+3*f[x/2]:0}

Try it online!

Python 2, 56 55 bytes
lambda n:int(''.join('12'[c>'0']for c in bin(n)[2:]),3)

Try it online!

Attache, 19 bytes
FromBase&3@1&`+@Bin

Try it online!
This is a composition of three functions:

FromBase&3
1&`+
Bin

This first converts to binary (Bin), increments it (1&`+), then converts to ternary (FromBase&3).
Alternatives
Non-pointfree, 21 bytes: {FromBase[Bin!_+1,3]}
Without builtins, 57 bytes: Sum@{_*3^(#_-Iota!_-1)}@{If[_>0,$[_/2|Floor]'(1+_%2),[]]}

Retina 0.8.2, 36 bytes
.+
$*
+`^(1+)\1
$1;1
^
1
+`1;
;111
1

Try it online! Explanation:
.+
$*

Convert from decimal to unary.
+`^(1+)\1
$1;1

Repeatedly divmod by 2, and add 1 to the result of the modulo.
^
1

Add 1 to the first digit too.
+`1;
;111

Convert from unary-encoded base 3 to unary.
1

Convert to decimal.

Japt, 6 bytes
¤cÄ n3
¤      // Convert the input to a base-2 string,
 c     // then map over it as charcodes.
  Ä    // For each item, add one to its charcode
       // and when that's done,
    n3 // parse the string as a base 3 number.

Takes input as a number, outputs a number.
Try it online!

Damnit! Why didn't I think of that? Nicely done.

MATL, 12 7 6 bytes
BQ3_ZA

Try it online!
Saved 5 bytes thanks to Giuseppe and another one thanks to Luis Mendo.
Old 7 byte answer:
YBQc3ZA

Try it online!
Explanation:
YB        % Convert to binary string
  Q       % Increment each element
   c      % Convert ASCII values to characters
    3     % Push 3
     ZA   % Convert from base 3 to decimal.

Old one for 12 bytes:
BQtz:q3w^!Y*

Try it online!
Oh my, that was messy... So is this: `BQ3GBn:q^!Y*.
Explanation:
               % Implicit input
B              % Convert to binary vector
 Q             % Increment all numbers
  t            % Duplicate
   z           % Number of element in vector
    :          % Range from 1 to that number
     q         % Decrement to get the range from 0 instead of 1
      3        % Push 3
       w       % Swap order of stack
        ^      % Raise 3 to the power of 0, 1, ...
         !     % Transpose
          Y*   % Matrix multiplication
               % Implicit output

C# (Visual C# Compiler), 128 bytes
using System;using System.Linq;i=>{int z=0;return Convert.ToString(i,2).Reverse().Select(a=>(a-47)*(int)Math.Pow(3,z++)).Sum();}

Try it online!
I am counting System because i use Convert and Math.

Select gives you the index as optional parameter. So you could get rid of your z variable. Also in the expression body you could get rid of the {, } and return statements. So something like this n=>Convert.ToString(n,2).Reverse().Select((x,i)=>(x-47)*Math.Pow(3,i)).Sum();

Python 2, 56 54 bytes
lambda i:int(''.join(`int(x)+1`for x in bin(i)[2:]),3)

Try it online!

PHP, 84 64 Bytes
Try it online!!
ORIGINAL Code
function f($n){$b=decbin($n);echo base_convert($b+str_repeat('1',strlen($b)),3,10);}

Try it online!!
Thanks to Cristoph, less bytes if ran with php -R
function f($n){echo base_convert(strtr(decbin($n),10,21),3,10);}

Explanation
function f($n){
$b=decbin($n);                    #Convert the iteger to base 2
echo base_convert(                  #base conversion PHP function
    $b+str_repeat('1',strlen($b)),  #It adds to our base 2 number
    3,                              #a number of the same digits length
    10);                            #with purely '1's
}

Here is when i see i have a loooogn way to go at programming....had no idea of the existence of strtr

Will do!!, sorry <?="Will do!!"

C, 32 27 bytes
n(x){x=x?x%2+1+3*n(x/2):0;}

Based on user202729's Java answer. Try it online here.
Thanks to Kevin Cruijssen for golfing 5 bytes.
Ungolfed version:
n(x) { // recursive function; both argument and return type are implicitly int
    x = // implicit return
    x ? x % 2 + 1 + 3*n(x/2) // if x != 0 return x % 2 + 1 + 3*n(x/2) (recursive call)
    : 0; // else return 0
}

You can save 5 bytes by replacing the return with x= and reversing the ternary so the ! is no longer necessary: n(x){x=x?x%2+1+3*n(x/2):0;}

@KevinCruijssen Nice. Thanks!

Octave with the communication toolbox, 33 32 bytes
@(x)(de2bi(x)+1)*3.^(0:log2(x))'

Try it online!
Converts the input to a binary vector using de2bi, and incrementing all numbers. Does matrix multiplication with a vertical vector of 3 raised to the appropriate powers: 1, 3, 9, ..., thus getting the sum without an explicit call to sum.

While this is extremely clever, you can also do this for 32 bytes: Try it online!

And with MATLAB you may even do @(x)base2dec(de2bi(x)+49,3) for 27 (a rare occasion where MATLAB is more lenient than Octave)

Husk, 5 bytes
B3m→ḋ

Try it online!
Explanation
B3m→ḋ
    ḋ  Convert to base 2
  m→   Map increment
B3     Convert from base 3

CJam, 8 bytes
ri2b:)3b

Try it online!
Explanation
ri   e# Read input as an integer
2b   e# Convert to base 2. Gives a list containing 0 and 1
:)   e# Add 1 to each number in that list
3b   e# Convert list from base 3 to decimal. Implicitly display

I kinda like the :) ..

Brain-Flak, 74 bytes
({<>(())<>({<({}[()])><>([{}]())<>})}(<>)){{}((({})()){}{}[{}])([][()])}{}

Try it online!
"Readable" version
({<>(())<>
  ({
    <({}[()])>
    <>
    ([{}]())
    <>
  })
}
# At this point we have a inverted binary string on the stack
(<>)
)
{
  {}
  (
    (({})()){}{}[{}]
  )
  ([][()])
}{}

-2 bytes

Ruby, 28 bytes
f=->x{x>0?x%2+3*f[x>>1]+1:0}

black magic, no idea how it works
Try it online!

the left shift gets binary digits right to left, and x%2+1 increases the binary value according to the spec.

Whitespace, 117 bytes
[S S S N
_Push_0][S N
S _Duplicate_0][S N
S _Duplicate_0][T   N
T   T   _Read_STDIN_as_number][T    T   T   _Retrieve][N
S S S N
_Create_Label_OUTER_LOOP][S N
S _Duplicate][S S S T   S N
_Push_2][T  S T T   _Modulo][S S S T    N
_Push_1][T  S S S _Add][S N
T   _Swap][S S S T  S N
_Push_2][T  S T S _Integer_division][S N
S _Duplicate][N
T   S N
_If_0_jump_to_Label_INNER_LOOP][N
S N
S N
_Jump_to_Label_OUTER_LOOP][N
S S N
_Create_Label_INNER_LOOP][S S S T   T   N
_Push_3][T  S S N
_Multiply][T    S S S _Add][S N
T   _Swap][S N
S _Duplicate][N
T   S T N
_If_0_jump_to_Label_PRINT_AND_EXIT][S N
T   _Swap][N
S N
N
_Jump_to_Label_INNER_LOOP][N
S S T   N
_Create_Label_PRINT_AND_EXIT][S N
T   _Swap][T    N
S T _Output_integer_to_STDOUT]

Letters S (space), T (tab), and N (new-line) added as highlighting only.
[..._some_action] added as explanation only.
Try it online (with raw spaces, tabs and new-lines only).
Explanation in pseudo-code:
I first converted the recursive function int f(int n){return n<1?0:n%2+1+3*f(n/2);} to its iterative form (in pseudo-code):
Integer n = STDIN as integer
Add starting_value 0 to the stack
function OUTER_LOOP:
  while(true){
    Add n%2+1 to the stack
    n = n/2
    if(n == 0):
      Jump to INNER_LOOP
    Else:
      Jump to next iteration OUTER_LOOP

function INNER_LOOP:
  while(true){
    n = 3*n
    n = n + Value at the top of the stack (the ones we calculated with n%2+1)
    Swap top two items
    Check if the top is now 0 (starting value):
      Jump to PRINT_AND_EXIT
    Else:
      Swap top two items back
      Jump to next iteration INNER_LOOP

function PRINT_AND_EXIT:
  Swap top two items back
  Print top to STDOUT as integer
  Exit program with error: Exit not defined

And I then implemented this iterative approach in the stack-based language Whitespace, using it's default stack.
Example runs:
Input: 1
Command    Explanation                   Stack           Heap    STDIN   STDOUT   STDERR

SSSN       Push 0                        [0]
SNS        Duplicate top (0)             [0,0]
SNS        Duplicate top (0)             [0,0,0]
TNTT       Read STDIN as integer         [0,0]           {0:1}   1
TTT        Retrieve                      [0,1]           {0:1}
NSSSN      Create Label OUTER_LOOP       [0,1]           {0:1}
 SNS       Duplicate top (1)             [0,1,1]         {0:1}
 SSSTSN    Push 2                        [0,1,1,2]       {0:1}
 TSTT      Modulo top two (1%2)          [0,1,1]         {0:1}
 SSSTN     Push 1                        [0,1,1,1]       {0:1}
 TSSS      Add top two (1+1)             [0,1,2]         {0:1}
 SNT       Swap top two                  [0,2,1]         {0:1}
 SSSTSN    Push 2                        [0,2,1,2]       {0:1}
 TSTS      Int-divide top two (1/2)      [0,2,0]         {0:1}
 SNS       Duplicate top (0)             [0,2,0,0]       {0:1}
 NTSN      If 0: Go to Label INNER_LOOP  [0,2,0]         {0:1}
 NSSN      Create Label INNER_LOOP       [0,2,0]         {0:1}
  SSSTTN   Push 3                        [0,2,0,3]       {0:1}
  TSSN     Multiply top two (0*3)        [0,2,0]         {0:1}
  TSSS     Add top two (2+0)             [0,2]           {0:1}
  SNT      Swap top two                  [2,0]           {0:1}
  SNS      Duplicate top (0)             [2,0,0]         {0:1}
  NTSTN    If 0: Jump to Label PRINT     [2,0]           {0:1}
  NSSTN    Create Label PRINT            [2,0]           {0:1}
   SNT     Swap top two                  [0,2]           {0:1}
   TNST    Print top to STDOUT           [0]             {0:1}           2
                                                                                error

Try it online (with raw spaces, tabs and new-lines only).
Stops with error: Exit not defined.
Input: 4
Command    Explanation                   Stack           Heap    STDIN   STDOUT   STDERR

SSSN       Push 0                        [0]
SNS        Duplicate top (0)             [0,0]
SNS        Duplicate top (0)             [0,0,0]
TNTT       Read STDIN as integer         [0,0]           {0:4}   4
TTT        Retrieve                      [0,4]           {0:4}
NSSSN      Create Label OUTER_LOOP       [0,4]           {0:4}
 SNS       Duplicate top (4)             [0,4,4]         {0:4}
 SSSTSN    Push 2                        [0,4,4,2]       {0:4}
 TSTT      Modulo top two (4%2)          [0,4,0]         {0:4}
 SSSTN     Push 1                        [0,4,0,1]       {0:4}
 TSSS      Add top two (0+1)             [0,4,1]         {0:4}
 SNT       Swap top two                  [0,1,4]         {0:4}
 SSSTSN    Push 2                        [0,1,4,2]       {0:4}
 TSTS      Int-divide top two (4/2)      [0,1,2]         {0:4}
 SNS       Duplicate top (2)             [0,1,2,2]       {0:4}
 NTSN      If 0: Go to Label INNER_LOOP  [0,1,2]         {0:4}
 NSNSN     Jump to Label OUTER_LOOP      [0,1,2]         {0:4}
 SNS       Duplicate top (2)             [0,1,2,2]       {0:4}
 SSSTSN    Push 2                        [0,1,2,2,2]     {0:4}
 TSTT      Modulo top two (2%2)          [0,1,2,0]       {0:4}
 SSSTN     Push 1                        [0,1,2,0,1]     {0:4}
 TSSS      Add top two (0+1)             [0,1,2,1]       {0:4}
 SNT       Swap top two                  [0,1,1,2]       {0:4}
 SSSTSN    Push 2                        [0,1,1,2,2]     {0:4}
 TSTS      Int-divide top two (2/2)      [0,1,1,1]       {0:4}
 SNS       Duplicate top (1)             [0,1,1,1,1]     {0:4}
 NTSN      If 0: Go to Label INNER_LOOP  [0,1,1,1]       {0:4}
 NSNSN     Jump to Label OUTER_LOOP      [0,1,1,1]       {0:4}
 SNS       Duplicate top (1)             [0,1,1,1,1]     {0:4}
 SSSTSN    Push 2                        [0,1,1,1,1,2]   {0:4}
 TSTT      Modulo top two (1%2)          [0,1,1,1,1]     {0:4}
 SSSTN     Push 1                        [0,1,1,1,1,1]   {0:4}
 TSSS      Add top two (1+1)             [0,1,1,1,2]     {0:4}
 SNT       Swap top two                  [0,1,1,2,1]     {0:4}
 SSSTSN    Push 2                        [0,1,1,2,1,2]   {0:4}
 TSTS      Int-divide top two (1/2)      [0,1,1,2,0]     {0:4}
 SNS       Duplicate top (0)             [0,1,1,2,0,0]   {0:4}
 NTSN      If 0: Go to Label INNER_LOOP  [0,1,1,2,0]     {0:4}
 NSSN      Create Label INNER_LOOP       [0,1,1,2,0]     {0:4}
  SSSTTN   Push 3                        [0,1,1,2,0,3]   {0:4}
  TSSN     Multiply top two (0*3)        [0,1,1,2,0]     {0:4}
  TSSS     Add top two (2+0)             [0,1,1,2]       {0:4}
  SNT      Swap top two                  [0,1,2,1]       {0:4}
  SNS      Duplicate top (1)             [0,1,2,1,1]     {0:4}
  NTSTN    If 0: Jump to Label PRINT     [0,1,2,1]       {0:4}
  SNT      Swap top two                  [0,1,1,2]       {0:4}
  NSNN     Jump to Label INNER_LOOP      [0,1,1,2]       {0:4}
  SSSTTN   Push 3                        [0,1,1,2,3]     {0:4}
  TSSN     Multiply top two (2*3)        [0,1,1,6]       {0:4}
  TSSS     Add top two (1+6)             [0,1,7]         {0:4}
  SNT      Swap top two                  [0,7,1]         {0:4}
  SNS      Duplicate top (1)             [0,7,1,1]       {0:4}
  NTSTN    If 0: Jump to Label PRINT     [0,7,1]         {0:4}
  SNT      Swap top two                  [0,1,7]         {0:4}
  NSNN     Jump to Label INNER_LOOP      [0,1,7]         {0:4}
  SSSTTN   Push 3                        [0,1,7,3]       {0:4}
  TSSN     Multiply top two (7*3)        [0,1,21]        {0:4}
  TSSS     Add top two (1+21)            [0,22]          {0:4}
  SNT      Swap top two                  [22,0]          {0:4}
  SNS      Duplicate top (0)             [22,0,0]        {0:4}
  NTSTN    If 0: Jump to Label PRINT     [22,0]          {0:4}
  NSSTN    Create Label PRINT            [22,0]          {0:4}
   SNT     Swap top two                  [0,22]          {0:4}
   TNST    Print top to STDOUT           [0]             {0:4}           22
                                                                                error

Try it online (with raw spaces, tabs and new-lines only).
Stops with error: Exit not defined.

At this point, why not write assembly? Also I have a slightly simpler iterative method in my answer https://codegolf.stackexchange.com/a/161833/17360

I've simplified my python pseudocode further.

@qwr Your Python code is almost the same as the displayed Java code. Java is just more verbose and error-prone. The only difference is that my Java code is a nested while-loop, and yours is separated. I could do that as well in Java, but since it's nested in Whitespace I chose to write it as such in the Java pseudo-code as well. Also, Whitespace doesn't have any way to know the number of items left on the stack, which is why I push the 0 at the start, and in the INNER_LOOP part of the code do: swap, check if 0, swap back. Nice Assembly answer, though. So I've +1-ed it. :)

I still think you can get rid of the n < 1 check by pushing values until n is 0 and then popping them until you hit your boundary value (0). The stack depth doesn't need to be stored explicitly and there shouldn't even need to be swapping (if you mean swapping the top two values like in lisp)

@qwr "I still think you can get rid of the n < 1 check by pushing values until n is 0" Umm.. checking if n < 1 (or n == 0) IS pushing values until n is 0.. Or am I misinterpreting something here.. :S "The stack depth doesn't need to be stored explicitly" In Java it does, otherwise I can't create the array. I could have used a java.util.Stack instead, but I just used an array to make it less verbose. In Whitespace the stack is of undefined size.

As for the swap: Whitespace has no way to know the size of the stack left, and just continues until you tell it to stop, or until it errors out, so I need the swap and check if I've reached the 0 I pushed before starting the loop it to know when to stop (I could have used -1 and a check_if_negative instead, but it would be 1 more byte). Without that swap and check it would just continue looping and errors when it tries to do the Add_top_two action inside the INNER_LOOP with only a single item left on the stack, in which case I can't print to STDOUT anymore, hence the check.

@qwr I've removed the Java code because it only seemed to confuse you, and added actual pseudo-code instead.

Vyxal, 4 bytes
b›3β

Try it Online!
b    # Binary
 ›   # Increment
  3β # From base 3

Add++, 14 bytes
L,BBu1€+B]3$Bb

Try it online!

Japt, 7 bytes
¤£°XÃn3

Try it here

Stax, 7 bytes
É¥ê4¼⌐○

Run and debug it
This one is pretty straightforward.  After unpacking, and commenting, the program looks like this.
:B  Convert to bits
{^m Increment each
3|b Base-3 convert

Haskell, 32 bytes
f 0=0
f a=1+mod a 2+3*f(div a 2)

Try it online!

Pyth, 8
ihMjQ2 3

How to eliminate the space and make the Q implicit?
Pyth online.

I believe this is actually 8 bytes

@hakr14 Yes, you're right

How to eliminate the space and make the Q implicit? I don't think you can.

Perl 5, 36 bytes
$\+=(1+$_%2)*3**$b++,$_>>=1while$_}{

Try it online!

dc, 66 bytes
[2~rd0<B]dsBxz1-si[1+z:tz0<T]dsTx0dsj[ljd1+dsj;tr3r^*+ljli>M]dsMxp

Try it online!
[2~rd0<B]dsBx is a macro that uses dc's quotient/remainder integer division, ~ to continuously break divide by two, breaking n down to individual binary bits on the stack. It will always leave one extra zero, so we subtract one from the stack depth and store this total length in i with z1-si.
[1+z:tz0<T]dsTx is a macro that adds one to whatever is on the stack, and then pops that value, storing it at index(stack depth) in array t. This basically means that if we started with the binary 1101, t now holds 2, 1, 2, 2, assuming 1-indexing. 0dsj puts a zero on the stack so we don't get a stack empty error when we do our first addition, and it stores a zero in register j as well.
[ljd1+dsj;tr3r^*+ljli>M]dsMx is, unfortunately, a lot of counter nonsense. We need register j for two things - pull element (j+1) from array t, and multiply it by 3^j. We start macro M by putting j on the stack and duplicating it. We increment the new copy, duplicate it, and store it back into j. With the copy of (j+1) we left behind, we pull from array t. Swap so that our original j is at the top of the stack, do the necessary base-three math with 3r^*, add this 'bit' to our total, and then compare j with i to see if we still have more 'bits' to do. At the very end, we print.

Excel, 54 bytes
=DECIMAL(SUBSTITUTE(SUBSTITUTE(BASE(A1,2),1,2),0,1),3)

A fairly straightforward translation of the problem. Takes input from A1. I tried some cuter things with bit math like
=SUM(IF(ROW(1:31)<LOG(A1,2)+1,POWER(3,ROW(1:31)-1)*(1+MOD(BITRSHIFT(A1, ROW(1:31)-1),2))))

because nesting SUBSTITUTE always feels wasteful, but couldn't get nearly as short.

Try +REPT(1,LEN(BASE(A1,2))) instead of nesting SUBSTITUTE?

Or, even +REPT(1,1+LOG(A2,2)), since REPT ignores the non-integer portion of the number

It's a good suggestion but I couldn't make it work for the range covered by the test cases. The complete solution there is =DECIMAL(REPT(1,1+LOG(A1,2))+BASE(A1,2),3) which is only 43 bytes! But unfortunately it gets the wrong answer even for the  93825 test case, due to rounding error as it passes through a representation as a double, and I can't figure out how to work around that.

Jstx, 7 bytes
£?☺å♥£F

Try it online!
Explanation
£? # Push the first stack value in binary.
☺  # Push literal 1
å  # Push the second stack value with all characters arithmetically shifted by the first stack value.
♥  # Push literal 3
£F # Push the second stack value in base first stack value converted to decimal.

x86, 26 bytes
Rewrite of the recursive formula as a tail-recursive stack function, since  function calls are expensive. Uses __fastcall convention (input in ecx, output in eax).
The cmp %esp,%ebp/je sum1 branch is done to prevent an extra multiplication of 3 from occurring. It might save bytes to avoid this branch. Reordering the multiplication makes this unnecessary and saves 4 bytes.
.section .text
.globl main
main:
        mov     $10, %ecx

start:
        mov     %esp, %ebp          # Save sp
build:
        mov     %ecx, %eax
        and     $1, %eax
        inc     %eax                # n%2 + 1
        push    %eax                # push n%2 + 1
        sar     %ecx                # n >>= 1
        jnz     build               # do while (n)

        xor     %eax, %eax          # sum = 0
sum0:
        lea     (%eax,%eax,2),%eax  # sum *= 3
        pop     %ebx
        add     %ebx, %eax          # pop stack, add to sum
        cmp     %esp, %ebp
        jnz     sum0                # do while stack non-empty

        ret

Hexdump:
00000039  89 e5 89 c8 83 e0 01 40  50 d1 f9 75 f5 31 c0 8d  |.......@P..u.1..|
00000049  04 40 5b 01 d8 39 e5 75  f6 c3                    |.@[..9.u..|

Assembly-friendly python:
stack = []
while n:
    stack.append(n%2 + 1)
    n //= 2

while stack:
    s *= 3
    s += stack.pop()

Julia 0.6, 34 bytes
x->parse(Int,map(x->x+1,bin(x)),3)

Try it online!
Tho it seems like this is the cool way
Julia 0.6, 25 bytes
f(n)=n<1?0:n%2+1+3f(n÷2)

Try it online!

Zsh, 37 bytes
a=3#$[[##2]$1];echo $[a+${a//[01]/1}]

Try it online!

$[...] is another (deprecated?) form of $(( ))
[#n] in arithmetic expansion sets the output base but includes the base in output (so you get 2#1001), [##n] omits the base in output: 1001.
n# in arithmetic expansion sets the input base
${var//pat/rep} replaces all matches of pat with rep.

AWK, 43 bytes
func n(x){return x<1?0:x%2+1+3*n(int(x/2))}

Try it online!
I discovered that AWK has rshift and lshift functions.  They use more bytes than just doing a divide and cast, but might be useful sometime. :)

Bash + GNU utilities, 28
dc -e?2op|tr 01 12|dc -e3i?p

Input read from STDIN.
Try it online!

Pari/GP, 25 bytes
f(n)=if(n,n%2+1+3*f(n\2))

Try it online!

brainfuck, 50 bytes
+<,[[>-]++>[<]<[>+[<]<]>>-]>[>]<-<<[>[-<+++>]<<]>.

Try it online!
Input and output as code points, and assumes arbitrary size cells otherwise it can't get past n=31.

Go, 54 bytes
func f(n int)(o int){if n>0{o=n%2+1+3*f(n>>1)};return}

Base solution is the same as the one that everyone else uses.
Try it online!

Thunno 2, 4 bytes
ḃ⁺3b

Try it online!
Explanation
ḃ⁺3b  # Implicit input
ḃ     # Convert to binary
 ⁺    # Increment each
  3b  # Convert from base-3
      # Implicit output