title: Stack Exchange Vote Simulator

text:
# Question
Title: Stack Exchange Vote Simulator
Write a program or function that takes in a string only containing the characters `^` and `v` (you can assume there will be no other characters). Read from left to right this string represents the sequence of mouse clicks a single user made while viewing a Stack Exchange question or answer for the first time.

Every `^` represents a click of the upvote button and every `v` represents a click of the downvote button. (For working examples look slightly left.)

Assume that no voting limitations are in effect so all the clicks are registered correctly.
Print or return:

* `1` or `+1` if the post ends up being upvoted.
* `0` if the post ends up not being voted on. (`-0` and `+0` are not valid)
* `-1` if the post ends up being downvoted.

Posts start with zero net votes from the user and the buttons change the net votes as follows:

```
Net Votes Before    Button Pressed    Net Votes After
1                   ^                 0
1                   v                 -1
0                   ^                 1
0                   v                 -1
-1                  ^                 1
-1                  v                 0

```

The shortest code in bytes wins.

**Test cases:**

```
[empty string] -> 0
^^ -> 0
^v -> -1
^ -> 1
v -> -1
v^ -> 1
vv -> 0
^^^ -> 1
vvv -> -1
^^^^ -> 0
vvvv -> 0
^^^^^ -> 1
vvvvv -> -1
^^^^^^ -> 0
vvvvvv -> 0
^^v -> -1
^v^ -> 1
^vv -> 0
vv^ -> 1
v^v -> -1
v^^ -> 0
^vvv^^vv^vv^v^ -> 1
^vvv^^vv^vv^v^^ -> 0
^vvv^^vv^vv^v^^^ -> 1
^vvv^^vv^vv^v^^v -> -1
^vvv^^vv^vv^v^^vv -> 0
^vvv^^vv^vv^v^^vvv -> -1
^vvvvvvvvvvvv -> 0
^^vvvvvvvvvvvv -> 0
^^^vvvvvvvvvvvv -> 0
vvv^^^^^^^^^^^^ -> 0
vv^^^^^^^^^^^^ -> 0
v^^^^^^^^^^^^ -> 0

```

# Answer
> 35 votes
## Gol\>\<\> 0.3.11, ~~13~~ ~~12~~ 11 bytes

```
iEh`^=:@)+M

```

Try it online. Even though this will work fine in the next update, I've listed it as 0.3.11 just in case.

### Explanation

```
i               Read char
 Eh             If EOF, halt and output top of stack as num
   `^=          Push 1 if char is ^, else 0
      :@        Dup and rotate, giving [is^ is^ votecount]
        )       Compare greater than, pushing 1 or 0 as appropriate
         +M     Add and subtract 1

```

Note that the first use of `@` pulls a 0 from the bottom of the stack to initialise the vote count for the first iteration

To illustrate with a full table:

```
Votes before    Button    Is ^?    Compare <    Add     Subtract 1
     1            ^         1         0          1          0
     1            v         0         0          0         -1
     0            ^         1         1          2          1
     0            v         0         0          0         -1
    -1            ^         1         1          2          1
    -1            v         0         1          1          0

```

# Answer
> 21 votes
# JavaScript (ES7), ~~47~~ ~~46~~ ~~44~~ ~~43~~ ~~37~~ 36 bytes

Crossed out 44 is still regular 44 :(

```
s=>[for(x of s)s=x<"v"?s!=1:!~s-1]|s

```

Keeps a running total in `s`. Uses `for of` loop to iterate over each character in the string and updates `s` based on current character and previous value.

Edits: Golfed `~s&&-1` to `!~s-1`. This expression has to equal 0 if `s` equals -1 and -1 otherwise. Saved 6 bytes thanks to @nderscore.

How the expression works:

```
 ~s    // Bitwise inverse. ~s==0 only if s==-1
!      // Logical negate. Casts to boolean. Equivalent to s==-1
   -1  // Subtract. Casts to number so true-1 is 1-1 and false-1 is 0-1

```

# Answer
> 20 votes
# x86 machine code, 24 bytes

```
31 C0 8A 11 84 D2 75 07 C0 E0 02 C0 F8 06 C3 41 38 C2 74 EC 88 D0 EB EA

```

This is a function using the fastcall calling convention, which takes a string and returns an 8-bit integer.

I tested it with the following C program, which must be compiled for 32-bit mode.

```
#include <stdio.h>
#include <inttypes.h>

 __attribute__ ((aligned (16))) const unsigned char fun[] = {

    0x31,  //xor eax,eax
        0xC0,
    0x8A, //mov [ecx],dl
        1 | 2<<3,
    0x84, //test dl, dl
        0xC0 | 2<<3 | 2,
    0x75, // jnz
        7,
    0xC0, //shl al 2
        0xC0 | 4<<3,
        2,
    0xC0, //sar al 6
        0xC0 | 7<<3,
        6,
    0xC3, //ret
    0x41, //inc ecx
    0x38, //cmp al,dl
        0xC0 | 2,
    0x74, //je
        -20,
    0x88, //mov dl,al
        0xC0 | 2<<3,
    0xEB, //jmp
        -22,
};

int main()
{
    __fastcall int8_t (*votesimulator)(char*) = fun;
    char* s[] = {
        "",
        "^^",
        "^v",
        "^",
        "v",
        "v^",
        "vv",
        "^^^",
        "vvv",
        "^^^^",
        "vvvv",
        "^^^^^",
        "vvvvv",
        "^^^^^^",
        "vvvvvv",
        "^^v",
        "^v^",
        "^vv",
        "vv^",
        "v^v",
        "v^^",
        "^vvv^^vv^vv^v^",
        "^vvv^^vv^vv^v^^",
        "^vvv^^vv^vv^v^^^",
        "^vvv^^vv^vv^v^^v",
        "^vvv^^vv^vv^v^^vv",
        "^vvv^^vv^vv^v^^vvv",
        "^vvvvvvvvvvvv",
        "^^vvvvvvvvvvvv",
        "^^^vvvvvvvvvvvv",
        "vvv^^^^^^^^^^^^",
        "vv^^^^^^^^^^^^",
        "v^^^^^^^^^^^^",
    };

    for(int i = 0; i < sizeof(s)/sizeof(*s); i++)
        printf("%d\n", votesimulator(s[i]));

    printf("\n%d\n", sizeof(fun));
    for(int i = 0; i < sizeof(fun); i++)
        printf("%02X ", fun[i]);
    return 0;
}

```

# Answer
> 8 votes
# CJam, ~~18~~ 14 bytes

Updated version with significant improvements contributed by Dennis:

```
0'jqf{-g_@=!*}

```

Try it online

Explanation:

```
0     Start value for running total.
'j    Push character between '^ and 'v for use in loop.
q     Get input.
f{    Apply block with argument to all input characters.
  -     Subtract character from 'j. This will give -12 for '^, 12 for 'v.
  g     Signum, to get 1 for '^, -1 for 'v, which is our increment value.
  _     Copy increment value.
  @     Bring running total to top.
  =     Compare. This will give 1 for the -1/-1 and 1/1 combinations where the new
        running total is 0. Otherwise, the new running total is the increment value.
  !     Negate to get 0 for the -1/-1 and 1/1 cases.
  *     Multiply result with increment value, to get new running total.
}     End block applied to input characters.

```

# Answer
> 7 votes
## Befunge 93 - 55 bytes

```
vj#p01:>#<:1+|
>~:10g-|v:g25<
^p01"j"<1^   <
./*34-g0<@

```

52 characters and 3 new lines.

Tested on this interpreter.

The `j` is equidistant from `^` and `v` in ascii so it's used to make arithmetic conversions in the end, rather than space consuming conditionals.

# Answer
> 7 votes
# brainfuck, 146 bytes

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

```

This program takes each byte of input and compares it against the last. If they're the same, it throws the input away and stores "0" as the "previous input", otherwise it saves it normally.

If the final result is `v`, it prints `-`. If the final result was non-zero, 1 is added to an empty cell. Finally, 48 is added to that cell and it is printed.

# Answer
> 7 votes
# Javascript ES6, ~~91~~ 48 chars

```
s=>~~{'^':1,v:-1}[s.replace(/(.)\1/g).slice(-1)]

```

Explanation: `undefined` ends by `d`.

Test:

```
` -> 0
^^ -> 0
^v -> -1
^ -> 1
v -> -1
v^ -> 1
vv -> 0
^^^ -> 1
vvv -> -1
^^^^ -> 0
vvvv -> 0
^^^^^ -> 1
vvvvv -> -1
^^^^^^ -> 0
vvvvvv -> 0
^^v -> -1
^v^ -> 1
^vv -> 0
vv^ -> 1
v^v -> -1
v^^ -> 0
^vvv^^vv^vv^v^ -> 1
^vvv^^vv^vv^v^^ -> 0
^vvv^^vv^vv^v^^^ -> 1
^vvv^^vv^vv^v^^v -> -1
^vvv^^vv^vv^v^^vv -> 0
^vvv^^vv^vv^v^^vvv -> -1
^vvvvvvvvvvvv -> 0
^^vvvvvvvvvvvv -> 0
^^^vvvvvvvvvvvv -> 0
vvv^^^^^^^^^^^^ -> 0
vv^^^^^^^^^^^^ -> 0
v^^^^^^^^^^^^ -> 0`
.split("\n").map(s => s.split(" -> "))
.every(([s,key]) => (s=>~~{'^':1,v:-1}[s.replace(/(.)\1/g).slice(-1)])(s)==key)

```

Answer history:

```
s=>({'':0,'^':1,v:-1}[s.replace(/^(.)\1(\1\1)*(?=.?$)|.*(.)(((?!\3).)\5)+/,"").substr(-1)])
s=>~~{'^':1,v:-1}[s.replace(/^(.)\1(\1\1)*(?=.?$)|.*(.)(((?!\3).)\5)+/,"").substr(-1)]
s=>~~{'^':1,v:-1}[s.replace(/^.*(.)(((?!\1).)\3)+|(.)\4(\4\4)*/,"").substr(-1)]
s=>~~{'^':1,v:-1}[s.replace(/^.*(.)(((?!\1).)\3)+|(.)\4(\4\4)*/,"").slice(-1)]
s=>~~{'^':1,v:-1}[s.replace(/.*(.)(((?!\1).)\3)+|(.)\4(\4\4)*/,"").slice(-1)]
s=>~~{'^':1,v:-1}[s.replace(/.*(.)(((?!\1).)\3)+|((.)\5)*/,"").slice(-1)]
s=>~~{'^':1,v:-1}[s.replace(/((.)\2)+/g,"!").slice(-1)]
s=>~~{'^':1,v:-1}[s.replace(/(.)\1/g,"!").slice(-1)]
s=>~~{'^':1,v:-1}[s.replace(/(.)\1/g,0).slice(-1)]
s=>~~{'^':1,v:-1}[s.replace(/(.)\1/g).slice(-1)]

```

# Answer
> 7 votes
## Python 2, 49

```
lambda s:reduce(lambda x,c:cmp(cmp('u',c),x),s,0)

```

Iterates through with the update function

```
lambda x,c:cmp(cmp('u',c),x)

```

that takes the current vote count `x` and the new character `c` and outputs the new vote count.

The idea is to use Python 2's `cmp` function, which compares its two args and gives `-1, 0, 1` for `<, ==, >` respectively. The inner one `cmp('u',c)` gives `-1` for `v` and `1` for `^`; any character between them suffices for `'u'`. The outer one then compares that to `x`, which gives `cmp(1,x)` for `^` and `cmp(-1,x)` for `v`, which have the right values.

Direct iteration was 3 chars longer (52), though would be one char short (48) if taking an `input()` with quotes was allowed.

```
x=0
for c in raw_input():x=cmp(cmp('u',c),x)
print x

```

The best recursive function I found was one char longer (50)

```
f=lambda s:len(s)and cmp(cmp('u',s[-1]),f(s[:-1]))

```

# Answer
> 5 votes
# Prolog, ~~159~~ 152 bytes

**Code:**

```
v(1,^,0).
v(1,v,-1).
v(0,^,1).
v(0,v,-1).
v(-1,^,1).
v(-1,v,0).
r(X,[H|T]):-T=[],v(X,H,Z),write(Z);v(X,H,Z),r(Z,T).
p(S):-atom_chars(S,L),r(0,L).

```

**Test it yourself:**
Online Interpreter here
**Example**

```
>p("^vvv^^vv^vv^v^^vvv").
-1

>p("^vvv^^vv^vv^v^")
1

```

**Edit:** Saved 7 bytes by unifying r-clauses with OR.

# Answer
> 4 votes
# CJam, 16 bytes

```
0re`W=(2%*c'a--g

```

This will crash after printing **0**, if applicable. The error can be suppressed with the Java interpreter. If you try this online, ignore everything but the last line of output.

### How it works

```
0                e# Push a 0 on the stack.
 r               e# Read a whitespace-separated token from STDIN.
  e`             e# Perform run-length encoding.
    W=           e# Select the last [repetitions character] pair.
                 e# This will fail for the empty string, so the
                 e# interpreter will print the stack's only element (0).
      (          e# Shift out the number of repetitions.
       2%        e# Compute its parity.
         *       e# Create a string, repeating the character 1 or 0 times.
          c      e# Cast to character.
                 e# This will fail for a zero-length string, so the
                 e# interpreter will print the stack's only element (0).
           'a-   e# Subtract the character 'a' from '^' or 'v'.
              -  e# Subtract the difference (integer) from 0.
               g e# Apply the sign function.

```

# Answer
> 4 votes
# JavaScript (ES6), ~~64~~ ~~59~~ ~~58~~ 52 bytes

```
f=v=>(t=/\^*$|v*$/.exec(v)[0]).length*(t<'v'?1:-1)%2

```

This is based on the observation that only the last stretch of the repetition (of either `^` or `v`) affects the result.

*Thanks to Neil for golfing off 6 bytes.*

# Answer
> 4 votes
# Haskell, 40 bytes

```
1%'^'=0
_%'^'=1
1%_=-1
_%_=0
v=foldl(%)0

```

# Answer
> 4 votes
# Python 2, 177 159 72 bytes

Still kinda new to this code golf thing.

```
def v(s):
 c=0
 for i in s:c=((0,1)[c<1],(0,-1)[c>-1])[i=="^"]
 return c

```

**EDIT:** Fixed the incorrect behavior.
**EDIT 2:** Thanks @MorganThrapp for shaving off lots of bytes.

# Answer
> 4 votes
# Scala, 75 bytes

```
def d(s:String)=s./:(0){case(1,94)|(-1,'v')=>0;case(_,94)=> 1;case _=> -1}

```

Test for implemented function.

```
  object Util {
        def d(s: String) = s./:(0) {
    case (1, '^') | (-1, 'v') => 0
    case (_, '^') => 1
    case (_, _) => -1
  }
      def main(s: Array[String]): Unit = {
        println("1 == " + d("^vvv^^vv^vv^v^^^"))
        println("1 == " + d("^vvv^^vv^vv^v^"))
        println("-1 == " + d("^vvv^^vv^vv^v^^vvv"))
        println("0 == " + d("^^^vvvvvvvvvvvv"))
        println("0 == " + d("vvv^^^^^^^^^^^^"))
      }
    }

```

# Answer
> 3 votes
# APL, 17

```
(⊣×≠)/⌽0,2-'^ '⍳⍞

```

For interpreters without fork notation (like GNU APL), it would be `{⍺×⍺≠⍵}/⌽0,2-'^ '⍳⍞` (19). This is probably the most boring of possible solutions because it works directly from the definition of the problem.

# Answer
> 3 votes
# Ruby, ~~41~~ 35 bytes

Regex. Only the last button pressed is interesting, so check the run-length of that. Then compare it to `"a"` (or any letter between `^` and `v`) to get `1` or `-1`.

```
->s{s[/(.?)\1*$/].size%2*(?a<=>$1)}

```

# Answer
> 3 votes
# C# 6, 18 + 80 = 98 bytes

Requires:

```
using System.Linq;

```

Actual function:

```
int S(string v)=>v.Split(new[]{"^^","vv"},0).Last().Length<1?0:v.Last()<95?1:-1;

```

How it works: the code first removes everything before the last `^^` or `vv`. That content is not relevant because clicking the same button twice will always cancel your vote. It does this by splitting on `^^` and `vv` and taking the last item. If this item is an empty string (`.Length<1`), then the function returns `0` because all voting has been cancelled. If the string it not empty, then it just looks at the last char of the original string: it will override all previous votes. If the char code is smaller than 95, then it will be 94, `^`, so it returns `1`, otherwise `-1`.

# Answer
> 3 votes
# Python 2.7, ~~79~~ ~~75~~ 88

```
s=input()
print (0,(1,-1)[s[-1]=='v'])[len(s[s.rfind(('v^','^v')[s[-1]=='v'])+1:])%2!=0]

```

# Answer
> 3 votes
# Go, 179 bytes

An ***extremely*** naive solution.

```
package main
import(."fmt"."strings")
func main(){a:=""
i:=0
Scanln(&a)
b:=Split(a,"")
for _,e:=range b{switch i{case 1:i--
case 0:if e=="^"{i++}else{i--}
case-1:i++}}
Println(i)}
```

Ungolfed:

```
package main

import (
    ."fmt"
    ."strings"
)

func main() {
    a := ""
    i := 0
    Scanln(&a)
    b := Split(a, "")
    for _, e := range b {
        switch i {
        case 1:
            i--
        case 0:
            if e == "^" {
                i++
            } else {
                i--
            }
        case -1:
            i++
        }
    }
    Println(i)
}
```

# Answer
> 3 votes
# 05AB1E, 8 bytes

```
γ¤®öÓÆ.±

```

Try it online!

Alternative solutions with the same length: `uγ¤®öÓÆ(`, `γ¤®ögÓÆ(`.

# Answer
> 2 votes
## Minkolang 0.11, ~~28~~ 22 bytes

```
0$I2&N."j"o-34*:dr=,*!

```

Try it here.

### Explanation

```
0                         Push a 0 (running total)
 $I                       Push length of input
   2&N.                   Output as integer and stop if this is 0
       "j"                Push 106
          o               Take character from input (94 for ^, 118 for v)
                          <<so ^ becomes +12 and v becomes -12>>
           -              Subtract
            34*:          Divide by 12
                d         Duplicate top of stack
                 r        Reverse stack
                  =,      Push 0 if equal, 1 otherwise
                    *     Multiply
                          <<this handles two of the same vote in a row>>
                     !    Unconditional trampoline (jumps the 0 at the beginning)

```

Note that there is no `N.` at the end. That's because I let it wrap around to the beginning. When the input is empty, the final tally is output as integer and the program stops.

# Answer
> 2 votes
# Pyth, 13 bytes

```
ut+Jq\^H>JGzZ

```

# Answer
> 2 votes
# Mathematica, 60 bytes

```
Mod[#,2]Sign@#&@Tr@Last@Split@StringCases[#,{"^"->1,_->-1}]&

```

# Answer
> 2 votes
# Shape Script, 26 bytes

```
"^"$"0>1@-"~"v"$"0<1-"~0@!

```

How it woks:

```
"^"$     split input on '^'
"
  0>         Check if the number is more than 0 (1 if true, 0 if false).
  1@-        subtract the answer from one.
"~       Join it back together, with this string in place of '^'
"v"$     Split on 'v'
"
  0<         Check if 0 is more than the number (1 if true, 0 if false).
  1-         subtract one from the results
"~       Join it back together, with this string in place of 'v'
0@       add a zero to the stack and place it under the string just built.
!        run the string as code

```

# Answer
> 2 votes
# Perl 5, 41 bytes

40 bytes, plus 1 for `-p`

```
/(.)\1*$/;$_=((length$&)%2)*($1=~v?-1:1)

```

`/(.)\1*$/;` compares the input string to the regex `/(.)\1*$/`, i.e. sees whether it ends with a single character repeated some number ≥1 of times.

If so, `$&` is the whole repetition string and `$1` is the character; otherwise (i.e. the input string is empty), those two variables are the empty string.

`$1=~v?-1:1` compares `$1` to the regex `v` and returns −1 if it matches and 1 otherwise.

And multiply that ±1 by `(length$&)%2`, the length of `$&` modulo 2.

# Answer
> 2 votes
# C# 6, 18 + 97 95 = 115 113 bytes, no string methods, excessive LINQ

```
int v(string s)=>(int)s.Reverse().TakeWhile((c,i)=>i<1||c==s[s.Length-i])?.Sum(x=>x<95?1:-1)%2;

```

Truly deserves to be preceded by

```
using System.Linq;

```

Got the idea of using `x<95?1:-1` instead of `x=='^'?1:-1` from ProgramFOX's answer

Coincidences:

* The tweak I stole makes use of comparing to 95 – the byte count excluding the using statement, using said tweak
* The sum of the digits of the total byte count equals the number of digits of the total byte count written as roman numeral

# Answer
> 2 votes
# C: ~~67~~ 66 Bytes

golfed:

```
void f(char *v){int i=0,c,s=0;for(;v[i]!=0;i++){v[i]>94?s--:s++;}}

```

ungolfed:

```
void f (char *v)
{
    int i = 0, c, s = 0;

    for (;v[i]!=0;i++)
    {
        v[i] > 94 ? s-- : s++;
    }
}

```

# Answer
> 2 votes
# 05AB1E, ~~14~~ ~~12~~ 11 bytes

```
Îvy'^QDŠ‹+<

```

Port of *@Sp3000*'s Gol\>\<\> answer.

NOTE: *@Grimy* already posted a shorter 8 bytes alternative for 05AB1E, so make sure to upvote him!

Try it online or verify all test cases.

**Explanation:**

```
Î            # Push 0 (later mentioned as `r`) and the input-string
 v           # Loop over the characters of the input:
  y'^Q      '#  Does the current character equal "^"?
             #  (results in 1 for truthy; 0 for falsey - later mentioned as `b`)
      D      #  Duplicate this result `b`
       Š     #  Triple swap (`r`,`b`,`b`) to (`b`,`r`,`b`)
        ‹    #  Check if the boolean `b` is smaller than the result-integer `r`
             #  (again results in 1 for truthy; 0 for falsey)
         +   #  Add them together
          <  #  Decrease this by 1
             # (Implicitly output the result-integer `r` after the loop)

```

# Answer
> 1 votes
# CJam, ~~27~~ 24 bytes

```
'^_]r+e`W=(2%\(i99-g@*W*

```

Try it Online.

All I took from Dennis' answer is `g` (sign function) .

# Answer
> 1 votes
# Ruby, 43

```
->s{a=0
s.bytes{|i|b=9-i/11;a=a!=b ?b:0}
a}

```

`9-i/11` evaluates to 1 or -1 when given the ascii codes of `^` (94) or `v` (118)

In test program:

```
f=->s{a=0
s.bytes{|i|b=9-i/11;a=a!=b ?b:0}
a}

g=gets.chomp
puts f[g]

```

# Answer
> 1 votes
## C (107 bytes)

```
#include<stdio.h>
int c,t;main(){while((c=getchar())-'\n')(c=='^')?++t:((c=='v')?--t:0);printf("%d\n",t);}

```

# Answer
> 1 votes
# C++, ~~90~~ 87 bytes

```
int f(char* c){int r=1,T[2][3]={{2,2,1},{1,0,0}};while(*c)r=T[*c++==94][r];return r-1;}

```

Ungolfed:

```
int f( char* c )
{
     // Lookup table created from Golfing description. Need to shift values up by 1
     // because will be using them to index table later
     int lookup_table[ 2 ][ 3 ] = {{2, 2, 1}, {1, 0, 0}};
     int result = 1;                 // empty string result: 1
     while ( *c )                    // check if end of string
     {
          int  row    = *c - '^' ? 1 : 0; // if char is '^' search in second row else in first
          auto column = result;           // column to look for is current result
          result      = lookup_table[ row ][ column ];
          c++;
      }
      return result - 1;                  // make expected result
 }

```

hehe finally got to write c++ in C++ ;-)

Edit:

1. Exchanged tenary row calculation to simple boolean expression.

# Answer
> 1 votes
# Braingolf, 17 bytes

```
VR{.#veM|}lvlMR-s

```

Try it online!

Thought I could get it shorter by subtracting 9 from the charcodes of each character, then using `J` to change vowels to 1 and non-vowels to 0, but it turned out to be the same length

# Answer
> 1 votes
# Turing Machine Code, 115 bytes

```
init:r
accept:e
r,^
^,_,>
r,v
v,_,>
r,_
e,0,-
^,^
r,_,>
^,v
r,v,-
^,_
e,1,-
v,^
r,^,-
v,v
r,_,>
v,_
w,-,>
w,_
e,1,-

```

Try it here

Ungolfed:

```
//-------CONFIGURATION
init: startread
accept: end

//startread
startread,^
read^,_,>

startread,v
readv,_,>

startread,_
end,0,-

//read^
read^,^
startread,_,>

read^,v
startread,v,-

read^,_
end,1,-

//readv
readv,^
startread,^,-

readv,v
startread,_,>

readv,_
write-,-,>

write-,_
end,1,-

```

The approach I used was to compare every two adjacent characters and either remove them if they canceled, or to remove just the first if the second one were to overwrite the first. An extra state is needed so that `-1` can be written, because this simulator does not support multi-symbol cells.

# Answer
> 0 votes
# Japt, 17 bytes

```
¬®c nL gÃrÈ-Y©Y}0

```

Try it online!

### Unpacked & How it works

```
Uq mZ{Zc nL g} rXY{X-Y&&Y}0

Uq     Convert the input string into list of chars
mZ{    Map...
Zc       Get charcode
nL       100 - charcode
g        sign(100 - charcode)
}
rXY{   Reduce...
X-Y&&Y   If X == Y, return 0; Otherwise, return Y
}0     ... default being 0

```

Having an array of `-1`s and `1`s at hand yields a nice reducing function.

# Answer
> 0 votes
## PHP 5, 47 bytes

Run on the command line, using `php -nR 'code here'`. The option `-R` counts as one byte.

```
echo(strrpos($s=x.$argn,"^")-strrpos($s,v))%2;

```

# Answer
> 0 votes
# Julia 0.6, 38 bytes

```
s->foldl((x,c)->cmp(cmp('u',c),x),0,s)

```

Try it online!

Julia version of xnor's answer. (Uses `foldl` instead of `reduce` to save a byte.)

# Answer
> 0 votes
# Jelly, 9 bytes

```
ŒgṪO³_^/Ṡ

```

Try it online!

Assumes the program this function is in doesn't take command-line arguments.

For a 10-byte version that doesn't assume so:

```
ŒgṪOȷ2_^/Ṡ

```

Try it online!

# Answer
> 0 votes
# Perl 5 `-pF`, 32 bytes

```
$\=int(/v/?-($\>=0):$\<1)for@F}{

```

Try it online!

---
Tags: code-golf, arithmetic
---


title: Magical Modulo Squares

text:
# Question
Title: Magical Modulo Squares
I'm a big fan of number theory. A big thing in number theory is modular arithmetic; the definition being \\$a\equiv b\mod m\\$ if and only if \\$m\mid a-b\\$. A fun thing to do is raising to powers: especially when the modulus is a prime number. In particular, it has been proven that if \\$a\\$ and \\$m\\$ are relatively prime (share no common factors besides \\$1\\$) then there exists a number \\$e\\$ such that \\$a^e\equiv 1\mod m\\$.

I will explain what the exercise is by an example. Let's take a modulus \\$m=7\\$. A possible output of the program or function would be:

```
3 2 6 4 5 1
2 4 1 2 4 1
6 1 6 1 6 1
4 2 1 4 2 1
5 4 6 2 3 1
1 1 1 1 1 1

```

Each row is a list of the powers of the first number in that row: the first row is \\$3, 3^2, 3^3, \cdots, 3^6\\$, which is equivalent to \\$3,2,6,4,5,1\\$ modulo \\$7\\$. The second row of the square above is the powers of \\$2\\$, etcetera, up to the last row, which are just powers of \\$1\\$.

This is a magical modulo square because:

* The square is symmetric; that is, the \\$i\\$th column is the same as the \\$i\\$th row.
* All values \\$1\\$ to \\$m-1\\$ appear at least once.

Below is the only other valid output for \\$m=7\\$, starting with powers of \\$5\\$:

```
5 4 6 2 3 1
4 2 1 4 2 1
6 1 6 1 6 1
2 4 1 2 4 1
3 2 6 4 5 1
1 1 1 1 1 1

```

## The challenge

Create a function or program that given a prime `p` outputs a magical modulo square, that is, a square with side lengths `p-1`, such that each row is a list of the consecutive powers of the first element in the row, and the same for the columns. All numbers between `0` and `p` must occur, and the square can only contain numbers in that range.

Input is a number or a string, and output can be ascii, a matrix, an array of arrays (any reasonable format).

This is code-golf, so the shortest code wins.

# Answer
> 4 votes
# Jelly, ~~13~~ 10 bytes

-3 thanks to Nick Kennedy

~~Feels like~~ the repeated code ~~should be~~ is golf-able, but I ~~have~~ did not manage~~d~~ it...

```
*€Ṗ%µQƑƇḢị

```

**Try it online!** (footer pretty-formats as a grid)

### How?

```
*€Ṗ%µQƑƇḢị - Link: integer, p
 €         - for each n in [1..p]
*          -   exponentiate with:
  Ṗ        -     pop = [1..p-1]
           - ...i.e [[1^1,1^2,...,1^(p-1)],[2^1,2^2,...,2^(p-1)],...,[....,p^(p-1)]]
   %       - modulo p
    µ      - start a new monadic chain (call that list of lists X)
       Ƈ   - keep those which:
      Ƒ    -   are invariant under:
     Q     -     de-duplicate
        Ḣ  - head
         ị - index into the list of lists X

```

# Answer
> 3 votes
# Charcoal, 36 bytes

```
≔Ｅ…¹θ﹪Ｘι…¹θＩθηＥ⊟Φη⁼¹№ι¹⪫Ｅ§η⊖ι◧ＩλＬ⊖θ

```

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

```
≔Ｅ…¹θ﹪Ｘι…¹θＩθη

```

Create a `p-1` by `p-1` array of powers of `1..p-1` to indices `1..p-1` (modulo `p`).

```
Ｅ⊟Φη⁼¹№ι¹

```

Map over one of the rows which has exactly one `1`.

```
⪫Ｅ§η⊖ι◧ＩλＬ⊖θ

```

Rearrange the rows into the order given by the selected row and format the output.

# Answer
> 2 votes
# Wolfram Language (Mathematica), ~~46~~ 43 bytes

```
Mod[PrimitiveRoot@#^Array[1##&,{#,#}-1],#]&

```

Try it online!

-3 thanks to alephalpha

# Answer
> 2 votes
# , ~~35~~ ~~32~~ 31 bytes

```
[:(/:0/:@{]\:#@~."1)]|^/~@}.@i.

```

Try it online!

# Answer
> 2 votes
# Zsh, ~~117~~ 90 bytes

```
b=$1
c=(eval set -- '$[x**'{1..$[b-1]}%b\])
for ((;${#${(u)@}}-b+1;++x))$c
for x;$c&&<<<$@

```

~~Try it online!~~ Try it online!

May God have mercy on my soul. There's a lot of bad practice all wrapped up here, let me explain the biggest offender at least:

```
c=(eval set -- '$[x**'{1..$[b-1]}%b\])
                      {1..$[b-1]}        # brace expansion, expands immediately
               '$[x**'           %b\]    # string literals, expand during eval
   eval set --                           # sets the positional parameters
c=(                                   )  # defines c to the words contained

```

Example for `b=4`:

```
c=(eval set -- '$[x**'{1..$[b-1]}%b\])
c=(eval set -- '$[x**'{1..3}%b\]     )                # $[b-1] => 3
c=(eval set -- '$[x**1%b]' '$[x**2%b]' '$[x**3%b]' )  # brace expansion

```

Finally, where `$c` appears in the rest of the program, the array elements are evaluated as `eval set -- ....`.

Lastly, `${#${(u)@}}` counts the unique elements int the positional parameters (i.e.: is there a cycle / are there `1`s?)

Comments relevant to the 117 byte answer below.

---

Challenges we have to overcome:

* No multidimensional or nested arrays. Instead we print out the strings as we get them in a loop.
* Options for testing if a given row has multiple 1s:
    + `${#${(M)a:#1}`: `:#` removes matching, and `(M)` reverses the match. So, this will expand to the number (`${# }`) of `1`s in the array. Unfortunately this expansion doesn't play nicely with the arithmetic for loop we use here. If it did, it could potentially save a byte.
    + `${${:-1}:*a}`: This is the set intersection between the singleton `1` and the set `a`. This will expand to the single `1` if it is found in the array. Using this option, we save one character here, but lose 1 overall having to put off adding the `1`s in the last row and column until the end.

```
f(){ # f [element] [modular base], puts powers up to n-2 into array $a
    a=()
    for i ({1..$[$2-2]})
        a+=($[$1**i%$2])
}
a=(1)                     # put 1 in a to force first loop iteration
for ((;${${:-1}:*a};))    # test for 1 in array $a
    f $[++x] $1           # increment x, iterate through all elements mod $1
for y ($a 1){             # for all elements in the [last array, 1]
    f $y $1               # put that row in $a
    <<<$a\ 1              # print out $a with 1 appended (space-delimited string)
}

```

# Answer
> 1 votes
# Perl 6, ~~65~~ 57 bytes

```
{.[|.first(*.Set+2>$_)]}o{.&{@=(($++X**1..^$_)X%$_)xx$_}}

```

Try it online!

There's probably some way to just output the square itself, but this does the same process outlined in the question, sorting the lists by their positions in the first list that is just a permutation of 1 to input-1. Returns as a list of lists.

BTW, there's a lot of jockeying around, trying to get around some of Perl 6's annoying limitations involving sequences vs arrays, and anonymous variables.

### Explanation:

```
                               $++               xx$_    # Map 0 to i-1 to
                              (   X**1..^$_)             # n, n^2, n^3... n^(i-1)
                             (              X%$_)        # All modulo i
{                      }o{.&{                        }}  # Pass to the next function
 .[                   ]    # Index into that list of lists
   |.first(          )     # The list of the first list that
           *.Set+2>$_        # Has all the elements in the range 1 to i-1

```

# Answer
> 1 votes
# JavaScript (ES7),  ~~91~~  86 bytes

This version attempts to compute the powers before applying the modulo and will fail for \\$p\ge11\\$ because of loss of precision. It is otherwise using the same logic as the commented version below.

```
f=(p,k)=>(g=k=>[...Array(i=p-1)].map(_=>k**++i%p))(k).sort()[1]>1?g(k).map(g):f(p,-~k)

```

Try it online!

---

# JavaScript (ES6),  ~~92~~  87 bytes

This version uses modular exponentiation to support (much) higher input values.

```
f=(p,k)=>(g=k=>[...Array(p-1)].map(_=>n=n*k%p,n=1))(k).sort()[1]>1?g(k).map(g):f(p,-~k)

```

Try it online!

## How?

### Finding the first row

Given \\$1\le k\<p\\$, we use the helper function \\$g\\$ to compute \\$a\_k(n)=k^n\bmod p\\$ for \\$1\le n\<p\\$.

```
g = k =>              // k = input
  [...Array(p - 1)]   // generate an array of size p - 1
  .map(_ =>           // for each entry in there:
    n = n * k % p,    //   update n to (n * k) mod p
    n = 1             //   starting with n = 1
  )                   // end of map()

```

We look for \\$k\\$ such that there's only one value \\$n\\$ such that \\$a\_k(n)=1\\$. We do that by sorting the array and testing if the 2nd element is greater than \\$1\\$.

```
g(k).sort()[1] > 1

```

This works even in lexicographical order -- which is the default behavior of `sort()` -- because:

* if there are several \\$1\\$'s, they will all be moved to the front just like they would in numeric order
* if there's only a single \\$1\\$, the 2nd value will be greater than \\$1\\$, no matter if it's really the 2nd value in numeric order or not

*Example:*

For \\$p=17\\$:

* for \\$k=1\\$, we get:
    + \\$a\_1=\[ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 \]\\$
    + sorted as \\$\[ 1, \color{red}1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 \]\\$
* for \\$k=2\\$, we get:
    + \\$a\_2=\[ 2, 4, 8, 16, 15, 13, 9, 1, 2, 4, 8, 16, 15, 13, 9, 1 \]\\$
    + sorted as \\$\[ 1, \color{red}1, 13, 13, 15, 15, 16, 16, 2, 2, 4, 4, 8, 8, 9, 9 \]\\$
* for \\$k=3\\$, we get:
    + \\$a\_3=\[ 3, 9, 10, 13, 5, 15, 11, 16, 14, 8, 7, 4, 12, 2, 6, 1 \]\\$
    + sorted as \\$\[ 1, \color{red}{10}, 11, 12, 13, 14, 15, 16, 2, 3, 4, 5, 6, 7, 8, 9 \]\\$

### Building the matrix

Once we've found \\$k\\$, we invoke \\$g(k)\\$ again (to retrieve the unsorted version of the array) and invoke \\$g\\$ on each element of \\$g(k)\\$ to build the rows of the matrix.

This part can be simply written as:

```
g(k).map(g)

```

# Answer
> 1 votes
# 05AB1E, ~~19~~ 16 bytes

```
LεI<LmI%}ÐΘOÏн<è

```

-3 bytes thanks to *@Emigna*.

Try it online (the footer is to pretty-print the 2D list).

**Explanation:**

```
L          # Create a list in the range [1, (implicit) input]
 ε         # Map each number `y` in the list to:
  I<L      #  Create a list in the range [1, input-1]
     m     #  Get number `y` to the power of each number in this list
      I%   #  Take modulo-input on each number
 }Ð        # After the map: triplicate this modified matrix
   ΘO      # Get the amount of 1s in each row
     Ï     # And only leave the rows with exactly one 1
      н    # Then only leave the first row which contains a single 1
       <   # Decrease each value by 1 to make it 0-indexed
        è  # And index each into the rows of the modified matrix to create a new matrix
           # (which is output implicitly as result)

```

# Answer
> 1 votes
# Python 2, 108 bytes

```
def f(p):R=range(1,p);return[m for m in[[[j**(k*i)%p for i in R]for k in R]for j in R]if sorted(m[0])==R][0]

```

Try it online!

# Answer
> 0 votes
# Wolfram Language (Mathematica), 67 bytes

```
(s=Thread@Mod[x^#&/@(x=Range[#-1]),#])[[#&@@Select[s,Sort@#==x&]]]&

```

Try it online!

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

```
n->lift(matrix(n-1,,i,j,znprimroot(n)^(i*j)))

```

Try it online!

# Answer
> 0 votes
# APL(NARS), 29 chars, 58 bytes

```
{k←⍵∣⍺*⍳⍵-1⋄⊃{m∣k*⍵}¨⍳¯1+m←⍵}

```

test:

```
  f←{k←⍵∣⍺*⍳⍵-1⋄⊃{m∣k*⍵}¨⍳¯1+m←⍵}
  3 f 7
3 2 6 4 5 1
2 4 1 2 4 1
6 1 6 1 6 1
4 2 1 4 2 1
5 4 6 2 3 1
1 1 1 1 1 1
  5 f 7
5 4 6 2 3 1
4 2 1 4 2 1
6 1 6 1 6 1
2 4 1 2 4 1
3 2 6 4 5 1
1 1 1 1 1 1

```

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


# Question
Title: Cayley Table of the Dihedral Group \$D_3\$
The Dihedral group \\$D\_3\\$ represents the symmetries of an equilateral triangle, using the identity (represented by `id`), rotations (represented by `r1` and `r2`), and reflections (represented by `s0`, `s1`, and `s2`).

Your task is to compute the composition \\$yx\\$ of the elements \\$x, y \in D\_3 \\$. They are given by the Cayley table below:

```
  x  id  r1  r2  s0  s1  s2
y  +-----------------------
id | id  r1  r2  s0  s1  s2
r1 | r1  r2  id  s1  s2  s0
r2 | r2  id  r1  s2  s0  s1
s0 | s0  s2  s1  id  r2  r1
s1 | s1  s0  s2  r1  id  r2
s2 | s2  s1  s0  r2  r1  id

```

### Input

Any reasonable input of `x` and `y`. Order does not matter.

### Output

`y` composed with `x`, or looking up values in the table based on `x` and `y`.

### Test Cases

These are given in the form `x y -> yx`.

```
id id -> id
s1 s2 -> r1
r1 r1 -> r2
r2 r1 -> id
s0 id -> s0
id s0 -> s0

```

### Notes on I/O

You may use any reasonable replacement of `id, r1, r2, s0, s1, s2`, for example `1, 2, 3, 4, 5, 6`, `0, 1, 2, 3, 4, 5`, or even `[0,0], [0,1], [0,2], [1,0], [1,1], [1,2]` (here the first number represents rotation/reflection and the second is the index).

# Answer
> 8 votes
# Python 2, 27 bytes

```
lambda o,O:[o[_]for _ in O]

```

Try it online!

# Answer
> 3 votes
# JavaScript (ES6), 39 bytes

Uses the following mapping:

```
 id | r1 | r2 | s0 | s1 | s2
----+----+----+----+----+----
 2  | 0  | 4  | 1  | 3  | 5

```

Takes input as `(x)(y)`.

```
x=>y=>'450123234523012323'[(x*51^y)%18]

```

Try it online!

---

# JavaScript (ES6), 20 bytes

Using Jonathan Frech's I/O format:

```
x=>y=>y.map(n=>x[n])

```

Try it online!

# Answer
> 3 votes
# Jelly, 1 byte

A dyadic link taking y on the left and x on the right.

Uses the representations of the fist three natural numbers transformed as their actions describe:

```
   name:  id          r1          r2          s0          s1          s2
  value:  [1,2,3]     [2,3,1]     [3,1,2]     [2,1,3]     [1,3,2]     [3,2,1]
(action:  identity    rot-Left    rot-Right   swap-Left   swap-Right  swap-Outer)

```

A port of Jonathan Frech's Python answer

is Jelly's "index into" atom, and it vectorises; note that Jelly is 1-indexed.

**Try it online!** Or see a table using the question-names.

---

To take x on the left and y on the right, these values may be used instead:

```
id       r1       r2       s0       s1       s2
[1,2,3]  [3,1,2]  [2,3,1]  [1,3,2]  [3,2,1]  [2,1,3]

```

...see here.

# Answer
> 3 votes
# Python 2, ~~27~~ ~~26~~ 23 bytes

```
lambda x,y:(y+x*5**y)%6

```

Try it online! Edit: Saved 3 bytes thanks to @NieDzejkob. Uses the following mapping:

```
 id | r1 | r2 | s0 | s1 | s2
----+----+----+----+----+----
 0  | 2  | 4  | 1  | 3  | 5

```

# Answer
> 2 votes
# APL (Dyalog Classic), 3 bytes

```
+.×

```

Try it online!

`+.×` is matrix multiplication

we represent the group as

```
id     r1     r2     s0     s1     s2
1 0 0  0 0 1  0 1 0  0 0 1  0 1 0  1 0 0
0 1 0  1 0 0  0 0 1  0 1 0  1 0 0  0 0 1
0 0 1  0 1 0  1 0 0  1 0 0  0 0 1  0 1 0

```

# Answer
> 2 votes
# K (ngn/k), 1 byte

```
@

```

Try it online!

`x@y` is list indexing, which is the same as composition of permutations; we represent the group as

```
id:0 1 2; r1:1 2 0; r2:2 0 1; s0:2 1 0; s1:1 0 2; s2:0 2 1

```

# Answer
> 1 votes
# Japt, 2 bytes

Uses Jonathan's I/O format.

```
gV

```

Try it online

# Answer
> 1 votes
# JavaScript (Node.js), ~~24~~ 19 bytes

```
(x,y)=>(y+x*5**y)%6

```

Try it online! Edit: Saved 2 bytes by switching to `**` and 3 bytes thanks to @NieDzejkob. Uses the following mapping:

```
 id | r1 | r2 | s0 | s1 | s2
----+----+----+----+----+----
 0  | 2  | 4  | 1  | 3  | 5

```

The old 24 byte version also works in old versions of JavaScript:

```
(x,y)=>(y%2?y+6-x:y+x)%6

```

# Answer
> 1 votes
# Racket, 42 bytes

```
(lambda(x y)(modulo(+ y(* x(expt 5 y)))6))

```

Try it online!

A boring port of Neil's Python answer. Uses the same I/O format, so:

```
 id | r1 | r2 | s0 | s1 | s2
----+----+----+----+----+----
 0  | 2  | 4  | 1  | 3  | 5

```

# Answer
> 1 votes
# Wolfram Language (Mathematica), 16 bytes

```
Mod[#+#2*5^#,6]&

```

Try it online!

Another boring port of Neil's answer, this time in Mathematica. It is an anonymous function that takes arguments in the order `[y, x]`.

Here’s the input representation:

```
 id | r1 | r2 | s0 | s1 | s2
----+----+----+----+----+----
 0  | 2  | 4  | 1  | 3  | 5

```

# Answer
> 0 votes
# 05AB1E, 1 byte

```
è

```

Port of *@JonathanAllan*'s Jelly answer, but with 0-based indices, so the representations are:

```
id       r1       r2       s0       s1       s2       # Original values
[0,1,2]  [1,2,0]  [2,0,1]  [1,0,2]  [0,2,1]  [2,1,0]  # Values instead

```

Try it online or verify all possible combinations or verify all mapped back to ids.

**Explanation:**

```
è  # Index the second (implicit) input-list vectorized into the first (implicit) input-list
   # And output the result implicitly

```

---
Tags: code-golf, math
---


title: Is it a Munchausen Number?

text:
# Question
Title: Is it a Munchausen Number?
A *Munchausen Number* in base \\$b\\$, also known as a Perfect digit-to-digit invariant or PDDI is a peculiar type of positive integer where the sum of its base-\\$b\\$ digits raised to themselves is equal to the number itself. They are named for the fictional Baron Munchausen, who apparently hoisted himself up via his own ponytail to save himself from drowning. A related concept is Narcissistic numbers.

For instance, \\$1\\$ is trivially a Munchausen number in every base because \\$1^1=1\\$. Additionally, every positive integer is a base-1 Munchausen number by definition.

More interestingly, \\$3435\\$ is a base-10 Munchausen number because \\$3^3+4^4+3^3+5^5=3435\\$, and in fact is the only other base-10 Munchausen number.

A partial list of Munchausen numbers in every base up to 35 can be found on the OEIS as sequence A166623.

Given a positive integer \\$n\>0\\$, determine if it is a Munchausen number in any base \\$b\geq2\\$.

## Rules

* Default I/O rules apply, so:
    + Full program or functions are acceptable.
    + Input can be from STDIN, as a function argument, and output can be to STDOUT, as a function return value, etc.
* Default loopholes apply.
* The output must be one of two distinct, consistent results. So `TRUE` is fine for truthy and `FALSE` is fine for falsy, but you can reverse that or return `None` for truthy and `1` for falsy or whatever. Please specify the selected results in your answer.
* Your answer has to work at least theoretically for any positive integer.
* Munchausen numbers use the convention \\$0^0=1\\$, so \\$2\\$ is a base-2 Munchausen number as \\$1^1+0^0=2\\$. Your code must follow this convention.
* Explanations are strongly encouraged, even though submissions will most likely use the brute-force search method.
* Using esoteric languages earns you brownie points since Munchausen was apparently a strange person.

## Test Cases

```
Truthy
1 (all bases)
2 (base 2)
5 (base 3)
28 (base 9 and base 25)
29 (base 4)
55 (base 4)
3435 (base 10)
923362 (base 9)
260 (base 128)
257 (base 64 and base 253)

Falsy
3
4
591912
3163
17
```

This is , so the shortest answer in each language (in bytes) wins!

# Answer
> 13 votes
# 05AB1E, 7 bytes

```
LвDmOQZ

```

Try it online!

The larger test cases will time out on TIO.

**Explanation**

```
L         # push range [1 ... input]
 в        # convert input to a digit list in each of these bases
  Dm      # raise each digit to the power of itself
    O     # sum each
     Q    # check each for equality with input
      Z   # max

```

# Answer
> 5 votes
# Jelly, 8 bytes

```
bŻ*`§ċ⁸Ị

```

Yields `0` for Munchausen and `1` otherwise.

**Try it online!**
Or see the first five hundred positive integers split up as `[[Munchausen], [non-Munchausen]]`.

### How?

```
bŻ*`§ċ⁸Ị - Link: integer, n
 Ż       - zero-range -> [0,1,2,3,4,...,n]
b        - (n) to base (vectorises)
   `     - with left as both arguments:
  *      -   exponentiation (vectorises)
    §    - sums
     ċ   - count occurrences of:
      ⁸  -   n
       Ị - is insignificant (abs(x) <= 1)

```

---

Alternative for `1` for Munchausen and `0` otherwise:

```
bŻ*`§ċ>1

```

# Answer
> 5 votes
# , ~~33~~ ~~28~~ 27 bytes

```
e.1#.i.@>:^~@(#.inv ::1)"0]

```

Try it online!

* `e.` is the input an element of...
* `1#.` the sum of each row of...
* `i.@>: ... ]` 0..input and the input itself, passed as left and right args to...
* `^~@(#.inv)"0` convert the right arg (input) to each base in the left arg and raise each result elementwise to itself `^~@`.
* `::1` finally this is needed because you can't convert uniquely to base 1, so it errors. in this case, we simply return 1, which won't match for any number *except* 1, which is what we want

# Answer
> 4 votes
# , ~~72~~ 69 bytes

-1 byte thanks to digEmAll

```
function(x){for(b in 1+1:x)F=F|!sum((a=x%/%b^(0:log(x,b))%%b)^a)-x;F}

```

Try it online!

Outputs `TRUE` for Munchausen numbers and `FALSE` otherwise.

`x%/%b^(0:log(x,b))%%b)` converts `x` to base `b`, and the for loop does the rest of the work (reassigning `F`, which is `FALSE` by default).

We need to allow the base `b` to go all the way to `x+1` instead of `x` to handle the case `x=1`.

# Answer
> 3 votes
# JavaScript (ES7), 60 bytes

Returns a Boolean value.

```
n=>(F=b=>(g=n=>n&&g(n/b|0)+(n%=b)**n)(n)==n||b<n&&F(b+1))(2)

```

Try it online!

### Commented

```
n =>                   // n = input
  ( F = b =>           // F = recursive function taking a base b
    ( g = n =>         //   g = recursive function taking an integer n
      n &&             //     if n is not equal to 0:
        g(n / b | 0) + //       do a recursive call with floor(n / b)
        (n %= b) ** n  //       and add (n mod b) ** (n mod b)
    )(n)               //   initial call to g with the original value of n
    == n ||            //   return true if the result is equal to n
    b < n &&           //   otherwise, if b is less than n:
      F(b + 1)         //     try with b + 1
  )(2)                 // initial call to F with b = 2

```

# Answer
> 3 votes
# Japt, 13 bytes

```
õ@ìXÄ x_pZ
øN

```

Saved one byte thanks to @Shaggy

Try it

# Answer
> 3 votes
# Perl 6, 51 bytes

```
{?grep {$_==sum [Z**] .polymod($^a xx*)xx 2},^$_+2}

```

Try it online!

### Explanation:

```
{                                                 } # Anonymous code block
 ?grep {                                  }         # Do any
                                           ,^$_+2   # Of the bases from 2 to n+1
            sum                              # Have the sum of
                      .polymod($^a xx*)      # The digits of n in that base
                [Z**]                  xx 2  # Raised to the power of themselves
        $_==                                 # Equal to the original number?

```

# Answer
> 3 votes
# Ruby, 50 bytes

TIO timed out on 591912. Somehow edges out Perl by 1 byte... (at time of writing)

```
->n{(2..n+1).any?{|b|n.digits(b).sum{|d|d**d}==n}}

```

Try it online!

# Answer
> 3 votes
# APL (dzaima/APL), ~~23~~ 13 bytes

```
⊢∊⊂+.*⍨⍤⊤⍨¨2…

```

Try it online!

Thanks to Adám, ngn and dzaima, we managed to shave 10 bytes off this answer by using dzaima/APL.

Prefix tacit function. Munchausen numbers return 1, else 0.

### How

```
⊢∊⊂+.*⍨⍤⊤⍨¨2… ⍝ Prefix tacit function, argument will be called ⍵

             2… ⍝ Generate the integer sequence [2..⍵]
          ⊤⍨¨  ⍝ Convert ⍵ to each base in the vector
     +.*⍨⍤      ⍝ Raise each digit of each element in the vector to itself, then sum
⊢∊⊂            ⍝ Check if ⍵ is in the resulting vector.

```

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

```
#<2||!Tr[Check[#^#,1]&/@#~IntegerDigits~i]~Table~{i,2,#}~FreeQ~#&

```

Try it online!

*-4 bytes from @attinat*

# Answer
> 2 votes
# C (gcc) `-lm`, ~~79~~ 75 bytes

```
f(n,b,i,g,c){for(g=b=1;b+++~n;g*=!!c)for(c=i=n;c-=pow(i%b,i%b),i/=b;);n=g;}

```

Try it online!

Returns `0` for Munchausen numbers, and `1` otherwise.

---

### also 75 bytes

```
a,b;f(n){for(a=b=1;b+++~n;a*=g(n)!=n);n=a;}g(n){n=n?g(n/b)+pow(n%b,n%b):0;}

```

Try it online!

# Answer
> 2 votes
# Charcoal, 17 bytes

```
Ｎθ¬Φθ⁼θΣＥ↨θ⁺²ιＸλλ

```

Try it online! Link is to verbose version of code. My 16-byte attempt didn't work but that might be a bug in Charcoal, so watch this space. Outputs `-` unless the number is a Munchausen number. Explanation:

```
Ｎθ                  Input `n` as a number
   Φθ               Try bases `2` .. `n+1`
       Σ            Sum of
         ↨θ         `n` converted to base
           ⁺²ι      Next trial base
        Ｅ           Each digit
              Ｘλλ   Raised to its own power
     ⁼              Equals
      θ             `n`
  ¬                 Logical Not

```

# Answer
> 2 votes
# C# (Visual C# Interactive Compiler), 99 bytes

```
n=>Enumerable.Range(2,n).Any(x=>{int g=0,t=n;for(;t>0;t/=x)g+=(int)Math.Pow(t%x,t%x);return g==n;})

```

Try it online!

# Answer
> 2 votes
## Haskell, 61 bytes

```
_#0=0
b#n|m<-mod n b=m^m+b#div n b
f n=elem n$1:map(#n)[2..n]

```

Returns `True` for Munchausen and `False` otherwise.

Try it online!

# Answer
> 2 votes
# Python 2, ~~83~~ 81 bytes

```
def f(n,b=2):
 s=0;m=n
 while m:k=m%b;s+=k**k;m/=b
 return s==n or b<n>0<f(n,b+1)

```

Try it online!

Returns `1` for truthy and `0` for falsey. Because of the recursion, can't practically deal with `591912`, but it works in the abstract.

# Answer
> 1 votes
# Perl 6, ~~66~~ 65 bytes

```
{$^a==1||[+] map {$a==[+] map {$_**$_},$a.polymod($_ xx*)},2..$a}

```

Try it online!

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

```
f=n=>{for(b=2;n-b++;){for(c=0,r=n;r;r=(r-a)/b)c+=(a=(r%b))**a;if(n==c)return 1}return 0}

```

# Answer
> 1 votes
# Icon, 109 bytes

```
procedure m(n)
every k:=2to n&{i:=n;s:=0
while{a:=i%k;a<:=1;s+:=a^a;0<(i/:=k)}
n=s&return 1}
return n=1|0
end

```

Try it online!

Times out for `591912`. Icon treats `0^0` as an overflow and that's why I need an additional check for zero.

# Answer
> 1 votes
# Stax, 15 bytes

```
╡!←!║╝âñoêû►╦ä▓

```

Run and debug it

Takes very long for the larger test cases.

Explanation:

```
{^xs|E{c|*m|+x=m|a Full program, unpacked
                   Implicitly input x
{              m   Map over bases [1 .. x]
 ^                   Increment base (effectively mapping over [2 .. x+1])
  xs                 Tuck x below base
    |E               Get digits of x in base
      {   m          Map over digits:
       c|*             copy and power
           |+        Sum
             x=      sum = x?
                |a Check if any element in array is true
                   Implicit output

```

---
Tags: code-golf, number, decision-problem
---


title: Palindromic Prime Factors

text:
# Question
Title: Palindromic Prime Factors
Palindromic prime problems are pretty common, but that's not what this question is about. In this challenge, the number doesn't have to be a palindrome, its prime factors do.

# Task

Your code has to take a single positive integer as input. Then check if any of the permutations of the prime factors of that integer are palindromic when concatenated. If so, output one of them (the list of factors, not the concatenated string). Else, you have to output `-1`.

This is , so shortest code in **bytes** wins!

# Test Cases

```
11 -> [11]
4 -> [2, 2]
39 -> [3, 13]
6 -> -1
1207 -> [17, 71]
393 -> -1
2352 -> [2, 2, 7, 3, 7, 2, 2]

```

# Answer
> 4 votes
# 05AB1E, 7 bytes

```
Òœ.ΔJÂQ

```

Try it online!

Explanation:

```
Ò            # prime factorization of the input
 œ           # permutations
  .Δ         # find the first one such that
    J        # concatenated
     ÂQ      # is a palindrome

```

( conveniently defaults to -1, so no extra work needed)

# Answer
> 3 votes
# Pyth, 14 bytes

*-2 bytes by @FryAmTheEggman*

```
h+f_IjkT.pPQ_1

```

Explanation:

```
h                 first element of
 +                (append a -1 to the end in case the filter is empty)
  f                 filter by lambda T:
   _I                 is invariant under reversing
     jkT              stringified list
   .p                over permutations of
     P Q             prime factors of Q with duplicates
  _1              -1

```

Thanks @FryAmTheEggman for reminding me about `I`. I don't think I've used it before.

Test suite

# Answer
> 3 votes
# CJam - 17 bytes

*Thanks to Martin Büttner for saving me **10** bytes!*

```
Wqimfe!{s_W%=}=p;

```

My first time writing in CJam! Explanation:

```
W              # Push a -1 onto the stack
q               # Get input
i               # Convert to integer
mf              # Find prime factorization
e!              # Find all permutations
{...}=          # Find permutation which...
s               # Convert to string
_               # Copy string
W%              # Get inverse
=               # Check if inverse == original
p;              # Print top of stack and discard the rest

```

# Answer
> 2 votes
## Ruby, 89+7=96 ~~102+7=109~~

```
->n{n.prime_division.flat_map{|*a,b|a*b}.permutation.find{|x|x.join==x.join.reverse}||-1}

```

+7 for the `-rprime` flag.

*Sigh*, some Ruby builtins have such long names... at least that makes the code fairly self-explanatory.

The `flat_map` bit is because `prime_division` returns ex. `[[2, 2], [3, 1]]` for input `12` (which represents `2<sup>2</sup>3<sup>1</sup>`).

Thanks to @histocrat for 13 bytes!

# Answer
> 2 votes
# Julia, ~~132~~ 122 bytes

```
n->(x=filter(p->(q=join(p))==reverse(q),permutations(foldl(vcat,[[repeated(k,v)...]for(k,v)=factor(n)]))))==[]?-1:first(x)

```

This is a lambda function that accepts an integer and returns either an array or -1. To call it, assign it to a variable.

Ungolfed:

```
function f(n::Int)
    # Construct an array of all prime factors of n
    P = foldl(vcat, [[repeated(k, v)...] for (k, v) in factor(n)])

    # Filter the set of permutations of this array to only
    # those such that the string constructed by concatenating
    # all elements is a palindrome
    x = filter(p -> (q = join(p)) == reverse(q), P)

    # If x is empty, return -1, otherwise get the first array
    # in the collection
    return x == [] ? -1 : first(x)
end

```

Saved 10 bytes thanks to Glen O!

# Answer
> 2 votes
# Brachylog, 10 bytes

```
ḋp.cX↔X∨_1

```

Try it online!

```
  .           The output is
 p            a permutation of
ḋ             the prime factorization of
              the input
   c          such that concatenated
    X         it is the variable X
     ↔        which reversed
      X       is still X;
       ∨      if this is not possible,
              the output is
        _1    -1.

```

Initially, I had expected that having to output `-1` instead of being allowed to fail would be at a fairly large byte cost, but since the output in the case of success can't be concatenated, it only costs the two bytes necessary to write `_1` (if we removed those, it would leave the output unconstrained defaulting to `0`, and if we additionally changed the  to , the predicate would fail instead), because we need to break unification with the implicit output either way. (If the concatenation was the output for success but `-1` was still the output for failure, we'd have `ḋpc.↔|∧_1` or `ḋpc.↔.∨_1`. In the shortest case, where the output is concatenated and the predicate can fail, the whole thing is only five bytes: `ḋpc.↔`. Although not outputting the actual factors gives it more of a feel...)

# Answer
> 1 votes
## Haskell, 122 bytes

```
import Data.Numbers.Primes
import Data.List
f x=head$[p|p<-permutations$primeFactors x,s<-[show=<<p],s==reverse s]++[[-1]]

```

Usage example: `f 39` -\> `[3,13]`.

The obvious brute force approach. Iterating over all permutations of the prime factors and check for palindroms. Pick the first one. If there are none, the list is empty and the appended `[-1]` jumps in.

# Answer
> 1 votes
# Perl 6, 100 bytes

```
{$/=$_;map(->\f{|({$/%f||($//=f)&&f}...^*!==f)},2..$_).permutations.first({.join.flip eq.join})||-1}

```

```
{
  # store copy of argument in $/
  $/ = $_;
  # uses $/ so that I don't have to declare a variable

  # find the prime factors
  map(
    ->\f{
      # Slip so that outer list of all prime factors is flat
      |(
        {
          $/ % f    # return modulus
          ||        # or
          ($/ /= f) # factor the prime out of $/
          &&        # and
          f         # return factor
        }
        # produce a list of them and
        # stop when it returns something other than the factor
        # also ignoring the last non-factor value
        ...^ * !== f
      )
    },
    # find the factors out of the values from 2
    # up to the original argument
    2..$_
    # don't need to skip the non-primes as their
    # prime factorization will have already be
    # factored out of $/
  )

  # try all permutations of the prime factors
  .permutations

  # find the first palindromic one
  .first({ .join.flip eq .join })

  # return -1 if .first returned Nil or empty list
  || -1
}

```

Usage:

```
# give it a lexical name
my &prime-palindrome = {...}

say prime-palindrome    1; # -1
say prime-palindrome    2; # (2)
say prime-palindrome   11; # (11)
say prime-palindrome   13; # -1
say prime-palindrome   39; # (3 13)
say prime-palindrome   93; # (31 3)
say prime-palindrome    6; # -1
say prime-palindrome 1207; # (17 71)
say prime-palindrome  393; # -1
say prime-palindrome 2352; # (2 2 7 3 7 2 2)
say prime-palindrome 2351; # -1
say prime-palindrome 2350; # -1

```

---

About half of it (53 bytes) is taken up with the prime factorization code.

```
$/=$_;map(->\f{|({$/%f||($//=f)&&f}...^*!= f)},2..$_)

```

If there were a `prime-factorize` method the whole thing could be significantly shorter.

```
{.prime-factorize.permutations.first({.join.flip eq.join})||-1} # 63

```

# Answer
> 1 votes
# Jelly, 16 bytes

```
ÆFŒṙŒ!VŒḂ$ƇḢ¹-¹?

```

Longer than I expected, both in the byte count and the time it took to write.

Try it online!

**Explanation:**

```
ÆFŒṙŒ!VŒḂ$ƇḢ¹-¹?
ÆFŒṙ                Get the prime factors (gets them as exponents then run-length decodes).
    Œ!              Get the permutations.
          Ƈ         Filter (keep) the ones that...
       ŒḂ$          ...are palindromic when...
      V             ...joined.
           Ḣ        Take the first.
              ¹?    If the value is truthy...
            ¹       ...return the value...
             -      else return -1.

```

# Answer
> 1 votes
# Japt `-F-1`, 9 bytes

```
k á æ_¬êS

```

Try it

# Answer
> 0 votes
# Japt, 18 bytes

*Almost* as short as CJam...

```
Uk á f_¬¥Z¬w} g ªJ

```

Try it online!

### How it works

```
        // Implicit: U = input, e.g. 2352
Uk      // Factorize the input.      [2,2,2,2,3,7,7]
á       // Take permutations.        [[2,2,2,2,3,7,7],[2,2,2,2,7,3,7],[2,2,2,7,2,3,7],...]
f_   }  // Filter to only the ones that return truthily to this function:
Z¬¥Z¬w  //  Return Z.join('') == Z.join('').reverse().
        //                           [[2,2,7,3,7,2,2],[2,7,2,3,2,7,2],[7,2,2,3,2,2,7]]
g       // Take the first item.      [2,2,7,3,7,2,2]
ªJ      // If falsy, resort to -1.   [2,2,7,3,7,2,2]

```

# Answer
> 0 votes
# JavaScript (ES6), ~~256~~ ~~244~~ ~~208~~ 187 bytes

*Saved 36 bytes thanks to @Neil*

```
x=>eval("for(a=[],i=2;x>1;x%i?i++:(a.push(i),x/=i));p=-1,f=(z,t=[])=>z[0]?z.map((u,i)=>f([...z.slice(0,i),...z.slice(i+1)],[...t,u])):(y=t.join``)==[...y].reverse().join``&&(p=t),f(a),p")

```

Defines an anonymous function; prepend e.g. `F=` to use it. It's actually quite fast on input of 2352, only taking ~150 milliseconds to finish on my computer.

# Answer
> 0 votes
# APL(NARS), 169 chars, 338 bytes

```
∇r←F w;i;k;a;m;j
  r←⊂,w⋄→0×⍳1≥k←↑⍴w⋄a←⍳k⋄j←i←1⋄r←⍬⋄→C
A: m←i⊃w⋄→B×⍳(i≠1)∧j=m⋄r←r,m,¨∇w[a∼i]⋄j←m
B: i+←1
C: →A×⍳i≤k
∇
G←{F⍵[⍋⍵]}
f←{∨/k←{⍵≡⌽⍵}¨∊¨⍕¨¨v←Gπ⍵:↑k/v⋄¯1}

```

G would be the function find the permutations and f is the function of this exercise; test:

```
  ⎕fmt f¨11 4 39 6 1207 393 2352
┌7───────────────────────────────────────────────────┐
│┌1──┐ ┌2───┐ ┌2────┐    ┌2─────┐    ┌7─────────────┐│
││ 11│ │ 2 2│ │ 3 13│ ¯1 │ 17 71│ ¯1 │ 2 2 7 3 7 2 2││
│└~──┘ └~───┘ └~────┘ ~~ └~─────┘ ~~ └~─────────────┘2
└∊───────────────────────────────────────────────────┘

```

---
Tags: code-golf, palindrome, factoring
---


title: Encode an integer

text:
# Question
Title: Encode an integer
Given positive integer `n > 2`. We convert it to an array as follows:

1. If it is equal to `2` return an empty array
2. Otherwise create array of all `n`'s prime factors sorted ascending, then each element replace with its index in prime numbers sequence and finally convert each element to array

For example, lets convert number `46` to array. Firstly, convert it to array of its prime factors:

```
[2, 23]

```

Number `23` is `9`th prime, so replace `2` with empty array and `23` with `[9]`. Array now becomes:

```
[[], [9]]

```

Prime factors of `9` are `3` and `3`, so:

```
[[], [3, 3]]

```

Do the same for both `3`:

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

```

And finally:

```
[[], [[[]], [[]]]]

```

Now, to encode it, we simply replace each open bracket with `1` and each closing bracket with `0`, then remove all ending zeros and drop one `1` from the end. This is our binary number. Using the above example:

```
[ ] [ [ [ ] ] [ [ ] ] ]

| | | | | | | | | | | |
| | | | | | | | | | | |
V V V V V V V V V V V V

1 0 1 1 1 0 0 1 1 0 0 0

```

Now simply drop the last three zeros and the last `1`. The number becomes `10111001` which is `185` in decimal. That is the expected output. Notice that in array to binary conversion brackets of the main array are not included.

## Input

Positive integer `n` greater than `2`.

## Output

Encoded integer `n`.

## Rules and IO format

* Standard rules apply.
* Input can be string or number (but in case of string it must be in base 10).
* Output can be string or number (but in case of string it must be in base 10).
* This is , the shortest answer in bytes wins!

## Test cases

More test cases upon request.

```
3 ---> 1
4 ---> 2
5 ---> 3
6 ---> 5
7 ---> 6
8 ---> 10
9 ---> 25
10 ---> 11
10000 ---> 179189987
10001 ---> 944359
10002 ---> 183722
10003 ---> 216499
10004 ---> 2863321
10005 ---> 27030299
10006 ---> 93754
10007 ---> 223005
10008 ---> 1402478

```

## Sandbox

# Answer
> 14 votes
# Husk, ~~35~~ ~~31~~ ~~30~~ ~~29~~ ~~26~~ ~~25~~ ~~24~~ ~~22~~ ~~20~~ ~~19~~ 15 bytes

-7 bytes thanks to @Zgarb!

Saved an extra 4 bytes, indirectly, thanks to Zgarb

```
ḋhΣhgφṁȯ`Jḋ2⁰ṗp

```

Try it online!

### Explaination

```
     φ             -- Define a recursive function which calls itself ⁰ and is applied to an Integer
      ṁ       p    -- map then concatenate over its prime factors
             ṗ     --   return their indices into the primes
            ⁰      --   and then recur, applying ⁰ to that number
       ȯ`Jḋ2       --   then surround it between the list [1,0] (binary 2)
    g              -- group adjacent equal elements
   h               -- drop last element (trailing 0s)
  Σ                -- concatenate
 h                 -- drop the last element
ḋ                  -- interpret as base 2

```

# Answer
> 8 votes
# Jelly,  ~~22 20~~  19 bytes

-1 thanks to Erik the Outgolfer (tail zeros from both sides, `t`, rather than from the right `œr`)

```
ÆfÆC$ÐLŒṘO%3ḟ2Ḋt0ṖḄ

```

A monadic link taking an integer greater than 2 and returning an integer greater than 0 (2 would return 0 as per the original spec too).

**Try it online!**

### How?

This almost exactly replicates the description given, just with some ordinal manipulation for the creation of the binary array...

```
ÆfÆC$ÐLŒṘO%3ḟ2Ḋt0ṖḄ - Link: number n (>=2)
     ÐL             - loop until no more changes occur:
    $               -   last two links as a monad:
Æf                  -     prime factorisation (includes duplicates & vectorises)
  ÆC                -     count primes less than or equal (vectorises)
                    -   ...note for entries of 2 this yields [1]
                    -      then for entries of 1 it yields [], as required
       ŒṘ           - get a Python representation - just like in the OP,
                    -    something like: "[[], [[[]], [[]]]]" (for an input of 46)
         O          - convert to ordinals e.g. [91,91,93,44,32,91,91,91,93,93,44,32,91,91,93,93,93,93]
          %3        - modulo by 3         e.g. [ 1, 1, 0, 2, 2, 1, 1, 1, 0, 0, 2, 2, 1, 1, 0, 0, 0, 0]
            ḟ2      - filter discard twos e.g. [ 1, 1, 0, 1, 1, 1, 0, 0, 1, 1, 0, 0, 0, 0]
              Ḋ     - dequeue             e.g. [ 1, 0, 1, 1, 1, 0, 0, 1, 1, 0, 0, 0, 0]
               t0   - strip zeros         e.g. [ 1, 0, 1, 1, 1, 0, 0, 1, 1]
                 Ṗ  - pop                 e.g. [ 1, 0, 1, 1, 1, 0, 0, 1]
                  Ḅ - binary to decimal   e.g. 185

```

# Answer
> 6 votes
# Python 2, 212 177 bytes

```
lambda n:int(g(n).rstrip("0")[1:-1],2)
g=lambda n:"1%s0"%"".join(map(g,p(n)))
def p(n,i=0,j=1):
 while n>1:
  j+=1;P=q=1;exec"P*=q*q;q+=1;"*~-j;i+=P%q
  while n%j<1:yield i;n/=j

```

Try it online!

The lack of prime builtins really hurts the byte count, and it times out on TIO with larger primes. Uses xnor's primality check.

---

# Python 2 \+ gmpy2, 175 bytes

```
lambda n:int(g(n).rstrip("0")[1:-1],2)
g=lambda n:"1%s0"%"".join(map(g,p(n)))
def p(n,i=0,j=1):
 while n>1:
  j+=1;i+=is_prime(j)
  while n%j<1:yield i;n/=j
from gmpy2 import*

```

Try it online!

This version does not time out on the larger test cases (i.e. 10000 - 10008).

# Answer
> 5 votes
# Mathematica, ~~125~~ 119 bytes

```
Flatten[#//.{{1}->{1,0},a_/;a>1:>{1,List/@PrimePi[Join@@Table@@@FactorInteger@a],0}}]/.{1,d__,1,0..}:>{d}~FromDigits~2&

```

Uses a slightly different approach; converts prime indices to `{1, index, 0}`, and 2 to `{1, 0}`.

Try it on Wolfram Sandbox

**Usage:**

```
f = Flatten[ ...

f[10008]

```

> `1402478`

# Answer
> 3 votes
# Jelly, 35 bytes

```
ÆfẎW€ÆC2,“”y¹ß€Ṇ?
ÇŒṘḊ⁾][iÐ€ḟ0t1Ṗ’Ḅ

```

Try it online!

# Answer
> 3 votes
# J, ~~74~~ ~~73~~ 66 bytes

```
3 :'#.(}.~ >:@i.&1)&.|.2+}.;<@(_2,~_1,[:>:[:_1&p:q:) ::<"0@;^:_ y'

```

Try it online!

This is a real mess that certainly is in need of further golfing (e.g. removal of the explicit function definition). I think that the boxing I've been doing is especially what's bringing up the bytecount since I really don't know what I'm doing there (it's been a lot of trial and error). Also, I'm *pretty* sure that there are some built-ins I'm forgetting about (e.g. I feel like `_2,~_1,` probably has a built-in).

# Explanation (ungolfed)

### Preamble

Sit back tight, because this is not going to be a short explanation. Ironically, a terse language has been paired with a verbose person.

I'll be splitting this into a few functions

```
encode  =. 3 : '<@(_2,~_1, [: >: [: _1&p: q:) ::<"0@;^:_ y'
convert =. 3 : '2 + }. ; y'
drop    =. (}.~ >:@i.&1)&.|.
decode  =. #.

```
* `encode` encodes the integer using \_1 and \_2 instead of \[ and \]
* `convert` converts a list of \_1 and \_2 into a list of 1 and 0
* `drop` drops the last 1 and trailing zeroes
* `decode` converts from a binary list to a number

I'll be walking through a sample call for 46, which expressed in the ungolfed format is done

```
   decode drop convert encode 46
185

```

### Encode

There's a lot to explain here.

```
3 : '<@(_2,~_1, [: >: [: _1&p: q:) ::< "0@;^:_ y'
                                           ^:_      Do until result converges
                                          ;          Raze (remove all boxing)
                                       "0            For each
                               q:                     Factorize
                         _1&p:                        Get index of prime
                   >:                                 Add 1 (J zero-indexes)
            _1,                                       Prepend -1
        _2,~                                          Append -2
     <                                                Box resulting array
                                   ::                If there is an error
                                     <                Box the element

```

Note that the explicit function definition `3 : '[function]'` evaluates the function as if it were on the REPL with the right argument replacing every instance of `y` (this means that I can avoid having to use caps (`[:`), atops (`@`), and ats (`@:`) at the cost of a few bytes).

Here's what it looks like for each successive iteration on the input of 46

```
┌─────────┐    ┌──┬─────┬─────────┬──┐    ┌──┬──┬──┬──┬───────┬───────┬──┬──┐
│_1 1 9 _2│ => │_1│_1 _2│_1 2 2 _2│_2│ => │_1│_1│_2│_1│_1 1 _2│_1 1 _2│_2│_2│ =>
└─────────┘    └──┴─────┴─────────┴──┘    └──┴──┴──┴──┴───────┴───────┴──┴──┘

┌──┬──┬──┬──┬──┬─────┬──┬──┬─────┬──┬──┬──┐
│_1│_1│_2│_1│_1│_1 _2│_2│_1│_1 _2│_2│_2│_2│ => the final iteration is just every
└──┴──┴──┴──┴──┴─────┴──┴──┴─────┴──┴──┴──┘    value in its own box

```

This function makes use of adverse (`::`) in order to nest the values in "brackets" (the brackets used here are -1 and -2). Basically, every time we factorize and convert to prime number indices, \_1 is prepended and \_2 is appended, which act as brackets. When the function is called on those elements, it just returns them as-is since `q:` will error on trying to factorize a negative number. It's also fortunate that `q:` does *not* error on trying to factorize 1 and instead returns the empty array (as desired).

### Convert

```
3 : '2 + }. ; y'
            ;     Raze (remove boxing)
         }.       Behead (remove head)
     2 +          Add 2

```

Convert is a lot simpler. It just removes all the boxing, as well as the first element, and then converts everything to 1s and 0s (simply by adding 2)

### Drop

```
(}.~ >:@i.&1)&.|.
             &.|.  Reverse, apply the left function, and then undo
 }.~ >:@i.&1        Drop the leading zeroes and first 1
        i.&1         Index of first one
     >:              Add 1
 }.~                 Drop

```

This reverses the list, finds the first one and then drops all the values up to that one, then reverses the list again.

### Decode

Decode is the built-in function `#.` which takes a list of 1s and 0s and converts it to a binary number.

# Answer
> 2 votes
# Retina, ~~244~~ ~~227~~ 225 bytes

```
+%(G`
\d+
$*0¶$&$*
+`^00(0+)
0$1¶$0
A`^(00+?)\1+$
^0+
$0;1
+`(1+)¶0+(?=¶)
$0;1$1
+`¶(11+?)(\1)*$
¶$1¶1$#2$*1
1$

m`^11$
[]
m`^1+
[¶$.0$*0¶]
+s`(0+);(1+)(.+¶)\1¶
$1;$2$3$2¶
0+;1+¶

)`1+
$.0
T`[]¶`10_
10+$

1
01
+`10
011
^0+

1

```

Try it online!

This is a straight forward approach following the algorithm demonstrated in the question. The prime index generation is exponential complexity so it will time out for larger inputs

### Explanation:

```
+%(G`                Repeatedly apply on each line:
\d+                      If the line is a number, convert it to unary 0s and 1s
$*0¶$&$*
+`^00(0+)                Generate all prefixes of the zeros greater than 1
0$1¶$0
A`^(00+?)\1+$            Remove non-prime strings of zeros
^0+                      Index the first zero set (00) as 1
$0;1
+`(1+)¶0+(?=¶)           Index the rest of the zeroes as their prime index
$0;1$1
+`¶(11+?)(\1)*$          Compute prime factors of input value
¶$1¶1$#2$*1
1$                       Remove the 1 factor (not really prime)

m`^11$                   Turn all 2 prime factors to []
[]
m`^1+                    Surround all non-2 prime factors in brackets
[¶$.0$*0¶]
+s`(0+);(1+)(.+¶)\1¶     Convert non-2 prime factors to their index
$1;$2$3$2¶
0+;1+¶                   Remove the list of primes

)`1+                     Return all primes back to decimal ready to be repeated
$.0
T`[]¶`10_            Then convert all [ to 1 and ] to 0, and remove linefeeds
10+$                 Remove the final 1 and trailing zeroes

1                    Convert from binary to unary
01
+`10
011
^0+

1                    Convert from unary to decimal

```

# Answer
> 1 votes
# Haskell, ~~162~~ ~~160~~ 155 bytes

```
sum.zipWith((*).(2^))[0..].tail.snd.span(<1).(r%)
r=zip[1..][x|x<-[2..],all((>0).mod x)[2..x-1]]
_%1=[]
((i,q):p)%n|mod n q<1=r%div n q++0:r%i++[1]|1<3=p%n

```

Try it online!

**Explanation:**

`r=zip[1..][x|x<-[2..],all((>0).mod x)[2..x-1]]` defines an infinite list of tuples of primes and their indices: `[(1,2),(2,3),(3,5),(4,7),(5,11),(6,13), ...]`.

The function `(%)` takes this list `r` and a number `n` and converts the number into the reversed factor-array representation. This is done by stepping through `r` until we find a prime which divides `n`. We then recursively determine the representation of the index of this prime and enclose it in `0` and `1` and prepend the representation of `n` divided by that prime.

For `n=46`, this yields the list `[0,0,0,1,1,0,0,1,1,1,0,1]` from which then the leading zeros (`snd.span(<1)`) and the next `1` (`tail`) are dropped. Afterwards the list is converted to a decimal number by element-wise multiplying with a list of powers of two and summing up the resulting list: `sum.zipWith((*).(2^))[0..]`.

# Answer
> 1 votes
# tinylisp, 209 bytes

```
(load library
(d [(q((N)(map(q((P)([(length(filter prime?(1to P))))))(reverse(prime-factors N
(d B(q((L)(c 1(insert-end 0(foldl concat(map B L
(d T(q((N)(if(mod N 2)(/ N 2)(T(/ N 2
(q((N)(T(from-base 2(t(B([ N

```

The last line is an unnamed function that computes the specified encoding. Try it online!

### Pre-golfing version

This is the code I had before I started golfing it down:

```
(load library)

(def prime-index
 (lambda (P)
  (length (filter prime? (1to P)))))

(def to-list
 (lambda (N)
  (map to-list
   (map prime-index
    (reverse (prime-factors N))))))

(def to-bits
 (lambda (L)
  (cons 1
   (insert-end 0
    (foldl concat
     (map to-bits L))))))

(def trim
 (lambda (N)
  (if (mod N 2)
   (div2 N 2)
   (trim (div2 N 2)))))

(def encode
 (lambda (N)
  (trim
   (from-base 2
    (tail (to-bits (to-list N)))))))

```

# Answer
> 1 votes
# 05AB1E, 18 bytes

```
ΔÒ.Ø>}¸»Ç3%2K0Ü¨2β

```

Try it online!

Explanation:

```
Δ    }       # loop until a fixed point
 Ò           # replace each number with its prime factorization
  .Ø>        # replace each prime with its 1-based index
¸»           # after the loop: join to a string
  Ç          # get ASCII value of each character
   3%        # modulo 3 (maps '[' to 1, ']' to 0, ' ' to 2, ',' to 2)
     2K      # remove 2s
       0Ü    # trim trailing 0s
         ¨   # remove the last 1
          2β # parse as base 2

```

# Answer
> 0 votes
# JavaScript, 289 bytes

The bytes are the sum of the JavaScript code without linebreaks after the commas (which are inserted only for better formatting and readability) (256 bytes) and the additional characters for the command line switch, which is required when using Chrome (33 bytes).

```
'use strict'
var f=(n,i=2,r=[])=>n>1?n%i?f(n,i+1,r):f(n/i,i,r.concat(i)):r,
c=(p,r=1,i=2)=>i<p?f(i)[1]?c(p,r,i+1):c(p,r+1,i+1):r-1?f(r).map(h):[],
h=a=>c(a),
s=a=>a.reduce((r,e)=>r+s(e),'1')+' ',
o=i=>+('0b'+s(f(i).map(h)).trim().replace(/ /g,'0').slice(1,-1))

```

And a longer, better readable version:

```
'use strict';
const f = (n,i=2,r=[]) => n>1 ? n%i ? f(n,i+1,r) : f(n/i,i,r.concat(i)) : r;
const c = (p,r=1,i=2) => i<p ? f(i)[1] ? c(p,r,i+1) : c(p,r+1,i+1) : r-1 ? f(r).map(h) : [];
const h = i => c(i);
const s = a => a.reduce((r,e) => r+s(e),'1')+' ';
const o = i => +('0b'+s(f(i).map(h)).trim().replace(/ /g,'0').slice(1,-1));

```

Some brief explanations:

`f` is a purely functional tail-recursive factorization algorithm.

`c` counts at which place `r` the prime number `p` occurs in the sequence of prime numbers and returns either `[]` (if `p=2` and `r=1`) or factorizes and further processes `r` by means of recursion.

`h` is a small helper function which unfortunately is necessary as `map` calls the supplied function with `numberOfCurrentElement` as the second and `wholeArray` as the third argument, thus overriding the default values provided in `c` if we would pass this function directly (it took me some time to get after this pitfall; replacing `h` by its definition would be a few bytes longer).

`s` transforms the generated array to a string. We use `blank` instead of `0` so that we can use `trim()` in `o`.

`o` is the function to be called with the input value `i` which returns the output. It generates the binary string representation required by the specification and converts it to a (decimal) number.

**Edit:** Chrome must be started with `chrome --js-flags="--harmony-tailcalls"` to enable optimization of tail-recursion (see https://v8project.blogspot.de/2016/04/es6-es7-and-beyond.html). This also requires using strict mode.

The following test shows that the computation is a bit slow for some values (the longest is more than six seconds for `10007`on my computer). Interestingly, without optimization of tail-recursion the computation is much faster (about factor 5) when there is no stack overflow.

```
for (let i=3; i<=10008; i==10 ? i=10000 : ++i) {
    let time = new Date().getTime();
    let val = o(i);
    time = new Date().getTime() - time;
    document.write(i + ': ' + o(i) + ' (computed in ' + time + ' ms)<br>');
}

```

---
Tags: code-golf, number, primes, binary, factoring
---


title: Output the date in the Mel calendar

text:
# Question
Title: Output the date in the Mel calendar
The Mel calendar is used in the fictional world of Kaldia. Your goal is to convert dates into the Mel calendar.

This calendar has 13 months of 28 days each, plus 1 or 2 extra days after the last month. A year that is divisible by 4 but not by 100, or divisible by 400 has 366 days, and other years have 365 (i.e. our leap year rules, but with years in the Mel calendar).

You should use the month and day name abbreviations:

**months:** dia vio lis gil ful dyu mel ral zan pal mik fav ruj

**days:** dia vio lis gil ful dyu mel ral zan pal mik fav ruj ser rav tan lin rez jil din ket len lax nen pin mat kun mir

The extra days outside of any month have the month name of `myuxet` (no abbreviation here), and the day names are `axet` and `teems`, respectively.

`0 dia dia` is 1988/11/30.

You can take the input date as a string or a (year, month, day) tuple; alternatively, for functions, the parameter can be in your standard library's date type. The output should be a space-separated string.

## Test cases

```
1776-07-04 => -213 ral ket
1859-12-15 => -129 dia rav
1917-04-14 => -72 ful nen
1981-02-04 => -8 lis mik
1988-11-30 => 0 dia dia
1988-12-01 => 0 dia vio
1988-12-28 => 0 vio dia
2017-01-01 => 28 vio ful
2019-04-22 => 30 dyu lis
2019-11-30 => 30 myuxet axet
2019-12-01 => 31 dia dia
2021-11-29 => 32 myuxet axet
2021-11-30 => 32 myuxet teems
2089-11-30 => 101 dia dia
2389-11-30 => 400 myuxet teems

```

You should be able to handle dates from 1 AD to 9999 AD at least.

Reference implementation in Perl 6

Standard loopholes are forbidden.

# Answer
# Perl 6, 174 bytes

```
{~(.year,(|[X]("diaviolisgilfuldyumelralzanpalmikfavrujserravtanlinrezjildinketlenlaxnenpinmatkunmir".comb(3)xx 2)[^364],|("myuxet"X <axet teems>))[.day-of-year-1])}o*-726436

```

Try it online!

Generate a list of all the valid dates and then indexes the day of the year into that list.

### Explanation

```
{                                                   }  # Anonymous code block
                                                     o*-726436  # Subtract some days from the input
  (.year,                               # Output the year
           [X]("...".comb(3))[^365]     # Then produce a list of all months/days
         (|                        ,
          |("myuxet"X <axet teems>))    # And the extra days
                                    [.day-of-year-1]   # And get the current date
 ~   # Stringify the list

```
> 4 votes

# Answer
# Ruby, ~~199~~ ~~195~~ 193 bytes

Oof, only ~~23~~ ~~27~~ 29 bytes saved over the sample Perl code...

-4 bytes from @NickKennedy.

-2 bytes from @Neil.

```
->d{d-=62764e6;y=d.yday;s="diaviolisgilfuldyumelralzanpalmikfavrujserravtanlinrezjildinketlenlaxnenpinmatkunmir".scan /.../;[d.year,y<364?s[y/28]:"myuxet",(y<364?s:%w[axet teems])[y%28-1]]*' '}

```

Try it online!
> 3 votes

# Answer
# Japt `-S`, 148 bytes

```
ÐUVW;f1Uf -726436
-ÐTT i1Ui¹z864e5
`¹avio¦sgÅ~ldyu´llzpal·kfavruj rvt¦nzjÅanket¤nlaxnpµtkun·r`pD ò3
[Ui Vz28 gW¯D p"myuxet")VgWp"axet"`ems`]

```

Saved 4 bytes thanks to @Shaggy. +A lot more bytes due to bug-fixes. Takes months as 0-indexed numbers.

Japt does have built-in date handling, but it's not very good. Seriously, 34 bytes to initialize a date, then subtract days from it, and then calculate which day of the year it is?

Try it

```
ÐUVW;                Initialize date object with given inputs
f1Uf -726436         Subtract 726436 days; Store in variable 'U'
-ÐTT i1Ui¹z864e5     Store the day of year in variable 'V'
`...`                Compressed string of all the days
  pD                 Repeated 13 times
    ò3               Split into chunks, where each chunks is 3 chars long, store in variable 'W'
[Ui                  Year
Vz28 gW¯D p"myuxet") Month
VgWp"axet"`ems`]    Day

```
> 3 votes

# Answer
# Jelly, ~~181~~ 164 bytes

```
“BƥṠĿZȧ{ḷċ'#1ƇIræżzḤ$ḅ3ṃefɲ⁴S⁵ẊKḲ&8ɲz⁸Ẋ⁼ṣẸÇɼ:İ~¢ȥ³QⱮ:Ṗỵrɼ¬ṂĿZ⁵ṣ»Ḳḣ€3ḣ13pƊ;“¬ỵƇnḄẋFƬ@§Żị»ḲḢWpƊ¤
“ÇġƁʠÇỤḷṁÑWðṫ⁷m¥ṛʂɲðḊk¶`Ḣ»ḲjḢ$;;“","%Y%m%d"))+3499e5)”ŒVm7_2ȷ;ị¢$}ʋ/K

```

Try it online!

Jelly has no built-in date handling, so this falls back on the functionality within Python’s time module.

### Explanation

```
“Bƥ...⁵ṣ»                      | Compressed string "diact viol lisk gild full dyu mela rale zanja palay miked fava ruj ser rave tanas linac rez jilt dinar ket lend lax nene pinas mat kune mire"
         Ḳ                     | split at spaces
          ḣ€3                  | first 3 characters of each
                 Ɗ             | following links as a monad
             ḣ13               |    first 13
                p              |    Cartesian product (with all 28)
                 ;           ¤ | concatenate to:
                  “¬...ị»      |   compressed string "myuxet axet teems"
                         Ḳ     |   split at spaces
                            Ɗ  |   following two links as a monad
                          Ḣ    |     head
                           p   |     Cartesian product (with last two)

“Ç...Ḣ»                             | Compressed string 'time  .local ( .mk ( .strp ("'
       Ḳ                            | split at spaces
        jḢ$                         | join using first item (i.e. time)
           ;                        | concatenate to input
            ;“"...)”                | concatenate this to '","%Y%m%d"))+3499e5)'
                    ŒV              | eval as Python
                      m7            | take every 7th item (year and day in year)
                                ʋ/  | reduce using following links as a dyad
                        _2ȷ         |   subtract 2000 (from first value, the year)
                           ;ị¢$}    |   concatenate with right argument (day in year) indexed into above link
                                  K | join with spaces

```
> 2 votes

# Answer
## JavaScript (ES6), ~~297~~ ~~269~~ ~~252~~ ~~249~~ 245 bytes

```
f=
d=>(d=new Date(+d+3498336e5),d=(d-Date.UTC(y=d.getUTCFullYear(a=`diaviolisgilfuldyumelralzanpalmikfavrujserravtanlinrezjildinketlenlaxnenpinmatkunmir`.match(/.../g))))/864e5,y-2e3+` ${d<364?a[d/28|0]+` `+a[d%28]:`myuxet ${d&1?`teems`:`axet`}`}`)
```

```
<input type=date oninput=o.textContent=f(this.valueAsDate)><pre id=o>
```

Takes input as a JavaScript date object in UTC (would be 1 byte less as a JavaScript timestamp number). Edit: Saved ~~3~~ 7 bytes thanks to @Arnauld.

Try it online! if the snippet still isn't working for you for some reason.
> 1 votes

# Answer
# C# (Visual C# Interactive Compiler), 247 bytes

```
n=>$"{(n=n.AddDays(4049)).Year-2e3} {((k=n.DayOfYear-1)<365?s.Substring(k/28*3,3):"myuxet")} {(k<365?s.Substring(k%28*3,3):k<366?"axets":"teems")}";var s="diaviolisgilfuldyumelralzanpalmikfavrujserravtanlinrezjildinketlenlaxnenpinmatkunmir";int k;

```

Try it online!
> 1 votes

# Answer
# Haskell, ~~387~~ ~~373~~ 372 bytes

```
import Data.Time.Calendar
t(a:b:c:r)=[a,b,c]:t r
t _=[]
w=t"diaviolisgilfuldyumelralzanpalmikfavrujserravtanlinrezjildinketlenlaxnenpinmatkunmir"
(%)=mod
a y=map(show y++)$[' ':m++' ':d|m<-take 13 w,d<-w]++" myuxet axet":[" myuxet teems"|y%4<1,y%400<1||y%100>0]
f d|n<-read.show$diffDays d$fromGregorian 1988 11 30=last$(a=<<[0..])!!n:[(reverse.a=<<[-1,-2..])!!(-n-1)|n<0]

```

Try it online!

Takes input as a `Day` object.

This was pretty fun to write! Basic idea is to build a list of dates and index into it for the result. Function `a` takes a year and outputs every date in that year in chronological order. Function `f` expands on `a` concatenating them together for successive years starting at 0. The trick is that for dates before the epoch we need to traverse backwards starting from the year -1 so we pass a values -1,-2... and reverse each list individually before concatenating them together. Finally, in function `f` we calculate the number of days between the epoch and our date (converting it from `Integer` to `Int`) and index into our list, taking care to fix our index if it's negative.

EDIT: golfed it down (-14)

EDIT 2: golfed down the day/month names list (-1)
> 1 votes

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


title: Building a Structured Outline

text:
# Question
Title: Building a Structured Outline
In a fictional document management system, input documents are structured with weighted headings. Lowest weighted headings are the most important.

This is a sample document:

H1 All About Birds

H2 Kinds of Birds

H3 The Finch

H3 The Swan

H2 Habitats

H3 Wetlands

From this document we would like to produce an outline using nested ordered lists in HTML, which would look like this when rendered:

1. All About Birds
    1. Kinds of Birds
        1. The Finch
        2. The Swan
    2. Habitats
        1. Wetlands

Your code only needs to take the input list and transform it into the expected data structure, which will be printed.

# Answer
> 0 votes
# Jelly, ~~53~~ 50 bytes

```
Ḋœṡ¥€⁶ZµḢVØ0jI>0ẋ"AƲị“<ol>“</ol>”żṪ“<li>“</li>”jⱮƊ

```

Try it online!

A monadic link taking a list of strings as input and outputting an HTML fragment with nested ordered lists. Should handle arbitrarily deep nesting of lists and return a syntactically valid HTML fragment.

## Example:

```
H1 All About Birds
H2 Kinds of Birds
H3 The Finch
H3 The Swan
H2 Habitats
H3 Wetlands
H4 Types of wetlands
H5 Very wet wetland
H3 Coast
H1 All about fish
H2 Sharks

```

yields:

```
<ol><li>All About Birds</li><ol><li>Kinds of Birds</li><ol><li>The Finch</li><li>The Swan</li></ol><li>Habitats</li><ol><li>Wetlands</li><ol><li>Types of wetlands</li><ol><li>Very wet wetland</li></ol></ol><li>Coast</li></ol></ol><li>All about fish</li><ol><li>Sharks</li></ol></ol>

```
1. All About Birds
1. Kinds of Birds
1. The Finch
2. The Swan

3. Habitats
1. Wetlands
1. Types of wetlands
1. Very wet wetland

3. Coast

3. All about fish
1. Sharks

---
Tags: code-golf, string, data-structures
---