title: How many cubes can be built

text:
# Question
Title: How many cubes can be built
# task

Your task is to build a structure with \\$n\\$ cubes. The volume of cubes follow the following sequence (bottom *-\>* top)

# \\$n^3, (n-1)^3, (n-2)^3,...,1^3\\$

# input

The total volume of the structure (\\$V\\$).

# output

value of (\\$n\\$), i.e : The total number of cubes.

\\$V = n^3 + (n-1)^3 + .... + 1^3\\$

# notes

* Input will always be an integer.
* Sometimes it isn't possible to follow the sequence, i.e : \\$V\\$ doesn't represent a specific value for \\$n\\$. In that event return -1, or a falsy value of your choosing (consistency is required though).
* This is so shortest answer in bytes for each language wins.
* No answer will be marked accepted for the above mentioned reason.

# requests

* This is my first challenge on the site so bear with me, and forgive (and tell me about) any mistakes that I made.
* Kindly provide a link so your code can be tested.
* If you can, kindly write an explanation on how your code works, so others can understand and appreciate your work.

# examples

```
input  : 4183059834009
output : 2022

input  : 2391239120391902
output : -1

input  : 40539911473216
output : 3568

```

---

Thanks to @Arnauld for the link to this :

Isn't that nice.

Link to orignial : Link

# Answer
> 18 votes
# JavaScript (ES7), 31 bytes

A direct formula. Returns `0` if there's no solution.

```
v=>(r=(1+8*v**.5)**.5)%1?0:r>>1

```

Try it online!

### How?

The sum \\$S\_n\\$ of the first \\$n\\$ cubes is given by:

$$S\_n = \left(\frac{n(n+1)}{2}\right)^2 = \left(\frac{n^2+n}{2}\right)^2$$

(This is A000537. This formula can easily be proved by induction. Here is a nice graphical representation of \\$S\_5\\$.)

Reciprocally, if \\$v\\$ is the sum of the first \\$x\\$ cubes, the following equation admits a positive, integer solution:

$$\left(\frac{x^2+x}{2}\right)^2=v$$

Because \\$(x^2+x)/2\\$ is positive, this leads to:

$$x^2+x-2\sqrt{v}=0$$

Whose positive solution is given by:

$$\Delta=1+8\sqrt{v}\\ x=\frac{-1+\sqrt{\Delta}}{2} $$

If \\$r=\sqrt{\Delta}\\$ is an integer, it is guaranteed to be an odd one, because \\$\Delta\\$ itself is odd. Therefore, the solution can be expressed as:

$$x=\left\lfloor\frac{r}{2}\right\rfloor$$

### Commented

```
v =>                    // v = input
  ( r =                 //
    (1 + 8 * v ** .5)   // delta = 1 + 8.sqrt(v)
    ** .5               // r = sqrt(delta)
  ) % 1 ?               // if r is not an integer:
    0                   //   return 0
  :                     // else:
    r >> 1              //   return floor(r / 2)

```

---

# Recursive version, ~~36~~ 35 bytes

Returns `NaN` if there's no solution.

```
f=(v,k=1)=>v>0?1+f(v-k**3,k+1):0/!v

```

Try it online!

### Commented

```
f = (v,                   // v = input
        k = 1) =>         // k = current value to cube
  v > 0 ?                 // if v is still positive:
    1 +                   //   add 1 to the final result
    f(                    //   do a recursive call with:
      v - k ** 3,         //     the current cube subtracted from v
      k + 1               //     the next value to cube
    )                     //   end of recursive call
  :                       // else:
    0 / !v                //   add either 0/1 = 0 if v is zero, or 0/0 = NaN if v is
                          //   non-zero (i.e. negative); NaN will propagate all the
                          //   way to the final output

```

# Answer
> 7 votes
# 05AB1E, 6 bytes

```
ÝÝOnIk

```

Try it online!

Port of Jonathan's Jelly answer. Take the cumulative sum of **\[0 ... n\]**, square each and find the index of **V**.

---

### 05AB1E, 7 bytes

```
ÝÝ3mOIk

```

Try it online!

### How it works

```
ÝÝ3mOIk – Full program.
ÝÝ      – Yield [[0], [0, 1], [0, 1, 2], ... [0, 1, 2, ... V]].
  3mO   – Raise to the 3rd power.
     Ik – And find the index of the input therein. Outputs -1 if not found.

```

8-byte alternative: `ÝÝÅΔ3mOQ`.

# Answer
> 6 votes
# , ~~42~~ 40 bytes

*-2 bytes thanks to Giuseppe*

```
function(v,n=((1+8*v^.5)^.5-1)/2)n*!n%%1

```

Try it online!

Port of Arnauld's JavaScript answer. Also returns 0 if there's no solution.

# Answer
> 5 votes
# Jelly,  ~~5~~  4 bytes

```
RÄ²i

```

A monadic link, yields `0` if not possible.

**Try it online!** way too inefficient for the test cases! (O(V) space :p)

Here is an 8-byte version that performs a cube-root of V first to make it O(V^(1/3)) instead. Using that 8-byte version here is a test-suite

### How?

$$\sum\_{i=1}^{i=n}i^3=\left(\sum\_{i=1}^{i=n}i\right)^2$$

```
RÄ²i - Link: integer, V
R    - range of v -> [1,2,3,...,V]
 Ä   - cumulative sums -> [1,3,6,...,(1+2+3+...+V)]
  ²  - square -> [1,9,36,...,(1+2+3++...+V)²] ( =[1³,1³+2³,1³+2³+3³,...,(1³+2³+3³+...+V³)] )
   i - first 1-based index of v? (0 if not found)

```

# Answer
> 4 votes
# Elixir, 53 bytes

```
&Enum.find_index 0..&1,fn n->&1*4==n*n*(n+1)*(n+1)end

```

Try it online!

Port of Jonathan's Jelly answer.

---

# Elixir, 74 bytes

```
fn v->Enum.find_index 0..v,&v==Enum.sum Enum.map(0..&1,fn u->u*u*u end)end

```

Try it online!

Definitely sub-optimal. But I am just an Elixir newbie! :) Returns `nil` for "invalid" values of `V`.

# Answer
> 3 votes
# Japt, 7 bytes

```
o³å+ bU

```

Try it

---

## Explanation

```
            :Implicit input of integer U
o           :Range [0,U)
 ³          :Cube each
  å+        :Cumulatively reduce by addition
     bU     :0-based index of U

```

---

## Alternative

```
Çõ³xÃbU

```

Try it

# Answer
> 3 votes
# Cubix, 27 bytes (or volume 27?)

Seems like the right place for this language.

```
I@.1OW30pWpP<s)s;;q\.>s-.?/

```

Try it online!

This wraps onto a 3x3x3 cube as follows

```
      I @ .
      1 O W
      3 0 p
W p P < s ) s ; ; q \ .
> s - . ? / . . . . . .
. . . . . . . . . . . .
      . . .
      . . .
      . . .

```

Watch it run

It essential brute forces by taking increasing cubes away from the input. If it results in zero, output *`n`* otherwise if there is a negative result, print 0 and exit.

# Answer
> 2 votes
# Perl 6, ~~30~~ ~~29~~ 26 bytes

*-4 bytes thanks to Jo King*

```
{first :k,.sqrt,[\+] ^1e4}

```

Try it online!

Brute-force solution for n \< 10000. Uses the equation from Jonathan Allan's answer. ~~37~~ 36 bytes solution for larger n (*-1 byte thanks to Jo King*):

```
{!.[*-1]&&$_-2}o{{$_,*-$++³...1>*}}

```

Try it online!

Returns `False` if there's no solution.

### Explanation

```
               o  # Combination of two anonymous Blocks
                {                 }  # 1st Block
                 {               }   # Reset anonymous state variable $
                  $_,*-$++³...1>*    # Sequence n,n,n-1³,n-1³-2³,... while positive
{             }  # 2nd Block
 !.[*-1]&&       # Return False if last element is non-zero
          $_-2   # Return length of sequence minus two otherwise

```

# Answer
> 2 votes
# JavaScript (Node.js), 28 bytes

```
a=>a**.5%1?0:(2*a**.5)**.5|0

```

Try it online!

I know it's my own question and all, but I had a better answer (for this lang) then is present, so I posted. Hope it's ok

# Answer
> 1 votes
## Matlab, 27 bytes

```
@(v)find(cumsum(1:v).^2==v)

```

Returns the `n` if exists or an empty matrix if not.

**How it works**

```
            1:v            % Creates a 1xV matrix with values [1..V]
     cumsum(   )           % Cumulative sum
                .^2        % Power of 2 for each matrix element
                   ==v     % Returns a 1xV matrix with ones where equal to V
find(                 )    % Returns a base-1 index of the first non-zero element

```

Try it Online!

**Note** It fails for large `v` due to memory limitations.

# Answer
> 1 votes
# APL (Dyalog), 18 bytes

```
{o×⍵≥o←⍵⍳⍨+\3*⍨⍳⍵}

```

Try it online!

# Answer
> 1 votes
# Python 3, 60 bytes

```
lambda V:[*[(n*-~n/2)**2for n in range(V+1)],V].index(V)%-~V

```

Try it online!

-6 thanks to Mr. Xcoder.

If we can throw an error in case there's no \\$n\\$ for a particular \\$V\\$, we can get this down to 51 bytes:

```
lambda V:[(n*-~n/2)**2for n in range(V+1)].index(V)

```

Try it online!

# Answer
> 1 votes
# Python 3, ~~53~~ 48 bytes

```
f=lambda V,n=1:V>0and f(V-n**3,n+1)or(not V)*n-1

```

Try it online!

-3 bytes from Jo King

Returns `-1` for no answer.

Only works up to `n=997` with the default recursion limits.

Repeatedly takes bigger and bigger cubes from the volume until it arrives at zero (success, return number of cubes removed), or a negative number (no answer).

Explanation:

```
f=lambda V,n=1: # f is a recursive lambda taking the volume and the cube size (defaulting to 1)

               V>0and               # if the volume is positive
                      f(V-n**3,n+1) # then we are not to the right cube size yet, try again with n+1, removing the volume of the nth cube

                                   or # if V is not positive
                                     (not V)*n-1
                         # case V == 0:
                         # (not V)*n == n; return n-1, the number of cubes
                         # case V < 0:
                         # (not V)*n == 0; return -1, no answer

```

# Answer
> 1 votes
# Perl 6, 33 bytes

```
{$!+>1 if ($!=sqrt 1+8*.sqrt)%%1}

```

Try it online!

This uses Arnauld's method. Returns an Empty object if the number is not valid.

# Answer
> 1 votes
# dc, 19 bytes

```
4*dvvdddk*+d*-0r^K*

```

Input and output is from the stack, returns 0 if no solution.

Try it online!

# Explanation

If there's a solution n, the input is `((n^2+n)^2)/4`. So we'll calculate a trial solution as `n=sqrt(sqrt(4*input))`, using dc's default 0 decimal place precision for square roots, then compare `(n^2+n)^2` to `4*input` to see if it's actually a solution.

```
4*dvv         Calculate a trial solution n (making a copy of 4*input for later use)
dddk          Store the trial solution in the precision and make a couple copies of it
*+d*          Calculate (n^2+n)^2
-             Subtract from our saved copy of 4*input - now we have 0 iff n is a solution
0r^           Raise 0 to that power - we now have 1 if n is a solution, 0 if not
K*            Multiply by our saved trial solution

```

The penultimate line relies on the non-obvious fact that to dc, `0^x=0` for all nonzero `x` (even negative `x`!) but `0^0=1`.

# Answer
> 0 votes
# gvm (commit 2612106) bytecode, 70 59 bytes

(-11 bytes by multiplying in a loop instead of writing the code for multiplying twice)

Hexdump:

```
> hexdump -C cubes.bin
00000000  e1 0a 00 10 00 1a 03 d3  8a 00 f6 2a fe 25 c8 d3  |...........*.%..|
00000010  20 02 2a 04 0a 01 1a 02  00 00 20 08 4a 01 fc 03  | .*....... .J...|
00000020  d1 6a 02 52 02 cb f8 f4  82 04 f4 e8 d1 6a 03 0a  |.j.R.........j..|
00000030  03 fc d5 a8 ff c0 1a 00  a2 00 c0                 |...........|
0000003b

```

Test runs:

```
> echo 0 | ./gvm cubes.bin
0
> echo 1 | ./gvm cubes.bin
1
> echo 2 | ./gvm cubes.bin
-1
> echo 8 | ./gvm cubes.bin
-1
> echo 9 | ./gvm cubes.bin
2
> echo 224 | ./gvm cubes.bin
-1
> echo 225 | ./gvm cubes.bin
5

```

Not really a low score, just using this nice question for testing `gvm` here ;) The commit is older than the question of course. **Note** this is an 8bit virtual machine, so using some code handling only the natural unsigned number range `0-255`, the test cases given in the question won't work.

Manually assembled from this:

```
0100  e1         rud                     ; read unsigned decimal
0101  0a 00      sta     $00             ; store to $00 (target sum to reach)
0103  10 00      ldx     #$00            ; start searching with n = #0
0105  1a 03      stx     $03             ; store to $03 (current cube sum)
0107  d3         txa                     ; X to A
                   loop:
0108  8a 00      cmp     $00             ; compare with target sum
010a  f6 2a      beq     result          ; equal -> print result
010c  fe 25      bcs     error           ; larger -> no solution, print -1
010e  c8         inx                     ; increment n
010f  d3         txa                     ; as first factor for power
0110  20 02      ldy     #$02            ; multiply #02 times for ...
0112  2a 04      sty     $04             ; ... power (count in $04)
                   ploop:
0114  0a 01      sta     $01             ; store first factor to $01 ...
0116  1a 02      stx     $02             ; ... and second to $02 for multiplying
0118  00 00      lda     #$00            ; init product to #0
011a  20 08      ldy     #$08            ; loop over 8 bits
                   mloop1:
011c  4a 01      lsr     $01             ; shift right first factor
011e  fc 03      bcc     noadd1          ; shifted bit 0 -> skip adding
0120  d1         clc                     ;
0121  6a 02      adc     $02             ; add second factor to product
                   noadd1:
0123  52 02      asl     $02             ; shift left second factor
0125  cb         dey                     ; next bit
0126  f8 f4      bpl     mloop1          ; more bits -> repeat
0128  82 04      dec     $04             ; dec "multiply counter" for power
012a  f4 e8      bne     ploop           ; not 0 yet -> multiply again
012c  d1         clc
012d  6a 03      adc     $03             ; add power to ...
012f  0a 03      sta     $03             ; ... current cube sum
0131  fc d5      bcc     loop            ; repeat unless adding overflowed
                   error:
0133  a8 ff      wsd     #$ff            ; write signed #$ff (-1)
0135  c0         hlt                     ;
                   result:
0136  1a 00      stx     $00             ; store current n to $00
0138  a2 00      wud     $00             ; write $00 as unsigned decimal
013a  c0         hlt

```

*edit*: I just fixed a bug in `gvm`; without this fix, `gvm` tried to read binary programs in *text mode*, which might break (code above doesn't contain any `0xd` bytes so won't break on windows without this fix).

# Answer
> 0 votes
# K (oK), 21 bytes

```
{(,_r%2)@1!r:%1+8*%x}

```

Try it online!

Port of Arnauld's JS answer.

### How:

```
{(,_r%2)@1!r:%1+8*%x} # Main function, argument x
             %1+8*%x  # sqrt(1+(8*(sqrt(x)))
           r:         # Assign to r
         1!           # r modulo 1
        @             # index the list:
 (,_r%2)              # enlist (,) the floor (_) of r modulo 2.

```

the function will return `(_r%2)` iff `1!r == 0`, else it returns null (`0N`). That is due to the single element in the list having index 0, and trying to index that list with any number other than 0 will return null.

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


title: Let's draw the Triforce

text:
# Question
Title: Let's draw the Triforce
The Triforce is a fictional artifact in The Legend of Zelda, made of three identical-looking equilateral triangles representing power, wisdom and courage. Several games in the saga include an animation when the three parts finally join together.

The purpose of this challenge is to draw a single 2D frame of such a simplified animation, with a given width for the triangles and a given spacing between the parts.

## Input

The input consists of two integers: a width \\$w\ge1\\$ and a spacing value \\$s\ge0\\$.

## Output

The frame has to be drawn according to the following specifications:

```
         /\
        /  \____________ this part is horizontally centered
       /    \
      /______\
                    \___ s empty lines
                    /
   /\          /\
  /  \        /  \______ w+1 backslashes
 /    \      /    \
/______\    /______\
                \_______ 2w underscores
        |__|
          \_____________ 2s spaces

```

In the above example, we have \\$w=3\\$ and \\$s=2\\$.

## More examples

\\$w=1\\$, \\$s=0\\$:

```
   /\
  /__\
 /\  /\
/__\/__\

```

\\$w=2\\$, \\$s=0\\$:

```
     /\
    /  \
   /____\
  /\    /\
 /  \  /  \
/____\/____\

```

\\$w=3\\$, \\$s=3\\$:

```
          /\
         /  \
        /    \
       /______\

   /\            /\
  /  \          /  \
 /    \        /    \
/______\      /______\

```

\\$w=4\\$, \\$s=1\\$:

```
          /\
         /  \
        /    \
       /      \
      /________\

    /\          /\
   /  \        /  \
  /    \      /    \
 /      \    /      \
/________\  /________\

```

## Rules

* Trailing spaces on each line are optional.
* Extra leading spaces on each line are not allowed.
* You may output a single extra leading newline and/or a single extra trailing newline.
* This is .

# Answer
# Python 2, ~~197~~ ~~194~~ ~~169~~ ~~167~~ ~~155~~ 144 bytes

```
w,s=input()
l=['']*(2*-~w+s)
for i in range(-~w):W=w-i;b='/'+'_ '[i<w]*2*i+'\\';l[i::w-~s]=' '*(w+s-~W)+b,' '*W+b+'  '*(W+s)+b
print'\n'.join(l)

```

Try it online!

---

Saved:

* -3 bytes, thanks to Mr. Xcoder
> 10 votes

# Answer
# Charcoal, 25 bytes

```
←×_Ｎ↗⊕θ‖Ｍ≔⁺⊕θＮηＣη±η‖ＢＯ⊗⊕θ

```

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

```
←×_Ｎ

```

Input `w` and draw `w` `_`s.

```
↗⊕θ

```

Draw `w+1` `/`s.

```
‖Ｍ

```

Reflect to complete the first triangle.

```
≔⁺⊕θＮη

```

Input `s` and calculate the offset between the left and middle triangles.

```
Ｃη±η

```

Copy the left triangle to the middle.

```
‖ＢＯ⊗⊕θ

```

Reflect around the middle triangle to complete the triforce.
> 9 votes

# Answer
# Python 2, ~~127~~ 124 bytes

```
w,s=input()
n=2*-~w+s
while n:n-=1;I=w-n+(n>w)*(w-~s);print' '*n+('  '*(n+s)).join(['/'+I*2*' _'[I>=w]+'\\'][I>w:]*-~(n<=w))

```

Try it online!
> 8 votes

# Answer
# Canvas, ~~20~~ ~~19~~ 16 bytes

```
＋├：⁸╵＼Ｌ_×；∔║ω╋║↕

```

Try it here!

Explanation:

```
+├                s + w + 2
  :               duplicated (for both X & Y)
   ⁸╵\            w+1 sized diagonal
      L_×         "_"*width of the diagonal
         ;∔       prepended before the diagonal
           ║      palindromize that
            ω     and push the argument of ║ (aka the unpalindromized version)
             ╋    overlap the upside down half-triangle over the upside down triangle at (s+w+2; s+w+2)
              ║   and palindromize the whole thing
               ↕  reverse everything vertically

```

note: in the making of this I fixed a mistake in the code, Without that fix, this would be 18 bytes.
> 7 votes

# Answer
# , ~~225~~, ~~224~~, ~~214~~, ~~211~~, 208 bytes

```
function(w,s){M=matrix
C=cbind
h=w+1
k=C(apply(m<-diag(h)*60,1,rev)/4,m)
k[row(k)==h&!k]=63
z=rbind(C(a<-M(0,h,h+s),k,a),M(0,s,h*4+2*s),C(k,M(0,h,2*s),k))
z[]=intToUtf8(z+32,T)
apply(z,1,cat,sep='','
')
rm()}

```

Try it online!

* -1 byte thanks to Giuseppe
* -10 bytes after change of approach
* -3 bytes exploting ASCII code
* -3 bytes thanks to JayCe
> 7 votes

# Answer
# Python 2, ~~256~~ ~~248~~ ~~240~~ ~~228~~ ~~199~~ 195 bytes

A longer program, but slightly different approach:

```
f,b,o='/\ '
O=o*2
w,s=input()
l=f+'__'*w+b
a=l+O*s+l
m=n=[]
p=lambda g:(len(a)-len(g))/2*o+g
for i in range(w):m=m+[p(f+O*i+b)];t=f+O*i+b;n+=p(t+O*(w-i+s)+t),
print'\n'.join(m+[p(l)]+[o]*s+n+[a])

```

Try it online!

---

saved a lot of bytes thanks to ignoring the trailing whitespace, and incorporating some tricks from @ovs
saved even more by defining a variable earlier
> 4 votes

# Answer
# Pascal (FPC), ~~296~~ 264 bytes

```
const A='/';B='\';var w,s,i:word;u:string;begin read(w,s);u:=StringOfChar('_',2*w);for i:=1to w do writeln(A:w+3+s+w-i,B:i*2-1);writeln(A:w+2+s,u,B);for i:=1to s do writeln;for i:=1to w do writeln(A:w+2-i,B:i*2-1,A:2*(s+w-i)+3,B:i*2-1);write(A,u,B,A:2*s+1,u,B)end.

```

Try it online!
> 4 votes

# Answer
# Ruby, 126 bytes

```
->w,s{(-v=w+1).upto(v){|i|j= ~-i%-~v;$><<[$/*s,$/+' '*(v+s)+t="/#{(j<w ?' ':?_)*j*2}\\".center(w*2+2)+' '*s*2,$/+t*2][0<=>i]}}

```

Try it online!
> 3 votes

# Answer
# Retina 0.8.2, 141 bytes

```
\d+
$*
(?=( *),( *))
¶$1/$`$`\$1$2$2$1/$`$`\
T` `\_`/ *\\(?=.*,)
s`¶(.*),( *)
$1¶$.2$*¶$1
\G(( *)/(  |__)*\\)\2(  )*\1 *¶
$2 $#3$* $#4$* $1¶

```

Try it online! Note: Some trailing whitespace in output. Explanation:

```
\d+
$*

```

Convert the inputs into spaces. (The second line ends with a space.)

```
(?=( *),( *))
¶$1/$`$`\$1$2$2$1/$`$`\

```

Create the sides of the bottom two triangles with the appropriate spacing.

```
T` `\_`/ *\\(?=.*,)

```

Fill in the base of the triangles.

```
s`¶(.*),( *)
$1¶$.2$*¶$1

```

Duplicate the triangles with the appropriate vertical spacing.

```
\G(( *)/(  |__)*\\)\2(  )*\1 *¶
$2 $#3$* $#4$* $1¶

```

Convert the upper triangles into a single centred triangle.
> 2 votes

# Answer
# C (gcc), ~~404~~ 389 bytes

```
#define p(x)putchar(x);
#define F for
W;S;i;a=32;b=47;c=92;f(w,s){W=w,S=s;F(;w;--w){F(i=W+w+s+1;i--;)p(a)p(b)F(i=w*2;i++-2*W;)p(a)p(c)p(10)}F(i=W+s+1;i--;)p(a)p(b)F(i=0;i++-2*W;)p(95)p(c)F(;s--+1;)p(10)F(w=W;w;--w){F(i=w;i--;)p(a)p(b)F(i=w*2;i++-2*W;)p(a)p(c)F(i=w*2+S*2;i--;)p(a)p(b)F(i=w*2;i++-2*W;)p(a)p(c)p(10)}p(b)F(i=0;i++-2*W;)p(95)p(c)F(i=S*2;i--;)p(a)p(b)F(i=0;i++-2*W;)p(95)p(c)}
```

Try it online!

-14 bytes from Rodolvertice

-1 byte by fixing a loop variable decrementation

crossed out ~~404~~ is almost still 404

Ungolfed:

```
#define p(x)putchar(x); // save 7 bytes per putchar call (+24, -182)
#define F for // save 2 bytes per for loop (+14, -28)
int W, S, i; // W is w backup, S is s backup, i is an counter variable;
int a = ' '; // save 1 byte per space printed (+5, -8) (use a instead of 32)
int b = '/'; // save 1 byte per slash printed (+5, -6) (use b instead of 47)
int c = '\\'; // save 1 byte per backslash printed (+5, -6) (use c instead of 92)
// This isn't worth it for '\n' (-5, +3) (10), or '_' (-5, +3) (95)
int f(int w, int s) {
    W = w; // Backup w and s, as we will modify them later,
    S = s; // but will need their original values
    for(; w != 0; --w) { // Top triangle (not the bottom line)
        for(i = W+w+s+1; i != 0; --i) // leading spaces
            putchar(' ');
        putchar('/'); // left side of triangle
        for(i = 2*w; i != 2*W; ++i) // inner spaces
            putchar(' ');
        putchar('\\'); // right side of triangle
        putchar('\n'); // newline
    }
    for(i = W+s+1; i != 0; --i)
        putchar(' '); // leading spaces for the bottom line
    putchar('/'); // left side
    for(i = 0; i != 2*W; ++i)
        putchar('_'); // the bottom line
    putchar('\\'); // right side
    for(; s-- + 1 != 0;)
        putchar('\n'); // newline after the bottom line and S empty lines
    for(w = W; w != 0; --w) { // Bottom triangles
        for(i = w; i != 0; --i)
            putchar(' '); // leading spaces
        putchar('/'); // left of left triangle
        for(i = w*2; i != 2*W; ++i)
            putchar(' '); // inside of left triangle
        putchar('\\'); // right of left triangle
        for(i = w*2+S*2; i != 0; --i)
            putchar(' '); // spaces between left and right triangles
        putchar('/');
        for(i = w*2; i != 2*W; ++i)
            putchar(' '); // inside of right triangle
        putchar('\\'); // right of right triangle
        putchar('\n'); // newline
    }
    putchar('//'); // left of left
    for(i = 0; i != 2*W; ++i)
        putchar('_'); // bottom of left triangle
    putchar('\\'); // right of left
    for(i = S*2; i != 0; --i)
        putchar(' '); // space between triangles
    putchar('/'); // left of right
    for(i = 0; i != 2*W; ++i)
        putchar('_'); // bottom of left triangle
    putchar('\\'); // right of right
}

```
> 2 votes

# Answer
# Jelly, 51 bytes

```
+‘⁶ẋ;Ɱ®Y
‘⁼þ`a”/o"”_o⁶Ṛ;ṚØ^yƊ$€©ż`j€Ḥ⁶ẋƊ}Y,@çj‘⁷ẋƊ}

```

Try it online!
> 1 votes

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


title: Is this a straight flush?

text:
# Question
Title: Is this a straight flush?
Related: Name the poker hand

> A straight flush is a poker hand containing five cards of sequential rank, all of the same suit. As part of a straight flush, an ace can rank either above a king or below a two. An ace can rank either high (e.g. A♥ K♥ Q♥ J♥ 10♥ is an ace-high straight flush) or low (e.g. 5♦ 4♦ 3♦ 2♦ A♦ is a five-high straight flush), but cannot rank both high and low in the same hand (e.g. Q♣ K♣ A♣ 2♣ 3♣ is an ace-high flush, not a straight flush).

**Challenge**

Given `N` cards (in any reasonable format) output a truthy value if a straight flush is contained in the poker hand.

**Input**

* `N` numbers of cards. (In any reasonable format)

There are four suits; hearts, spades, diamonds, and clubs `(H, S, D, C)`.

Each suit has one card for the numbers 2 to 10, plus 4 'picture' cards, Ace, Jack, Queen, and King `(A, J, Q, K)`

*Note: You can take 10 as T*

**Output**

* `Truthy/Falsy` value

**Test case**

```
["AS", "2S", "3S", "4S", "5S"] => true

["3D", "9C", "4S", "KH", "AD", "AC"] => false

["5D", "6D", "7D", "8H", "9D", "10D", "JD"] => false

["JC", "7C", "5D", "8C", "AC", "10C", "9C", "5S"] =>true

[] => false

["AS", "2S", "3S"] => false

["JC", "QC", "KC", "AC", "2C"] => false

[ "2H", "3H", "4H", "5H", "6H", "7H"] => true

```

---

Standard rules apply.

Winning criteria: Shortest code in each lang

# Answer
# Python 2, 95 bytes

```
lambda a:any(set('A234567891JQKA'[i/4:][:5])<={r['HCSD'[i%4]in r]for r in a}for i in range(40))

```

Try it online!

There are 40 possible straight flushes, and this simply checks them all. Chas Brown saved 2 bytes; Jo King saved 4 more.
> 15 votes

# Answer
# , ~~128 126~~ ~~94~~ 91 bytes

```
function(x,r=rle(outer(y<-chartr("J-X","A2-9TJQKAS",LETTERS),y,paste0)%in%x))any(r$l>4&r$v)

```

Try it online!

Original logic shortened considerably by @J.Doe.

Makes a 26 by 26 matrix with mostly nonsense but all the cards (with the Aces repeated at the bottom) contained in rows 10 to 23 of columns 3,4,8 and 24. The matrix is created by concatenating all combinations of the upper case alphabet with letters J through X replaced by A,2-9,T,J,Q,K,A,S via `chartr`. We get C, D, H for free!

The `%in%` flattens the matrix column-wise into a vector. Then see if run-length encoding is greater than 4 for any run of `TRUE` matches.
> 8 votes

# Answer
# JavaScript (ES6), 116 bytes

```
a=>[...'CDHS'].some(s=>a.map(c=>m|=c.match(s)&&2<<"234567891JQKA".search(c[0]),m=0)|(g=k=>k&&1+g(k&k/2))(m|m>>13)>4)

```

Try it online!

### How?

For each suit \\$s\\$, we convert all cards \\$c\\$ of suit \\$s\\$ into a 14-bit bitmask \\$m\\$, duplicate bit #13 (Ace) to bit #0 to handle the *steel wheel* (A,2,3,4,5) and count the number of consecutive bits. If it's greater than 4, we have a straight flush.
> 5 votes

# Answer
# Brachylog, 31 bytes

```
tᵍkᵐ²cᵐ{ps₅~s"A23456789TJQKA"}ᵉ

```

Try it online!

```
 ᵍ                    Group input by
t                     each element's "tail" (i.e. suit)
kᵐ²                   Knife off the suit character from each element in each array
cᵐ                    Concatenate the elements of each suit array into a string
{               }ᵉ    There exists at least one string in that such that
 p                    it has a permutation
 s₅                   which has a substring of length 5
 ~s                   which is also a substring of
 "A23456789JQKA"

```
> 4 votes

# Answer
# Retina 0.8.2, 66 bytes

```
J
11
Q
12
K
13
A
1$%'¶14
\d+(.)
$1$&$*
O`
^
¶
((?(1)\1.|¶.+)){5}\b

```

Try it online! Explanation:

```
J
11
Q
12
K
13

```

Convert the picture cards into their values.

```
A
1$%'¶14

```

`A` can be 1 or 14.

```
\d+(.)
$1$&$*
O`

```

Convert the value to unary, and suffix it so that the cards sort properly.

```
^
¶
((?(1)\1.|¶.+)){5}\b

```

Match 5 cards that increase by 1 each time, and ensure that the last increase was exactly 1.
> 3 votes

# Answer
# Java 10, ~~189~~ ~~167~~ ~~165~~ ~~164~~ ~~160~~ ~~157~~ 156 bytes

```
s->{int i=10;for(;i-->0;)i=s.matches("AKQJT98765432A".substring(i,i+5).replaceAll(".","(?=.*$0\\\\1)").replaceFirst(".1","([HSDC])")+".*")?-2:i;return-1>i;}

```

Takes the input as a single space-delimited String (i.e. `"AS 2S 3S 4S 5S"`).

-22 bytes thanks to *@OlivierGrégoire*.
-1 byte thanks to *@AlexRacer*.

Try it online.

Golfed version of the code that I've used for Project Euler #54, which I primarily did with regexes (for fun and to learn more about regexes). Without regexes it would probably have been better for performance and easier (probably also applies for golfing this answer; will take a look later on).

**Explanation:**

```
s->{                    // Method with String parameter and boolean return-type
  int i=10;for(;i-->0;) //  Loop `i` in the range (10,0]:
    i=s.matches(        //   If the input matches the following regex:
        "AKQJT98765432A".substring(i,i+5)
                        .replaceAll(".","(?=.*$0\\\\1)")
                        .replaceFirst(".1","([HSDC])")
                        //    Five adjacent cards
        +".*")?         //    With optionally zero or more other characters
         -2             //     Set `i` to -2, which also stops the loops at the same time
      :i;               //   Else: leave `i` unchanged to continue
  return-1>i;}          //  Return whether `i` is not -2 (so whether the loop has finished)

```

**Additional regex explanation:**

* `"AKQJT98765432A".substring(i,i+5)` takes five adjacent cards based on `i`
* `.replaceAll(".","(?=.*$0\\\\1)")` replaces each of those cards with `"(?=.*c\\1)"` (where `c` is the card-character)
* `.replaceFirst(".1","([HSDC])")` will then replace the first `\\1` with `([HSDC])`.

I.e. the total regex to check the Straight Flush for cards in the value-range `[9,5]` will become:
`^(?=.*9([HSDC]))(?=.*8\\1)(?=.*7\\1)(?=.*6\\1)(?=.*5\\1).*$`
(NOTE: `String#matches` implicitly adds the trailing/leading `^...$` to check the entire String.) This regex will:

```
^(?=.*9([HSDC]))(?=.*8\\1)(?=.*7\\1)(?=.*6\\1)(?=.*5\\1).*$
^                                                         $ Match the entire string
 (?=           )(?=      )(?=      )(?=      )(?=      )    Do positive lookaheads to check
                                                            each card
    .*             .*        .*        .*        .*         With optional leading characters
                                                            in front of every card
                                                        .*  And any trailing characters at
                                                            the end of the entire hand
      9              8         7         6         5        The five adjacent values
        [HSDC]                                              With a suit
       (      )       \\1       \\1       \\1       \\1     which is the same for all cards

```
> 2 votes

# Answer
# JavaScript (ES6), 106 bytes

```
h=>h.map(([r,s])=>[..."HSDCA23456789TJQKA"].map(c=>i+=c==s?i*15:c==r?d[i]=1:1,i=0),d=[])|/(,1){5}/.test(d)

```

Accepts an array of string representations of cards, replacing `10` with `T`. Try it online!

# Explanation

Iterates over each card and sets a flag in an array of booleans using an index computed from the unique combination of its rank and suit. This array is then stringified to permit matching a pattern of 5 consecutive truthy values.

For example, a hand with a straight flush may produce the following as a substring of the full string representation of the boolean array: `,,,,1,1,1,1,1,,,,`

Because the first rank value (i.e. A) is offset from the start of the string, there will always be empty values preceding all `1`'s in the array, ensuring the string representation will begin with a `,`

```
h =>
    h.map(([r, s]) =>                         // destructure card value, e.g. "JH" => ["J", "H"]
        [..."HSDCA23456789TJQKA"].map(c =>    // mapping accounts for both positions of 'A'
            i +=                              // increment index value
            c == s                            // if found index of suit...
                ? i * 15                      // buffer so that cards from different suits cannot be confused
            : c == r                          // if found index of rank...
                ? d[i] = 1                    // set flag to denote card is in hand
            : 1,
            i = 0
        ),
        d = []
    ) |
    /(,1){5}/.test(d)                         // implicitly converts to string joined with a ,

```
> 2 votes

# Answer
# Clean, ~~145~~ 135 bytes

```
import StdEnv,Data.List
?l=or[isInfixOf(map hd h)['A234567891JQKA']\\a<-l,b<-l,c<-l,d<-l,e<-l,h<-[[a,b,c,d,e]]|tl(nub(map last h))==[]]

```

Try it online!

Simplified:

```
? l                                             // function ? taking argument l
  = or [                                        // is at least one of these true
        isInfixOf (map hd h) ['A234567891JQKA'] // do the first characters of a hand appear in this string, in order
        \\ a <- l                               // loop level 1, assigns `a`
           , b <- l                             // loop level 2, assigns `b`
             , c <- l                           // loop level 3, assigns `c`
               , d <- l                         // loop level 4, assigns `d`
                 , e <- l                       // loop level 5, assigns `e`
                   , h <- [[a,b,c,d,e]]         // trick to assign `h`, because it's cheaper than let .. in ..
        | tl (nub (map last h)) == []           // only take the loop iterations where all the suits are the same
       ]

```
> 1 votes

# Answer
# Japt, 37 bytes

Takes input as a 2D array.

```
"AJQKA"i1Aò2 q)øUñÌòÏÌ¦XÌÃËmÎ¬ú5 á5Ãc

```

Try it

---

## Explanation

```
"AJQKA"                                   :String literal
       i1                                 :Insert at (0-based) index 1
         Aò2                              :  Range [2,10]
             q                            :  Join
              )                           :End insert
               ø                          :Does that string contain any element in the following array?
                U                         :Input
                 ñ                        :Sort
                  Ì                       : By last element (grouping suits together)
                   òÏ                     :Partition between X & Y where
                     Ì                    :  Last element of Y
                      ¦                   :  Does not equal
                       XÌ                 :  Last element of X
                         Ã                :End partition
                          Ë               :Map
                           m              :  Map
                            Î             :   First elements (card values)
                             ¬            :  Join
                              ú5          :  Right pad with spaces to length 5
                                 á5       :  Permutations of length 5
                                   Ã      :End map
                                    c     :Flatten

```
> 1 votes

# Answer
# Jelly, 18 bytes

```
Ṣœc5Uµ13R;1wṪ€ȧEµƇ

```

Try it online!

Actual input format: list (`[..., ...]`) of lists of 2 integers each; the first is an integer in \\$\[1,13\]\\$, for \\$A23456789TJQK\\$ respectively, and the second is in \\$\[1,4\]\\$, for \\$CDHS\\$ respectively. The TIO link accepts input in the format of the test cases.

Output format: empty list as falsy, non-empty list as truthy.
> 0 votes

# Answer
# PHP, 264 bytes

It echos `1` if it is a straight flush and `0` or `null` if not.

If you name the file `1X` then you can save `11 bytes` as you don't need to change `$argv[0]`. Not sure at the moment why the filename can break it.

For some reason the strings `:;<=>` get sorted before the strings `0123456789` by `asort` in TIO even though `:;<=>` have ASCII values 58-62 and `0123456789` have ASCII values 48-57. So if you take the code from the TIO link or below and use PHPTester with the following test suite it works.

```
$argb[0] = [".code.tio", "AS", "2S", "3S", "4S", "5S"]; // => true
$argb[1] = [".code.tio", "3D", "9C", "4S", "KH", "AD", "AC"]; // => false
$argb[2] = [".code.tio", "5D", "6D", "7D", "8H", "9D", "TD", "JD"]; // => false
$argb[3] = [".code.tio", "JC", "7C", "5D", "8C", "AC", "TC", "9C", "5S"]; // => true
$argb[4] = [".code.tio", ]; // => false
$argb[5] = [".code.tio", "AS", "2S", "3S"]; // => false
$argb[6] = [".code.tio", "JC", "QC", "KC", "AC", "2C"]; // => false
$argb[7] = [".code.tio", "TC", "JC", "QC", "KC", "AC", "2C"]; // => true
$argb[8] = [".code.tio", "2H", "3H", "4H", "5H", "6H", "7H"]; // => true

for ($z=0; $z<9;$z++){
    $argv=$argb[$z];
    array_shift($argv);
    unset($a,$b,$c,$d,$e,$f,$g,$h,$i);
    $f=false; // not needed, just removes several notices

    // TIO code here

    echo "<br>";

```

TIO Code

```
for($b=count($a=$argv);$b;){$a[0]='1X';$a[--$b]=strtr($a[$b],'ATJQK','1:;<=');$a[]=($a[$b][0]==1?">".$a[$b][1]:1);}asort($a);foreach($a as$c){$d[$c[1]][]=$c[0];}foreach($d as$e){if(4<$g=count($e)){for($h=0;$g>$i=4+$h;){$f|=(ord($e[$i])-ord($e[$h++])==4);}}}echo$f;

```

Try it online!
> 0 votes

# Answer
# Kotlin, 226 bytes

Used T for 10 so all cards are 2 characters in length.

```
{h:List<String>->val m=List(4){mutableSetOf<Int>()}
for(c in h)m["CDHS".indexOf(c[1])].add("A23456789TJQK".indexOf(c[0]))
var r=0>1
for(b in m){if(b.contains(0))b.add(13)
for(i in 0..9)r=b.containsAll((i..i+4).toList())||r}
r}

```

Try it online!
> 0 votes

# Answer
# Pascal (FPC), ~~223~~ ~~216~~ ~~210~~ 209 bytes

```
var a,b:char;c:set of byte;i:byte;begin repeat readln(a,b);i:=pos(b,'HDC')*14+pos(a,'23456789TJQK');c:=c+[i];if a='A'then c:=c+[i+13]until eof;i:=0;while not([i..i+4]<=c)or(i mod 14>9)do i:=i+1;write(i<52)end.

```

Try it online!

Uses `T` for 10. Input contains 1 card per line.

Now I golfed it so much that I don't know how it works anymore...

## Explanation:

```
var a,b:char; //for reading cards
    c:set of byte; //this set is for remembering which cards are present in the input
                   //14 numbers used for each suit
    i:byte;
begin
  repeat
    readln(a,b);             //read rank into a, suit into b and a newline
    i:=pos(b,'HDC')*14+pos(a,'23456789TJQK');
        //temporary use i to calculate corresponding number for the card
        //pos() gives 0 if b is not found
        //1st pos() is for the group of numbers for that suit, 2nd pos() is for offset
    c:=c+[i];                //include i into set
    if a='A'then c:=c+[i+13] //if rank is A, include the number at the end of group as well
  until eof;
  i:=0;
  while not(
    ([i..i+4]<=c) //if NOT 5 cards in a row are present...
    and           //while the check is started from 10 (T)...
    (i mod 14<10) //(otherwise, it is checking across 2 different suits)
  )do i:=i+1;     //increment i, otherwise stop
  write(i<52) //if i<=51, there is a straight flush starting at the card corresponding to i
              //(if there isn't a straight flush, i stops at 252 due to i..i+4, I don't know why)
end.

```
> 0 votes

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


title: Minimum of last k

text:
# Question
Title: Minimum of last k
Write a function that takes two arguments: a number `k` and a list `l`, and that returns another list `r` such that `r[i] = min(l[i-k+1:i])`.

## Examples

* **Input** k=2, l=1,2,3,4,5,6
* **Ouput** r=1,1,2,3,4,5
* **Input** k=3, l=-1,9,7,-9,8,3,5,0,12,1,2,3,-1,-2,-3
* **Ouput** r=-1,-1,-1,-9,-9,-9,3,0,0,0,1,1,-1,-2,-3

Constraints: **O(len(l))** time complexity. *Shortest code* wins.

# Answer
# R, 75 bytes

```
f=function(k,l){r=l;for(i in 1:length(l));r[i]=min(l[max(1,(i-k+1)):i]);r}

```

Testing:

```
f(3, c(-1,9,7,-9,8,3,5,0,12,1,2,3,-1,-2,-3))
[1] -1 -1 -1 -9 -9 -9  3  0  0  0  1  1 -1 -2 -3

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

```

Not sure how to calculate the complexity of this.
> 1 votes

# Answer
# SmileBASIC, 97 bytes

```
DEF M(K,L)DIM T[0],R[0]FOR I=1TO LEN(L)COPY T,L,MAX(I,K)-K,MIN(I,K)PUSH R,MIN(T)NEXT
RETURN R
END

```

Explanation: This line uses `COPY dest[],source[],start,length` to get part of the list into a temporary array:

```
COPY TEMP,LIST,MAX(I-K,0),MIN(I,K)

```

Example for a list of size 6, with K=3

```
I|start|length
1| 0   | 1
2| 0   | 2
3| 0   | 3
4| 1   | 3
5| 2   | 3
6| 3   | 3

```
> 1 votes

# Answer
# K, 32 bytes

`{|&/',/+((x*!_(#y)%x)+/:!x)_\:|y}`

Translating the symbols to meaning, that is: reverse min over each flattened transpose (firstargument multipliedby enumerate truncate (countof secondargument) dividedby firstargument)add eachright enumerate first argument) cutby eachleft reverse secondargument

It's not as terse as J, as K is a simpler language, but it is still interesting
> 1 votes

# Answer
I come from the future (from this future) and, since I'm learning J, I thought I'd give it a try.

# J, 21 bytes (non-competing)

```
<./"1@([,\$&_@<:@[,])

```

It prefixes the list with (K - 1) infinities, partitions it in overlapping chunks of length K and then computes the minimum of those. That's O(K\*len(L)) if I'm not mistaken but, AFAICT, you need stateful computation to achieve O(len(L)) which isn't very idiomatic in J.

### Usage:

```
   2 <./"1@([,\$&_@<:@[,]) 1 2 3 4 5 6
1 1 2 3 4 5

   3 <./"1@([,\$&_@<:@[,]) _1 9 7 _9 8 3 5 0 12 1 2 3 _1 _2 _3
_1 _1 _1 _9 _9 _9 3 0 0 0 1 1 _1 _2 _3

```
> 0 votes

# Answer
## Matlab, 72 bytes

```
function[r]=f(k,l),for i=1:length(l),r(i)=min(l(max(1,i-k+1):i));end;end

```

Try it Online!
> 0 votes

# Answer
# Haskell, 92 bytes

This is a question asking specifically for a program that runs in O(len(l)) time, yet all the other answers in 7½ years have ignored that constraint. Here’s one that satisfies it.

```
g id
g _ _[]=[]
g h k l|(a,b)<-splitAt(k-1)l=h(scanl1 min a)++g(zipWith min$scanr1 min a)k b

```

Try it online!

### How it works

Split the list into blocks of *k* − 1. Within each block, compute all prefix minima (with a left-to-right scan) and all suffix minima (with a right-to-left scan). Then any sublist of *k* numbers crosses exactly one block boundary, and can therefore be computed as the minimum of a suffix minimum from the first block and a prefix minimum from the second block.
> 0 votes

---
Tags: code-golf, number, restricted-complexity
---


title: Impatient divisibility test

text:
# Question
Title: Impatient divisibility test
Your task is to write a program or function that determines whether a number is divisible by another. The catch is that **it should give an answer as soon as possible**, even if not all digits of the number have been given.

Your program should take an integer *D* ≥ 2 and then a series of digits as input. These represent the digits of another integer *N* ≥ 1, starting at the least significant digit. At the first point that *N* either *must* or *must not* be divisble by *D*, your program should output the appropriate answer and exit. If the end of the input is reached, it should output whether the full *N* is divisible by *D*.

Here is a list of acceptable input formats for *N* (leave a comment if you think something that isn't included should be allowed):

* **Standard input**: digits are given on separate lines; *end of input* is EOF or a special value; *exit* means that the function returns or the program exits.
* **Analog input**: through e.g. keystrokes or ten buttons representing each digit; *end of input* is a special value; *exit* means that the function returns or the program exits.
* **Function with global state**: called repeatedly with successive digits; *end of input* is a special value; *exit* means that the function returns a non-null value. Note that if you use global state, it must be cleared after a value is returned or otherwise reset such that the function works multiple times.
* **Curried function**: returns either another function to be called with the next digit or a value; *end of input* is a special value or calling the function with no argument; *exit* means that the function returns an answer rather than another function.
* **GUI prompt or similar**: displayed repeatedly; *end of input* is "cancel" or equivalent, or a special value; *exit* means that prompts stop appearing.
* **Iterator function**: input is a stateful object or function that returns the next digit when called, *end of input* is an exception or special value; *exit* means that the iterator stops being called.

Input for *D* and the output can be through any acceptable standard method.

Test cases:

```
2;   6               => true
5;   6               => false
20;  0 3             => false
20;  0 4             => true
100; 1               => false
100; 0 0             => true
100; 0 2             => false
4;   2 4             => false
4;   2 5             => true
4;   2 [eof]         => false
4;   4 [eof]         => true
625; 5 5             => false
625; 5 7 2           => false
625; 5 7 3 6         => false
625; 5 7 3 4         => true
7;   9 3 4 [eof]     => false
7;   9 3 4 5 [eof]   => true
140; 0 3             => false
140; 0 4 5 [eof]     => false
140; 0 4 5 1 [eof]   => true
14;  4 5 1 4 [eof]   => false
14;  4 5 1 4 1 [eof] => true

```

# Answer
# JavaScript (ES6), 70 bytes

Input format: **Curried function**

A function that takes the divisor and returns a function that takes each digit or \\$-1\\$ for EOF. The second function returns either \\$0\\$ (false), \\$1\\$ (true) or itself (no answer).

```
p=>(q='',g=(d,t=k=z=!~d||(q=d+q,p))=>k--?g(d,t-=(k+q)%p<1):t?t-z&&g:1)

```

Try it online!

### How?

Given a divisor \\$p\\$ and a dividend \\$q\\$ consisting of \\$n\\$ decimal digits, we compute the following expression for all \\$0 \le k \< p\\$:

$$k\times 10^n+q \pmod p\tag{1}$$

For any \\$x\ge p\\$ there exists \\$m\ge 1\\$ and \\$0 \le k \< p\\$ such that \\$x=mp+k\\$, leading to:

$$x\times 10^n+q \pmod p=\\ (mp+k)\times 10^n+q \pmod p=\\ (mp\times 10^n \pmod p)+ (k\times 10^n+q \pmod p)\pmod p=\\ 0+(k\times 10^n+q \pmod p)\pmod p=\\ k\times 10^n+q \pmod p$$

Therefore, if \\$(1)\\$ is equal to \\$0\\$ for all \\$0 \le k \< p\\$, it will also be equal to \\$0\\$ for any \\$k \ge p\\$ and the answer is *true*.

For the same reason, if \\$(1)\\$ is greater than \\$0\\$ for all \\$0 \le k \< p\\$, the answer is *false*.

If the results of \\$(1)\\$ are mixed, we can't decide yet and need either more digits of \\$q\\$ or the EOF notification.

### Commented

```
p => (                       // p = divisor
  q = '',                    // q = dividend stored as a string, initially empty
  g = (                      // g() = curried function taking:
    d,                       //   d = next digit
    t =                      //   t = number of iterations yielding a non-zero value
    k =                      //   k = total number of iterations to process
    z =                      //   z = copy of k
      !~d ||                 //   if d == -1 (meaning EOF), use only 1 iteration
                             //   so that we simply test the current value of q
      (q = d + q, p)         //   otherwise, prepend d to q and use p iterations
  ) =>                       //
    k-- ?                    //   decrement k; if it was not equal to zero:
      g(                     //     do a recursive call to g():
        d,                   //       pass the current value of d (will be ignored anyway)
        t -= (k + q) % p < 1 //       test (k + q) % p and update t accordingly
      )                      //     end of recursive call
    :                        //   else:
      t ?                    //     if t is greater than 0:
        t - z && g           //       return 0 if t == z, or g otherwise
      :                      //     else:
        1                    //       return 1
)                            //

```
> 9 votes

# Answer
## Batch, ~~177~~ 169 bytes

```
@set n=
@set g=1
:l
@set/ps=
@if %s%==- goto g
@set n=%s%%n%
@set/ae=%1/g,g*=2-e%%2,g*=1+4*!(e%%5),r=n%%g
@if %g% neq %1 if %r%==0 goto l
:g
@cmd/cset/a!(n%%%1)

```

Takes `d` as a command-line parameter and reads digits of `n` on separate lines with `-` as the EOF marker. Outputs `1` for divisible, `0` if not. Explanation:

```
@set n=

```

Initialise `n` to the empty string.

```
@set g=1

```

`g` is `gcd(d, 10**len(n))`

```
:l

```

Begin a loop reading digits.

```
@set/ps=

```

Read the next digit.

```
@if %s%==- goto g

```

Stop processing at EOF.

```
@set n=%s%%n%

```

Prepend the next digit to `n`.

```
@set/ae=%1/g,g*=2-e%%2,g*=1+4*!(e%%5),r=n%%g

```

Update `g` now that `len(n)` has increased and calculate `n%g`.

```
@if %g% neq %1 if %r%==0 goto l

```

If `r` is non-zero then the `d` definitely does not divide `n`, because `g`, a factor of `d`, does not. If `r` is zero then we only know whether `d` divides `n` if `g` equals `d`, so if it isn't, continue the loop.

```
:g

```

Break out of the digit-reading loop here on EOF.

```
@cmd/cset/a!(n%%%1)

```

Calculate and implicitly output the result.
> 2 votes

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


title: Square-Random-Symmetrical

text:
# Question
Title: Square-Random-Symmetrical
## Challenge

Write a program or a function that returns or prints a square-random-symmetrical matrix.

---

## Input

**N**: The size of the matrix i.e `6 x 6`

---

## Output

The matrix. You can either print it, return it as string (with the newlines) or as a list/array of lists/arrays.

---

## Rules

1. You need to use at least `N` different characters, where `N` is the size of the square matrix (input). Since we 're using only letter \[a, z\]\[A, Z\] and digits \[0, 9\] (and only 1 digit at the time) you can assume that `N < 27` and `N > 2`, that is because at `N <= 2` you can't have both letters and digits. Last but not least, every letter/digit must have non-zero probability of occurring (uniform distribution is not a necessity). However, the result must have at least `N` different letter/digits.
2. The matrix has to be both horizontally and vertically symmetrical.
3. Exactly 2 rows and 2 columns must contain strictly one single-digit number (it's position should be random as well). The rest of rows/cols will contain only letters. Consider letters as \[a, z\] and \[A, Z\] and of course single-digit numbers as \[0, 9\].
4. Just to be easier, you can assume that the case of the letters doesn't matter, as long as the cases are symmetrical which means: `a=A, b=B, etc`.
5. Every possible output must have a non-zero probability of occurring. The random distribution doesn't need to be uniform.

---

## Example

**Input**: 8

**Output**:

```
c r p s s p r c
r k o z z o k r
u t 2 a a 2 t u
y n q z z q n y
y n q z z q n y
u t 2 a a 2 t u
r k o z z o k r
c r p s s p r c

```

# Answer
> 4 votes
# Charcoal, 30 bytes

```
ＮθＥ⊘⊕θ⭆⊘⊕θ‽βＪ‽⊘θ‽⊘θＩ‽χ‖ＯＯ→↓﹪θ²

```

Try it online! Link is to verbose version of code. If `n` is always even, then for 23 bytes:

```
ＮθＥ⊘θ⭆⊘θ‽βＪ‽⊘θ‽⊘θＩ‽χ‖Ｃ¬

```

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

```
Ｎθ

```

Input \\$ n \\$.

```
Ｅ⊘θ⭆⊘θ‽β

```

Create an \\$ \frac n 2 \\$ by \\$ \frac n 2 \\$ array of random lowercase letters. This prints implicitly as a square.

```
Ｊ‽⊘θ‽⊘θ

```

Jump to a random position in the square.

```
Ｉ‽χ

```

Print a random digit.

```
‖Ｃ¬

```

Reflect horizontally and vertically to complete the matrix.

# Answer
> 16 votes
# , ~~124~~ 118 bytes

```
function(n,i=(n+1)/2,j=n%/%2,m="[<-"(matrix(-letters,i,i),j-1,j-1,0:9-1))cbind(y<-rbind(m,m[j:1,]),y[,j:1])
`-`=sample

```

Try it online!

In R, things that look like operators are just functions that get special treatment from the parser.

If you redefine an operator (like `-`) to be some other function, it keeps the special treatment from the parser. Since `-` is both prefix and infix, and I need to call the `sample` function with both one and two arguments, I can use

```
`-`=sample

```

to get what I want.

So the code `-letters` is translated to `sample(letters)`, which randomly shuffles the `letters` built-in. But `j-1` is translated to `sample(j,1)`, which randomly samples `1` item from the vector `1:j`.

(This behaviour of the `sample` function depending on the number of parameters and what the first parameter is, is a huge pain in the butt in production code, so I'm happy to find a great use of its perverse nature here!)

Otherwise the code just makes the top left quadrant of the required result, replaces a random element (the `j-1`,`j-1` bit) with a random digit (the `0:9-1` bit), and folds it out for the required symmetry. The `i` and the `j` are needed to deal with the even and odd cases.

# Answer
> 6 votes
# Python3, 287 bytes

My first try at golfing something here; I'm sure someone can do far better:

```
import random as rn, math as m
n=int(input())
x,o=m.ceil(n/2),n%2
c=x-1-o
f=lambda l,n: l.extend((l[::-1], l[:-1][::-1])[o])
q=[rn.sample([chr(i) for i in range(97, 123)],x) for y in range(x)]
q[rn.randint(0,c)][rn.randint(0,c)] = rn.randint(0,9)
for r in q:
    f(r, n)
f(q, n)
print(q)

```

Try it Online!

Thanks to HyperNeurtrino, Ourous and Heiteria this shrunk down to 193 bytes (see comments). However, TFeld correctly pointed out that multiple calls to `sample` aren't guaranteeing at least `N` different characters.

That stuff in mind, try this new version that should guarantee at least `N` different characters per run.

# Python3, ~~265~~ 260 bytes, at least `N` distinct characters

```
from random import *
n=int(input())
x=-(-n//2)
o=n%2
c=x+~o
i=randint
u=[chr(j+97)for j in range(26)]
z,q=u[:],[]
for y in [1]*x:
  shuffle(z)
  q+=[z[:x]]
  z=z[x:] if len(z[x:])>=x else u[:]
q[i(0,c)][i(0,c)]=i(0,9)
for r in[q]+q:r.extend(r[~o::-1])
print(q)

```

Try it online!

# Answer
> 4 votes
# APL (Dyalog Classic), ~~45~~ ~~44~~ ~~43~~ 40 bytes

thanks @Adám for -1 byte

```
26{(⎕a,⍺⍴⎕d)[⌈∘⊖⍨⌈∘⌽⍨⍺+@(?⊂⌊⍵÷2)?⍵⍴⍺]},⍨

```

Try it online!

uses  (max) of the matrix with its reflections to make it symmetric, so it's biased towards the latter part of the alphabet

the digit is chosen uniformly from 0...25 mod 10, so it has a small bias to lower values

# Answer
> 3 votes
# Japt, 31 bytes (Fixed digit position)

```
;
/2 c
VÆVÆBö}ÃgT0@Mq9Ã®êUvÃêUv

```

Try it online!

---

# Japt, 41 bytes (Random digit position)

```
;
/2 c
VÆVÆBö}ÃgMq´VÉ ,MqVÉ @Mq9Ã®êUvÃêUv

```

Try it online!

---

**Explanation**

```
;                               Change to new vars
/2 c                            set implicit var V equal to implicit var U / 2 rounded up
VÆVÆBö}ÃgT0@Mq9Ã®êUvÃêUv        Main function

VÆ                              Range from 0 to V and map
  VÆ                            Range from 0 to V and map
    Bö}Ã                        return random char from alphabet
        gT0@                    map upper-left corner
            Mq9Ã                return random number
                ®êUv            horizontal mirror
                    êUv         vertical mirror

```

# Answer
> 2 votes
# Python 2, 259 bytes

```
from random import*
n=input();c=choice;r=range
w,W=n/2,-~n/2
o=n%2
A=map(chr,r(97,123))
l=[c(r(10))]+sample(A,n)+[c(A)for _ in' '*w*w]
l,e=l[:w*w],l[w*w:W*W]
shuffle(l)
l=[l[w*i:w*-~i]+e[i:i+1]for i in range(w)]+[e[-W:]]
for r in l+l[~o::-1]:print r+r[~o::-1]

```

Try it online!

# Answer
> 2 votes
# 05AB1E, ~~29~~ ~~40~~ 38 bytes

```
A.rs;ò©n∍9ÝΩ®DnαLʒ®%Ā}<Ωǝ®ô»¹Éi.º.∊ëº∊

```

+11 bytes to fix the digit being at a random position while still keeping rule 3 in mind for odd inputs..
-2 bytes thanks to *@MagicOctopusUrn*, changing `îï` to `ò` and changing the position of the `»`.

Try it online of verify some more test cases.

Old (**~~29~~ 27 bytes**) answer where the digit positions where always in the corners:

```
A.rs;ò©n∍¦9ÝΩì®ô»¹Éi.º.∊ëº∊

```

Try it online or verify some more test cases.

**Explanation:**

```
A           # Take the lowercase alphabet
 .r         # Randomly shuffle it
            #  i.e. "abcdefghijklmnopqrstuvwxyz" → "uovqxrcijfgyzlbpmhatnkwsed"
s           # Swap so the (implicit) input is at the top of the stack
 ;          # Halve the input
            #  i.e. 7 → 3.5
  ò         # Bankers rounding to the nearest integer
            #  i.e. 3.5 → 4
   ©        # And save this number in the register
    n       # Take its square
            #  i.e. 4 → 16
     ∍      # Shorten the shuffled alphabet to that length
            #  i.e. "uovqxrcijfgyzlbpmhatnkwsed" and 16 → "uovqxrcijfgyzlbp"
9ÝΩ         # Take a random digit in the range [0,9]
            #  i.e. 3
   ®Dnα     # Take the difference between the saved number and its square:
            #  i.e. 4 and 16 → 12
       L    # Create a list in the range [1,n]
            #  i.e. 12 → [1,2,3,4,5,6,7,8,9,10,11,12]
ʒ   }       # Filter this list by:
 ®%Ā        #  Remove any number that's divisible by the number we've saved
            #   i.e. [1,2,3,4,5,6,7,8,9,10,11,12] and 4 → [1,2,3,5,6,7,9,10,11]
     <      # Decrease each by 1 (to make it 0-indexed)
            #  i.e. [1,2,3,5,6,7,9,10,11] → [0,1,2,3,5,6,7,9,10]
      Ω     # Take a random item from this list
            #  i.e. [0,1,2,3,5,6,7,9,10] → 6
       ǝ    # Replace the character at this (0-indexed) position with the digit
            #  i.e. "uovqxrcijfgyzlbp" and 3 and 6 → "uovqxr3ijfgyzlbp"
®ô          # Split the string into parts of length equal to the number we've saved
            #  i.e. "uovqxr3ijfgyzlbp" and 4 → ["uovq","xr3i","jfgy","zlbp"]
  »         # Join them by new-lines (this is done implicitly in the legacy version)
            #  i.e. ["uovq","xr3i","jfgy","zlbp"] → "uovq\nxr3i\njfgy\nzlbp"
   ¹Éi      # If the input is odd:
            #  i.e. 7 → 1 (truthy)
      .º    # Intersect mirror the individual items
            #  i.e. "uovq\nxr3i\njfgy\nzlbp"
            #   → "uovqvou\nxr3i3rx\njfgygfj\nzlbpblz"
        .∊  # And intersect vertically mirror the whole thing
            #  i.e. "uovqvou\nxr3i3rx\njfgygfj\nzlbpblz"
            #   → "uovqvou\nxr3i3rx\njfgygfj\nzlbpblz\njfgygfj\nxr3i3rx\nuovqvou"
  ë         # Else (input was even):
   º∊       #  Do the same, but with non-intersecting mirrors

```

# Answer
> 2 votes
# C (gcc), ~~198~~ ~~197~~ 196 bytes

Saved 2 bytes thanks to ceilingcat.

```
#define A(x)(x<n/2?x:n-1-x)
#define R rand()
S(n,x,y){int s[x=n*n];for(srand(s),y=R;x;)s[x]=97+(--x*31+y)%71%26;y=n/2;for(s[R%y+n*(R%y)]=48+R%10;x<n*n;++x%n||puts(""))putchar(s[A(x%n)+A(x/n)*n]);}

```

Try it online!

Explanation:

```
// Coordinate conversion for symmetry
#define A (x) (x < n / 2 ? x : n - 1 - x)
// Get a random and seed
#define R rand()

S (n, x, y)
{
   // the array to store matrix values (x is the array size)
   // Note that we do not need the whole array, only its first quarter
   int s[x = n * n];

   // iterate n*n-1 times until x is zero
   for (srand(s), y = R; x;)
       // and fill the array with pseudo-random sequence of letters
       s[x] = 97 + (--x * 31 + y) % 71 % 26;

   // this is the max. coordinate of the matrix element where a digit may occur
   y = n / 2;

   // drop a random digit there
   s[R % y + n * (R % y)] = 48 + R % 10;

   // Now we output the result. Note that x is zero here
   for (;
       x < n * n; // iterate n*n times
       ++x % n || puts ("") // on each step increase x and output newline if needed
       )
       // output the character from the array
       putchar (s[A (x % n) + A (x / n) * n]);
}

```

# Answer
> 1 votes
# Clean, ~~346~~ 312 bytes

*will golf more tomorrow*

```
import StdEnv,Data.List,Math.Random,System.Time,System._Unsafe
$n#q=twice(transpose o\q=zipWith((++)o reverse o drop(n-n/2*2))q q)[[(['a'..'z']++['0'..'9'])!!(c rem 36)\\c<-genRandInt(toInt(accUnsafe(time)))]%(i*n/2,i*n/2+(n-1)/2)\\i<-[1..(n+1)/2]]
|length(nub(flatten q))>=n&&sum[1\\c<-q|any isDigit c]==2=q= $n

```

Try it online!

# Answer
> 1 votes
# JavaScript (ES6), ~~213~~ ~~209~~ 206 bytes

```
n=>(a=[],F=(x=y=d=c=0,R=k=>Math.random()*k|0,g=y=>(r=a[y]=a[y]||[])[x]=r[n+~x]=v.toString(36))=>y<n/2?F(g(y,R[v=R(m=~-n/2)<!d&x<m&y<m?R(d=10):R(26)+10]=R[v]||++c,g(n+~y))&&++x<n/2?x:+!++y,R):!d|c<n?F():a)()

```

Try it online!

### Commented

```
n => (                             // n = input
  a = [],                          // a[][] = output matrix
  F = (                            // F = main recursive function taking:
    x = y =                        //   (x, y) = current coordinates
    d = c = 0,                     //   d = digit flag; c = distinct character counter
    R = k =>                       //   R() = helper function to get a random value in [0,k[
      Math.random() * k | 0,       //         also used to store characters
    g = y =>                       //   g() = helper function to update the matrix
      (r = a[y] = a[y] || [])[x]   //         with horizontal symmetry
      = r[n + ~x] = v.toString(36) //         using the base-36 representation of v
  ) =>                             //
    y < n / 2 ?                    // if we haven't reached the middle row(s) of the matrix:
      F(                           //   do a recursive call to F():
        g(                         //     invoke g() ...
          y,                       //       ... on the current row
          R[v =                    //       compute v = next value to be inserted
            R(m = ~-n/2) < !d &    //       we may insert a digit if no digit has been
            x < m &                //       inserted so far and the current coordinates are
            y < m ?                //       compatible: 2 distinct rows / 2 distinct columns
              R(d = 10)            //         if so, pick v in [0, 9] and update d
            :                      //       else:
              R(26) + 10           //         pick v in [10, 35] for a letter
          ] = R[v] || ++c,         //       set this character as used; update c accordingly
          g(n + ~y)                //       invoke g() on the mirror row
        ) &&                       //     end of outer call to g()
        ++x < n / 2 ?              //     if we haven't reached the middle column(s):
          x                        //       use x + 1
        :                          //     else
          +!++y,                   //       increment y and reset x to 0
        R                          //     explicitly pass R, as it is used for storage
      )                            //   end of recursive call to F()
    :                              // else:
      !d | c < n ? F() : a         //   either return the matrix or try again if it's invalid
)()                                // initial call to F()

```

# Answer
> 1 votes
# Python 3, 197 bytes

**As mentioned by @Emigna, doesn't work for odd values of `N` (I didn't understand the question properly)**

```
from random import*
def m(N):M=N//2;E=reversed;R=range;B=[randint(48,57),*(sample(R(97,123),N)*N)][:M*M];shuffle(B);r=R(M);m=[k+[*E(k)]for k in[[chr(B.pop())for i in r]for j in r]];m+=E(m);return m

```

Try it online!

I do think the calls to `randint()` \+ `sample()` \+ `shuffle()` are too much, and getting rid of in-place shuffling would be great :)

I'm pretty sure this part (that selects the letters & digit) could be golfed a bit more.

# Answer
> 1 votes
# **Python 2/Python 3, 227 bytes**

```
from random import*
def m(N):n=N-N//2;r=range;C=choice;c=n*[chr(i+97)for i in r(26)];shuffle(c);c[C([i for i in r(n*(N-n))if(i+1)%n+1-N%2])]=`C(r(10))`;R=[c[i*n:i*n+n]+c[i*n:i*n+n-N%2][::-1]for i in r(n)];return R+R[::-1][N%2:]

```

ungolfing a bit:

```
from random import * # get 'choice' and 'shuffle'
def matrix(N):
    n = ceil(N/2) # get the size of the base block
    # get a shuffleable lowercase alphabet
    c = [chr(i+97)for i in range(26)]
    c = n*c # make it large enough to fill the base-block
    shuffle(c) # randomize it
    digit = choice('1234567890') # get random digit string
    ## this is only needed as to prevent uneven side-length matrices
    #  from having centerline digits.
    allowed_indices = [i for i in range( # get all allowed indices
        n*(N-n)) # skip those, that are in an unmirrored center-line
        if(i+1)%n  # only use those that are not in the center column
                 +1-N%2] # exept if there is no center column
    index = choice(allowed_indices) # get random index
    c[index]=digit # replace one field at random with a random digit
    ##
    R=[]
    for i in range(n):
        r = c[i*n:i*n+n] # chop to chunks sized fit for the base block
        R.append(r+r[::-1][N%2:]) # mirror skipping the center line
    return R+R[::-1][N%2:] # mirror skipping the center line and return

```

Older, *almost* correct versions below:

**Python2, Python3, 161 bytes**

```
from random import *
N=26
n=N-N//2
c=[chr(i+97)for i in range(26)]
R=[ r+r[::-1][N%2:]for r in[(shuffle(c),c[:n])[1]for i in range(n)]]
R+=R[::-1][N%2:]
print(R)

```

It seems N differing elements is only *almost* guarranteed.

**Python 2/Python 3, 170 bytes**

```
from random import*
def m(N):n=N-N//2;r=range;c=n*[chr(i+97)for i in r(26)][:n*n];shuffle(c);R=[_+_[::-1][N%2:]for _ in[c[i*n:i*n+n]for i in r(n)]];return R+R[::-1][N%2:]

```

It seems I forgot rule 3. Also somehow the \[:n\*n\] slipped in.

# Answer
> 1 votes
# Python 2, ~~275~~ 266 bytes

```
from random import*
def f(n):
 R=range;C=choice;A=map(chr,R(97,123));b=N=n-n/2;c=`C(R(10))`;s=[c]+sample(A,n-1)+[C(A)for i in R(N*N-n)]
 while b:shuffle(s);i=s.index(c);b=n%2>(i<N*N-N>N-1>i%N)
 a=[r+r[~(n%2)::-1]for r in[s[i::N]for i in R(N)]];return a+a[~(n%2)::-1]

```

Try it online!

Returns the array as a list of lists of characters. To satisfy Rule 1, we set up a pool of characters:

```
s = [c]                        # the unique digit...
     + sample(A,n-1)           # then sample without replacement `n-1` chars in a-z,
                               # so we have `n` distinct chars
     + [C(A)for i in R(N*N-n)] # and fill out the rest with any in a-z

```

The next tricky bit is rule 3: there must be *exactly 2* columns and rows having a digit; this means for `n` odd, that the chosen digit may not appear in the middle column or middle row. Since we construct the array using a twice reflected square sub array `s`, that is accomplished here by using:

```
while b:            # to save a couple bytes, `b` is initialized
                    # to `N`, which is greater than 0.
    shuffle(s)      # shuffle at least once...
    i = s.index(c)  # c is the unique digit used
    b = n%2
             >      # if n is even, 0>(any boolean) will be false,
                    # so exit the loop; otherwise n odd, and we are
                    # evaluating '1 > some boolean', which is equivalent
                    # to 'not (some boolean)'
         (i<N*N-N   # i is not the last column of s...
             >      # shortcut for ' and ', since N*N-N is always > N-1
          N-1>i%N)  # is not the last row of s

```

i.e., shuffle at least once; and then, if `n` is odd, keep looping if the digit is in the last column or the last row of `s`.

# Answer
> 1 votes
# Pyth, 48 bytes

```
L+b_<b/Q2JmO/Q2 2jy.eyXWqhJkbeJOT<csm.SGQK.EcQ2K

```

Try it out online here.

The program is in 3 parts - definition of palindromisation function, choosing location of numeric, and main function.

```
Implicit: Q=eval(input()), T=10, G=lower case alphabet

L+b_<b/Q2   Palindromisation function
L           Define a function, y(b)
      /Q2   Half input number, rounding down
    <b      Take that many elements from the start of the sequence
   _        Reverse them
 +b         Prepend the unaltered sequence

JmO/Q2 2   Choose numeric location
  O/Q2     Choose a random number between 0 and half input number
 m     2   Do the above twice, wrap in array
J          Assign to variable J

jy.eyXWqhJkbeJOT<csm.SGQK.EcQ2K   Main function
                           cQ2    Divide input number by 2
                         .E       Round up
                        K         Assign the above to K
                    .SG           Shuffle the alphabet
                  sm   Q          Do the above Q times, concatenate
                 c      K         Chop the above into segments of length K
                <             K   Take the first K of the above
  .e                              Map (element, index) as (b,k) using:
       qhJk                         Does k equal first element of J?
      W                             If so...
     X     b                          Replace in b...
            eJ                        ...at position <last element of J>...
              OT                      ...a random int less than 10
                                    Otherwise, b without replacement
    y                               Apply palindromisation to the result of the above
 y                                Palindromise the set of lines
j                                 Join on newlines, implicit print

```

Using several shuffled alphabets should ensure that the number of unique characters is always more then the input number.

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


# Question
Title: Trump needs your help to stop the Starman!
A man from the stars has come to Earth! Luckily the president of the United States, Donald Trump, has an infinity-sided die. Using this die, he can conjure up a number which *you*, the mayor of Podunk, must use to determine who should be sent to stop the invader! But be careful, you can only send a limited amount of bytes on the back of your frog!

Given a user input (which will be a positive integer), you must return a string depending on what category the number is in.

* If the number is a **Fibonacci number**, you must output ***Ness***.
* If the number is a **Lucas number**, you must output ***Lucas***.
* If the number is *both* a **Lucas number** and a **Fibonacci number**, you must output ***Travis***.
* If the number is *neither* a a **Lucas number** nor a **Fibonacci number**, you must output ***Pippi***.

## Examples

Here are a bunch of test cases:

```
1 => Travis
2 => Travis
3 => Travis
4 => Lucas
5 => Ness
6 => Pippi
7 => Lucas
8 => Ness
610 => Ness
722 => Pippi
843 => Lucas

```

## Rules

* This is , the shortest answer in bytes wins.
* You program may be a full program or a(n anonymous) function.

## Bonuses

There are a couple bonuses that you can use to help your frog get the data to President Trump faster:

* **For `-15` bytes:** If the input number is `2016`, you must output `Trump`, as he is at the peak of his presidency.

# Answer
# Pyth, 59 - 15 = 44 bytes

*or 42 bytes after a bug was fixed*

```
&Qr@c."av�a�(s��kW�С��"\b?q2016Q4/hMst*2.uL,eNsNQ_BS2Q4

```

Hexdump:

```
0000000: 2651 7240 632e 2261 7601 c061 15dc 2873  &Qr@c."av..a..(s
0000010: fde0 6b57 8bd0 a1ed ed0f 225c 623f 7132  ..kW......"\b?q2
0000020: 3031 3651 342f 684d 7374 2a32 2e75 4c2c  016Q4/hMst*2.uL,
0000030: 654e 734e 515f 4253 3251 34              eNsNQ_BS2Q4

```

The first two characters (`&Q`) are necessary because of a Pyth parsing bug that makes `Q` after `."` fail. Fix has been applied. If the post-bugfix interpreter is allowed, -2 bytes.

---

Without unreadable string compression:

# Pyth, 63 - 15 = 48 bytes

*49 bytes without Trump*

```
@c"Pippi Ness Lucas Travis Trump")?nQ2016/hMst*2.uL,eNsNQ_BS2Q4

```

Test Suite

Pretty straightforward, just generate the sequences, duplicate one and check for membership.

Sequences are generated by starting with `[1, 2]` and `[2, 1]`, and then applying the fibonacci rule.
> 5 votes

# Answer
# Julia, ~~146~~ ~~142~~ ~~121~~ 120 bytes

```
n->split("Pippi Lucas Ness Travis")[2any(isinteger,sqrt([5n^2+4,5n^2-4]))+(n∈[2;[(g=golden)^i+(-g)^-i for i=1:n]])+1]

```

This creates an unnamed function that returns a boolean. To call it, give it a name, e.g. `f=n->...`.

Ungolfed:

```
function trump(n::Integer)
    # Determine if n is a Fibonacci number by checking whether
    # 5n^2 ± 4 is a perfect square
    F = any(isinteger, sqrt([5n^2 + 4, 5n^2 - 4]))

    # Determine if n is a Lucas number by generating Lucas
    # numbers and testing for membership
    # golden is a built-in constant containing the golden ratio
    L = n ∈ [2; [golden^i + (-golden)^-i for i = 1:n]]

    # Select the appropriate Earthbound charater using array
    # indexing on a string split into an array on spaces
    return split("Pippi Lucas Ness Travis")[2F+L+1]
end

```

Fixed an issue and saved 7 bytes thanks to Glen O!
> 8 votes

# Answer
# Mathematica ~~143~~ 156 - 15 (bonus) = 141 bytes

With 2 bytes saved thanks to LegionMammal978.

```
t_~g~l_:=(r=1<0;n=1;While[(z=l@n)<=t,If[z==t,r=1>0];n++];r);a=g[k=Input[],LucasL];
b=k~g~Fibonacci;Which[k==2016,Trump,a&&b,Travis,a,Lucas,b,Ness,2<3,Pippi]

```
> 7 votes

# Answer
# Mathematica, ~~92~~ 87 bytes

Inspired by Sp3000's answer.

```
Travis[Ness,Lucas,Pippi][[{2,1}.Product[Abs@Sign[{Fibonacci@n,LucasL@n}-#],{n,0,2#}]]]&

```
> 7 votes

# Answer
## Python 2, 107

```
f=lambda i,n=input():abs(5*n*n+i)**.5%1>0
print["Travis","Lucas","Ness","Pippi"][f(4)*f(-4)+2*f(20)*f(-20)]

```

The key is two purely arithmetical checks for Fibonacci and Lucas numbers:

* `n` is a Fibonacci number exactly if `5*n*n+4` or `5*n*n-4` is a perfect square
* `n` is a Lucas number exactly if `5*n*n+20` or `5*n*n-20` is a perfect square

This site has proof sketches.

So, the output depends on the values of `5*n*n+i` for `i` in `{4,-4,20,-20}`. The function `f` tests a value of `i`, by checking if the corresponding value *does not* have a whole-number square root The `abs` is there just to avoid an error of taking the root of a negative for `n=1, i=-20`.

The function `f` takes the value of the number `n` to test from STDIN. Python only evaluates this once, not once per function call.

Whether the number is not Fibonacci is evaluated as `f(4)*f(-4)` using the implicit boolean to number conversion and similarly for not Lucas, and the corresponding string is taken. If trailing spaces were allowed, string interleaving would be shorter.
> 5 votes

# Answer
## Python 2, 117 bytes

```
F=[1]
L=[2,1]
n=input()
exec 2*n*"F,L=L+[sum(L[-2:])],F;"
print["Pippi","Lucas","Ness","Travis"][(n in F)*2+(n in L)]

```

For the string list, `"Pippi Lucas Ness Travis".split()` is the same length.
> 4 votes

# Answer
## CJam, ~~58~~ ~~55~~ 54 bytes

```
ri5Zbe!f{1${_-2>:++}*&!}2b"Travis Ness Lucas Pippi"S/=

```

Naïve approach of generating the Fibonacci and Lucas numbers then counting occurences in both, converting to binary, and picking the appropriate string.

Try it online.
> 3 votes

# Answer
## Perl, ~~133~~ ~~(146-15=)131~~ ~~(144-15=)129~~ (136-15=)121 bytes

+1 byte for the `-n` flag.

```
$a=$d=1;$b=$c=2;$f+=$_==$a,$l+=$_==$c,($a,$b,$c,$d)=($b,$a+$b,$d,$c+$d)while$a<$_*9;say$_-2016?(Pippi,Ness,Lucas,Travis)[$f+$l*2]:Trump

```

With newlines after semicolons, for readability:

```
$a=$d=1;$b=$c=2;
$f+=$_==$a,$l+=$_==$c,($a,$b,$c,$d)=($b,$a+$b,$d,$c+$d)while$a<$_*9;
say$_-2016?(Pippi,Ness,Lucas,Travis)[$f+$l*2]:Trump

```

Demo:

```
llama@llama:...code/perl/ppcg64476trump$ for x in 1 2 3 4 5 6 7 8 610 722 843 2016; do echo -n "$x => "; echo $x | perl -n trump.pl; done
1 => Travis
2 => Travis
3 => Travis
4 => Lucas
5 => Ness
6 => Pippi
7 => Lucas
8 => Ness
610 => Ness
722 => Pippi
843 => Lucas
2016 => Trump

```

Tricks:

* ~~You might be wondering why my variables are named `$a`, `$b`, `$%`, and `$d`. That is an excellent question! In fact, it allows me to save a byte.~~

~~```
(stuff) ... ,$l+=$_==$%while$a<$_

```
is one byte shorter than<br>```
(stuff) ... ,$l+=$_==$c while $a<$_

```~~

This no longer applies because I golfed my code by rearranging things, causing the variable name change to no longer save bytes. I changed it back so that variable names make sense again.
* ~~`$_-2?$f+$l*2:3` is mildly interesting. Basically, I had to special-case `2` for Lucas numbers because my program checks whether a number is a Lucas number *after* "updating" the Fibonacci and Lucas numbers. So `2` was considered a not-Lucas number. `$_-2?foo:bar` is a char shorter than `$_==2?bar:foo`. Same thing is used for the `2016` test.~~

This is also no longer true because I was able to restructure the program to not require special-casing `2`. But I still use `$_-2016?stuff:Trump` instead of `$_==2016?Trump:stuff`, which is one byte longer.
* Speaking of which, you may be wondering how I did this restructuring. I just made the program do 9 times more iterations than necessary, which only costs 2 bytes (`*9`) but allows me to make assumptions elsewhere that help golf stuff down.
* Because variables default to zero,

```
$f+=$_==$a

```

is shorter than

```
$f=1if$_==$a

```
* Perl supports barewords, so I don't have to quote any of my strings (\o/).
> 3 votes

# Answer
# Seriously, 69 bytes

```
,;;r`;F@2+F+`M2@q@#"%d="%£MΣ@f0≤2*+["Pippi","Lucas","Ness","Travis"]E

```

Before this challenge, Seriously had the builtin `f` (index in Fibonacci numbers, -1 if not a Fibonacci number)... but not index in a list or "is in list"! (It's since been added as `í`.)

As a result, this is what I spend finding if the input is a Fibonacci number:

```
,                              f0≤

```

This is what I spend generating a list of Lucas numbers:

```
  ;r`;F@2+F+`M2@q

```

And this is what I spend finding if the input is in the list of Lucas numbers:

```
 ;                @#":%d:="%£MΣ

```

That's a string being formatted using Python's % notation into something like `:610:=`, and converted to a function, which is then mapped over the array and summed. (The Lucas numbers are unique, so the sum is always 0 or 1.)

Thanks to @Mego for that last bit with the string formatting.
> 2 votes

# Answer
# Julia, ~~101~~ 100 bytes

```
n->split("Pippi Lucas Ness Travis")[[2;1]⋅(sum(i->[i[];trace(i)].==n,Any[[1 1;1 0]].^(0:n)).>0)+1]

```

Ungolfed:

```
function f(n)
  k=Any[[1 1;1 0]].^(0:n) # Produces characteristic matrices of Fibonacci
                          # numbers from 0 to n
  F=sum(i->i[]==n,k)      # Check if n is a Fibonacci number by checking
                          # the first value in each matrix for n
  L=sum(i->trace(i)==n,k) # Check if n is a Lucas number by checking
                          # the trace of each matrix for n
  I=[2;1]⋅[F;L]+1         # Calculate 2F+L+1, which is the index for the next step
  S=split("Pippi Lucas Ness Travis") # Creates array with four strings
                          # saves a byte compared with directly creating array
  return S[I]
      # This uses the above calculations to determine which of the four to return
end

```
> 2 votes

# Answer
# Octave, 93 bytes

```
@(n){'Pippi','Lucas','Ness','Travis'}{(1:2)*any(~rem(real(sqrt(5*n^2+[-20,-4;20,4])),1)).'+1}

```

This approach is similar to my MATLAB answer with the exception that Octave allows you to index directly into a fresh array:

```
{'a', 'b', 'c'}{2}    %// b

```
> 2 votes

# Answer
# MATL, ~~57~~ ~~55~~ ~~54~~ (67-15) = 52 bytes

```
20Kht_vi2^5*+X^Xj1\~a2:*sG2016=-'Lucas Ness Travis Trump Pippi'Ybw)

```

**Try it Online!**

**Explanation**

Again, similar logic to my other answers here and here.

```
20      % Number literal
K       % Retrieve the number 4 from the K clipboard (the default value)
h       % Horizontal concatenation to produce [20 4]
t       % Duplicate elements
_v      % Negate and vertically append elements (yields [20, 4; -20 -4])
i2^     % Explicitly grab the input and square it
5*      % Multiply by 5
+       % Add this to the matrix ([20, 4; -20 -4])
X^      % Take the square root
Xj      % Ensure that the result is a real number
1\      % Get the decimal component
~       % Create a logical arrays where we have TRUE when no remainder
a       % For each column determine if any element is TRUE
2:      % Create the array 1:2
*       % Perform element-wise multiplication with boolean
s       % Sum the result to yield an index
G       % Explicitly grab the input (again)
2016=   % Check to see if it is 2016 (yields TRUE (1) if equal)
-       % Then subtract the boolean from the index. Since 2016 is NOT a
        % Fibonacci or Lucas number, the original index is 0. Subtracting
        % this boolean, will make this index now -1. For all other non-2016
        % numbers this will have no effect on the index.
'Lucas Ness Travis Trump Pippi' % Create the possible strings values
        % Note: the 0 index wraps around to the end hence Pippi being at the end.
        % The next to last entry ('Trump') is ONLY accessible via a -1 index as
        % discussed above
Yb      % Split at the spaces to create a cell array
w       % Flip the top two stack elements
)       % Retrieve the desired value from the cell array

```
> 2 votes

# Answer
# C++11, 176 + 15 (#include) = 191

```
#include<mutex>
[](int n){std::function<int(int,int)>c=[&](int f,int s){return f-s>n?0:s-n?c(s,f+s):1;};int l=c(2,1),f=c(1,1);l&f?puts("Travis"):l?puts("Lucas"):f?puts("Ness"):puts("Pippi");}

```

Ungolfed with usage. I can add explanation if requested tomorrow, gtg to bed now!

```
#include <functional>
#include <cstdio>
int main()
{
    auto r = [](int n)
    {
        std::function<int(int, int)> c = [&](int f, int s)
        {
            return f - s > n ? 0 : f - n ? c(s, f + s) : 1;
        };
        int l = c(2, 1), f = c(1, 1);
        l & f ? puts("Travis") : l ? puts("Lucas") : f ? puts("Ness") : puts("Pippi");
    };

    for (int i : { 1, 2, 3, 4, 5, 6, 7, 8, 610, 722, 843 })
    {
        printf("%i - ", i); r(i);
    }
}

```
> 1 votes

# Answer
# Javascript (ES6), 108 bytes

```
x=>(f=(a,x,y)=>a==y||a==x?1:a<y?0:f(a,y,x+y),b=f(x,0,1),c=f(x,2,1),b&&c?'Travis':b?'Ness':c?'Lucas':'Pippi')

```

Same function for Fibonnacci and Lucas. It's a recursive function that takes the first two values as init.
> 1 votes

# Answer
# Java, 151 bytes

You could argue that Trump would never outsource this crucial decision, so we wouldn't have to make the method public, saving another 7 bytes.

```
public String t(int n){return"Pippi,Lucas,Ness,Travis".split(",")[2*f(n,1,1)+f(n,2,1)];}int f(int a,int x,int y){return a==x||a==y?1:a<y?0:f(a,y,x+y);}

```

Ungolfed including test-main invocation

```
public class Trump {

    //Test Invokation
    public static void main(String[] args) {
        int[] n = {1, 2, 3, 4, 5, 6, 7, 8, 610, 722, 843, 2016 };
        for(int i = 0; i < n.length; ++i) {
            System.out.println(""+ n[i] + " => " + new Trump().t(n[i]));
        }
    }

    public String t(int n) {
        return "Pippi,Lucas,Ness,Travis".split(",")[2*f(n,1,1)+f(n,2,1)];
    }
    int f(int a,int x,int y) {
        return a==x||a==y?1:a<y?0:f(a,y,x+y);
    }

}

```

I found no way so far to test for 2016 and return "Trump" in code that's less than 15 bytes in code.
> 1 votes

# Answer
# C (gcc),  ~~128~~   ~~120~~   ~~116~~  110 bytes

```
a;b;o;f(n){for(o=b=0,a=1;a<=n;b=a+b,a=b-a)o|=(b==n)+2*(2*a+b==n);n=o?o-1?o-2?"Travis":"Lucas":"Ness":"Pippi";}

```

Try it online!

# Explanation

Let's name `F(n)` the n-th Fibonacci number, and `L(n)` the n-th Lucas number.
`a`, `b` are `F(n-1)`, `F(n)` respectively.
Then we can calculate `L(n) == F(n-1)+F(n+1) == 2*F(n-1) + F(n) == 2*a+b`
This function will successively calculate Fibonacci and Lucas numbers, up to `n`, and check if `n` is any of them.
If `n` is a Fibonacci number, the 1st bit of `o` will be set to `1`
If `n` is a Lucas number, the 2nd bit of `o` will be set to `1`
`o` will then be used to determine which name to output

# Edit

* Saved 8 bytes by golfing the condition of the for-loop : starting at second iteration, we have `a<b<c` and `a<a+c=L(n)`, so `( b<=n || a+c<=n ) => a<n`. I actually needed `a<=n` to handle correctly `n=1`
* Saved 4 bytes thanks to ceilingcat ! (also corrected a mistake, my code was outputting "2 =\> Ness")
* Saved 6 bytes:
    + 2 thanks to ceilingcat again
    + 4 by removing the variable `c`, equal to `F(n+1)`, which was useless since we can already calculate `F(n+1)` with `a` and `b`
> 1 votes

# Answer
# 05AB1E, ~~39~~ 37 (52 - 15 bonus) bytes

```
2016Qi.•ªb‚•ë>ÅG¹å_¹ÅF¹åi.•F_ïk|»9•ë.•?®B'5n•}2äsè}™

```

Try it online or verify all test cases.

**Explanation:**

```
2016Qi                # If the input equals 2016:
      .•ªb‚•          #  Push "trump" to the stack
ë                     # Else:
 >ÅG                  #  List of Lucas numbers up to and including the input+1
    ¹å                #  Check if the input is in this list (1 if truthy; 0 if falsey)
      _               #  Invert the boolean (0→1 and 1→0)
 ¹ÅF                  #  List of Fibonacci numbers up to and including the input
    ¹åi               #  If the input is in this list:
       .•F_ïk|»9•     #   Push string "travisnessi" to the stack
    ë                 #  Else:
     .•?®B'5n•        #   Push string "pippilucas" to the stack
    }                 #  Close the inner if-else
     2ä               #  Split the string into two parts
                      #   i.e. "travisnessi" → ["travis","nessi"]
                      #   i.e. "pippilucas" → ["pippi","lucas"]
       sè             #  Index the Lucas result into the list of two strings
}                     # Close the outer if-else
 ™                    # And output the top of the stack in title-case

```
> 1 votes

# Answer
## Perl 5.10, 119 - 15 (bonus) = 104 bytes

```
$_=<>;$j=1;($i,$j)=($j,$i+$j)while$_>$i;say$_-2016?(Pippi,Lucas,Ness,Travis)[($_==$i)*2|$_==3*$j-4*$i|$_-1>>1==0]:Trump

```

Ungolfed:

```
# Read line from stdin
$_ = <>;

# Find first Fibonacci number greater than or equal to input.
# Store this number in $i and the next Fibonacci number in $j.
$j = 1;
($i, $j) = ($j, $i + $j) while $_ > $i;

say $_ - 2016
  ? (Pippi,Lucas,Ness,Travis)[
      ($_ == $i) * 2 |          # Bitwise OR with 2 if Fibonacci number
      $_ == 3 * $j - 4 * $i |   # Bitwise OR with 1 if Lucas number >= 3
      $_ - 1 >> 1 == 0          # Bitwise OR with 1 if Lucas number <= 2
    ]
  : Trump

```

This exploits the fact that

```
L(n-2) = 3 * F(n+1) - 4 * F(n)

```

is the greatest Lucas number lower to or equal than F(n).
> 0 votes

# Answer
# Groovy, 149 bytes

```
f={i->g={m,s->while(s[-2]<=m)s<<s[-2]+s[-1];s}
println(["Pippi","Ness","Lucas","Travis"][(g(i,[1,1]).contains(i)?1:0)+(g(i,[2,1]).contains(i)?2:0)])}

```

Test code:

```
[1,2,3,4,5,6,7,8,610,722,843].each {
    print "$it => "
    f(it)
}

```

`g` is a closure that generates a list of numbers based on a seed (`s`) and a max value (`m`). `(g(i,[1,1]).contains(i)?1:0)+(g(i,[2,1]).contains(i)?2:0)` finds the index to use based on the number being lucas or fibonacci.
> 0 votes

# Answer
# MATLAB, ~~122~~ 119 bytes

```
@(n)subsref({'Pippi','Lucas','Ness','Travis'},substruct('{}',{(1:2)*any(~rem(real(sqrt(5*n^2+[-20,-4;20,4])),1)).'+1}))

```

**Brief Explanation**

We first create a cell array containing the values to print: `{'Pippi', 'Lucas', 'Ness', 'Travis'}`. Then to figure out which value to display, we check to see whether `n` is a Fibonacci or Lucas number.

For Fibonnaci, we use the following formula:

```
any(~rem(sqrt(5*n^2 + [-4 4]), 1))

```

This checks to see if either `5*n^2 + 4` or `5*n^2 - 4` are a perfect square. If `any` of them are, then it is a Fibonacci number.

The formula for a Lucas number is *very* similar with the exception that we use +/- 20 instead of 4:

```
any(~rem(sqrt(5*n^2 + [-20 20]), 1))

```

In this solution I combined these two cases into one by using the matrix:

```
M = [-20 -4
      20  4]

```

By applying the same equation as those above, but force `any` to consider only the first dimension, I get a two element logical array where if the first element is `true`, then it is a Lucas number and if the second element is `true`, it is a fibonacci number.

```
any(~rem(sqrt(5*n^2 + [-20 -4;20 4]), 1))

```

Then to compute the index into my initial cell array, I treat this as a binary sequence by performing element-wise multiplication of this boolean with `[2^0, 2^1]` or simply `[1,2]`. And sum the elements. Obviously I have to add 1 because of MATLAB's one-based indexing.

```
index = (1:2) * any(~rem(real(sqrt(5*n^2+[-20,-4;20,4])),1)).' + 1;

```

Then I have to use `subsref` and `substruct` to index into the initial cell array to obtain the final result.
> 0 votes

# Answer
## JavaScript (ES6), 97 bytes

```
x=>[['Pippi','Lucas'],['Ness','Travis'],f=(a,x,y=1)=>a>x?f(a,y,x+y):a==x||a==1][+f(x,0)][+f(x,2)]

```

The `a==1` check is needed otherwise I don't notice that 1 is a Lucas number.
> 0 votes

# Answer
# Jelly, 47 bytes - 15 = 32

```
+2ḶÆḞ⁸eð+ị“©ḤʠhMṂƁÞḄṭAƓ»Ḳ¤µ2+Ð¡-⁸eḤ
“¡Ỵ¦»Ç⁼?⁽¥Ð

```

Try it online!
> 0 votes

---
Tags: code-golf, sequence, fibonacci
---