title: No-alphanumeric code exec

text:
# Question
Title: No-alphanumeric code exec
# Introduction

In most interpreted languages, there is an operation that will run code generated at runtime. It generally requires alphanumeric characters to refer to this operation. Write a program, using as few alphanumeric characters as possible, that is able to download and execute any string in the language you're working with, using as few alphanumeric characters as possible.

Informal bonus points for commonly used languages where this is a very difficult task, such as python.

# Challenge

Inputs: a url to code in your language of choice, via either stdin or argv.

Outputs: output of executing the downloaded code.

Your program must generate the string to execute and call the eval/exec function/operator without reading from any existing files (excluding the file readings done by your interpreter of choice on startup and reading of standard library files by your language's import mechanism).

Winning entries must be written using only printable ascii characters. Compiled languages are allowed, if you can find a way to invoke the same compiler at runtime with the same settings.

Submissions will be scored, per-language, based on who uses the fewest executable alphanumeric characters. Non-alphanumeric characters do not count towards your score, nor do comments - try to make your non-alphanumeric code readable.

# Input and Output example

Contents of my example target gist for python:

```
print("run by no-alphanum code exec")

```

example run:

```
$ python noalpha.py https://gist.githubusercontent.com/lahwran/77e94ef11493d4f36c726efe030f58e4/raw/5f7a0483a9fe7928ae2cf3f786d6d35f9d7870b9/example.py
run by no-alphanum code exec
$

```

# Answer
> 6 votes
# Python 2, 5 alphanumerics

```
__=-~-~([]==[])
__*=__
_=__*-~-~-~__
exec('%c'*~-~-~-(__*~-~-__))%(~-~-~-_,-~_,-~-~-~-~_,-~-~-~_,-~-~-~-~-~-~_,-~-~-~-~-~-~-~-~_,' ',_+__,-~-~-~-~-~-~_,_,_,~-~-~-_,~-_-__,' ',~-~-_-__,-~-~-~-~-~-~-~_,' ',_+__,',',-~-~-~-~-~-~-~_,-~-~-~-~_+__,-~-~-~-~-~-~-~_,';',~-~-~-~-~-~-~-_,-~-~-~_+__,~-~-~-~-~-~-~-_,_-__,' ',_+__,'.',_+__,-~-~-~-~-~-~_,_,-~-~-~_,-~-~-~-~_,~-~-~-~-~-~-~-_,-~-~_,'(',-~-~-~-~-~-~-~_,-~-~-~-~_+__,-~-~-~-~-~-~-~_,'.',~-~-_-__,-~-~-~-~-~-~_,~-~-~-~-~-_,-~_+__,'[','_','=','=','_',']',')','.',-~-~-~-~-~-~_,~-~-~-~-~-~-~-_,~-~-_-__,~-~-~-~-~-~-~-~-_,'(',')')

```

Try it online (with print not exec)

It helps with a bit of experience with Symbolic Python, where alphanumerics are banned anyway. This is rather lazily golfed and could probably be a few dozen bytes shorter, but hey, this isn't . The 5 alphanumerics here are the `exec` and the `c` of `%c`. If we were allowed unprintables, the `%c` could be bypassed with the help of the repr operator ```.

The executed format string translates to `import urllib as u,sys;exec u.urlopen(sys.argv[_==_]).read()`, which fetches the resource and executes it.

### Explanation:

Python can use variables with names entirely composed of underscores, which really helps us. It also treats `True/False` as `1/0`, which means we can compose numbers entirely without alphanumerics. For example, the first part of the code does:

```
__=-~-~([]==[])   # Set __ to 3
__*=__            # Square it to 9
_=__*-~-~-~__     # Set _ to 9*12 = 108

```

Here's where we reach the unavoidable letters. To make letter in a string, we can use `%c` in a format string to take a number and return the character with that ordinal value. We can then pass this string into the `exec` statement and voila! We can execute arbitrary code with only 5 alpha-numerics. The majority of the rest of the code is just repeating the `%c` enough times, then creating the numbers representing each letter.

# Answer
> 3 votes
# Javascript, 0 Alphanumerics

This is my first answer, so hopefully I haven't accidentally broken a rule :)

Here's the code before extreme obfuscation:

```
var str = prompt("Enter relative URL of code to exec:", "");
var xhr = new XMLHttpRequest();
xhr.open('GET', str, true);
xhr.onreadystatechange = function() {
  if (xhr.readyState === 4)  {
    eval(xhr.responseText);
  }
};
xhr.send(null);

```

It isn't verified, and neither is the obfuscated (and de-alphanumerized) version.

I used a form of obfuscated JS which you can find here. The actual solution is more than 220,000 characters long. It does have to be run in a browser. Also, there are no comments in the obfuscated code, but the de-obfuscated code speaks for itself if you have JS experience.

There are several online translators.

It takes the input URL through a prompt. You have to run it in a web browser while on the domain that the code is on.

Here's a link to the file, since pastebin lagged out after I pasted it: Source file

# Answer
> 0 votes
# Bash, 4 alphanumerics

```
wget $@
. ${@##*/}

```

No TIO link because TIO doesn't have hostname resolution.

---
Tags: code-challenge, restricted-source, printable-ascii
---


title: The Coin Problem

text:
# Question
Title: The Coin Problem
# Background

The official currency of the imaginary nation of Golfenistan is the *foo*, and there are only three kinds of coins in circulation: 3 foos, 7 foos and 8 foos. One can see that it's not possible to pay certain amounts, like 4 foos, using these coins. Nevertheless, all large enough amounts can be formed. Your job is to find the largest amount that can't be formed with the coins (5 foos in this case), which is known as the coin problem.

# Input

Your input is a list `L = [n<sub>1</sub>, n<sub>2</sub>, ..., n<sub>k</sub>]` of positive integers, representing the values of coins in circulation. Two things are guaranteed about it:

* The GCD of the elements of `L` is 1.
* `L` does not contain the number 1.

It may be unsorted and/or contain duplicates (think special edition coins).

# Output

Since the GCD of `L` is 1, every large enough integer `m` can be expressed as a non-negative linear combination of its elements; in other words, we have

```
 m = a<sub>1</sub>*n<sub>1</sub> + a<sub>2</sub>*n<sub>2</sub> + ... + a<sub>k</sub>*n<sub>k</sub>
```

for some integers `a<sub>i</sub> ≥ 0`. Your output is the largest integer that *cannot* be expressed in this form. As a hint, it is known that the output is always less than `(n<sub>1</sub> - 1)*(n<sub>k</sub> - 1)`, if `n<sub>1</sub>` and `n<sub>k</sub>` are the maximal and minimal elements of `L` (reference).

# Rules

You can write a full program or a function. The lowest byte count wins, and standard loopholes are disallowed. If your language has a built-in operation for this, you may not use it. There are no requirements for time or memory efficiency, except that you should be able to evaluate the test cases before posting your answer.

After I posted this challenge, user @vihan pointed out that Stack Overflow has an exact duplicate. Based on this Meta discussion, this challenge will not be deleted as a duplicate; however, I ask that all answers based on those of the SO version should cite the originals, be given the Community Wiki status, and be deleted if the original author wishes to post their answer here.

# Test Cases

```
[3, 7, 8] -> 5
[25, 10, 16] -> 79
[11, 12, 13, 14, 13, 14] -> 43
[101, 10] -> 899
[101, 10, 899] -> 889
[101, 10, 11] -> 89
[30, 105, 70, 42] -> 383
[2, 51, 6] -> 49

```

# Answer
# Pyth, 23 bytes

```
ef!fqTs.b*NYQY^UTlQS*FQ

```

It's very slow, as it checks all values up to the product of all the coins. Here's a version that is almost identical, but 1) reduces the set of coins to those not divisible by each other and 2) only checks values up to `(max(coins) - 1) * (min(coins) - 1)` (47 bytes):

```
=Qu?.A<LiHdG+GHGQYef!fqTs.b*NYQY^UTlQS*thSQteSQ

```

## Explanation

```
                   S            range 1 to
                    *FQ         product of input
 f                             filter by
               UT                range 0 to T
              ^  lQ              cartesian power by number of coins
   f                            filter by
      s.b*NYQY                   sum of coin values * amounts
    qT                           equals desired number T
  !                             nothing matching that filter
e                             take last (highest) element

```
> 4 votes

# Answer
# Perl, ~~60~~ ~~54~~ 51 bytes

50 bytes code + 1 bytes command line

```
$.*=$_,$r.=1x$_."|"}{$_=$.while(1x$.--)=~/^($r)+$/

```

The basic approach is to let the regex engine do the hard work with string matching. For example, it will construct a regex similar to `^(.{3})*(.{7})*(.{8})*$` and match against a string of length `n` where `n` descends from the product of the inputs until it fails to match.

Note that this will become exponentially slow as the number of arguments increases.

Usage: Arguments are read in from STDIN (new line separated), for example:

```
printf "101\n10" | perl -p entry.pl

```
> 9 votes

# Answer
# , 84 78 72 bytes

For an arbitrary entry of coprimes, \\$a\_1, a\_2,\ldots\\$, Frobenius' amount is given by

```
a=scan();max((1:(b<-min(a)*max(a)))[-colSums(combn(outer(a,0:b),sum(!!a)))])

```

Try it online!

since it is always smaller than the product of the extreme \\$a\_i\\$'s. It is then a matter of combining all possible combinations (and more) within that range. Thanks to Cole Beck for suggesting `outer` with no "\*" and `colSums` rather than \`apply(...,2,sum)'.

A faster but longer (by two bytes) version only considers `max(a)`:

```
a=scan();max((1:(min(a)*(b<-max(a))))[-colSums(combn(outer(a,0:b),sum(!!a)))])

```

A slightly shorter version (72 bytes) that most often takes too log or too much space to run on Try it online is

```
a=scan();max((1:(b<-prod(a)))[-colSums(combn(outer(a,0:b),sum(!!a)))])

```
> 3 votes

# Answer
# Python2, 188 187 bytes

```
def g(L):
 M=max(L);i=r=0;s=[0]*M;l=[1]+s[1:]
 while 1:
    if any(all((l+l)[o:o+min(L)])for o in range(M)):return~-s[r]*M+r
    if any(l[(i-a)%M]for a in L):l[i]=1
    else:r=i
    s[i]+=1;i=(i+1)%M

```

The second indentation is rendered as 4 spaces on SO, those should be tabs.

Actually a 'fast' solution, not bruteforce, uses 'Wilf's Method' as described here.
> 2 votes

# Answer
# Javascript ES6, ~~120~~ ~~130~~ ~~126~~ ~~128~~ ~~127~~ 125 chars

```
f=a=>`${r=[1|a.sort((a,b)=>a-b)]}`.repeat(a[0]*a[a.length-1]).replace(/./g,(x,q)=>r[q]|a.map(x=>r[q+x]|=r[q])).lastIndexOf(0)

```

Alternative 126 chars version:

```
f=a=>{r=[1];a.sort((a,b)=>a-b);for(q=0;q<a[0]*a[a.length-1];++q)r[q]?a.map(x=>r[q+x]=1):r[q]=0;return r.join``.lastIndexOf(0)}

```

Test:

```
"[3, 7, 8] -> 5\n\
[25, 10, 16] -> 79\n\
[11, 12, 13, 14, 13, 14] -> 43\n\
[101, 10] -> 899\n\
[101, 10, 899] -> 889\n\
[101, 10, 11] -> 89\n\
[30, 105, 70, 42] -> 383\n\
[2, 51, 6] -> 49".replace(/(\[.*?\]) -> (\d+)/g, function (m, t, r) {
  return f(JSON.parse(t)) == r
})

```
> 1 votes

# Answer
# Ruby, 108 bytes

```
->a{b=[0];m=a.min
(1..1.0/0).map{|n|c=p
a.map{|x|c|=(b!=b-[n-x])}
c&& b<<=n
return n-m if b[-m]&&b[-m]>n-m}}

```

Try it online!

# Explanation

```
->a{                                         input list
    b=[0];                                      list of representable integers
        m=a.min                                     minimum input
    (1..1.0/0).map{|n|                       n in range 1..
        c=p                                    c = false
          a.map{|x|c|=(b!=b-[n-x])}              check if n goes in b
            c&& b<<=n                                   put n in b
              return n-m if b[-m]&&b[-m]>n-m}}            return if m values in a row

```
> 0 votes

---
Tags: code-golf, number, combinatorics, integer-partitions
---


# Question
Title: Recreate a simplified version of the card game L.L.A.M.A
In LLAMA, you want to dump cards from your hand as quickly as you can, but you might not be able to play what you want.

Each player starts a round with six cards in hand; the deck consists of llama cards and cards numbered 1-6, with eight copies of each. On a turn, the active player can play a card or draw a card. To play a card, you must play the same number as the top card of the discard pile or one number higher (for simplicity, we will follow the rule that if you can play a card of the same number, you will play that card, if not, play the higher card). If a 6 is on the discard pile, you can play a 6 or a llama, and if a llama is on top, you can play another llama or a 1. If you cannot play any cards, you must draw a card.

The round ends when one player empties their hand, who is pronounced as the winner of that round.

Some specifications: 1. The llama cards may have any name, but must be stored as a string (e.g. simply using the value 7 as the llama card is not permitted) 2. If a player draws a card, they may not play the drawn card in the same round again, i.e. their turn ends after drawing a card. 3. We will play the game with four players.

The output should list the turns taken by each player in the following fashion:

```
1 - 1
2 - 1
3 - 1
4 - 2
1 - 3
2 - draw
3 - 3
4 - 4
.
.
.
1 - 6
2 - llama
game over, 2 wins.

```

As always in code-golf, the program with the lowest number of bytes wins.

Edits:

In response to the comments, here are a few additional specifications.

* The output may have any format as long as it contains the player number and their action.
* The llama card should be a string composed only of letters, no numbers allowed.
* At the start of a game, there is a single card on the discard pile, i.e. player 1 cannot play any card.
* If the draw deck is empty, the played cards should be reshuffled. As the official rules of the game do not specify what should happen if all cards are drawn and there are no cards in the discard pile, this case does not need to be accounted for.
* There is no input, i.e. the shuffled deck and dealing the hand cards must all be done in the program.

# Answer
# Jelly, 94 bytes

```
Ḣ_þⱮOƑƇ€}ṪṪʋ%7ż⁸ʋṢF,Ḣ;€2¦@¥¥¥F;1ịḢɗ}ɗ,;€”d$}ɗḢ€ḢỊƊ?ṭ€1¦⁸
56Ẋ%7s32s"31,6Ṛç/Ẉ€Ȧ$Ð¿Ṫ€⁺⁺Ḋo”l4R¤ṁżƊ

```

Try it online!

A set of links which when run niladically returns a list of pairs of `[player number, move]` where move is `l 1 2 3 4 5 6 d`. `l` represents llama and `d` draw.
> 2 votes

# Answer
# Python 3.8 (pre-release), <sup>~~401~~ \\$\cdots\\$ ~~347~~</sup> 345 bytes

```
from random import*
d=[*range(7)]*8
shuffle(d)
p=[[d.pop()for i in[1]*6]for j in[1]*4]
o=[*range(1,7)]+['l']
h=[]
s=d.pop()
def g(a):p[n].remove(a);h.append(s);print(f"{n+1}-{o[a]}")
n=3
while all(p):
 n=-~n%4
 if s in p[n]:g(s)
 elif(t:=-~s%7)in p[n]:g(t);s=t
 else:
  if not d:d=h;h=[];shuffle(d)
  p[n]+=[d.pop()];print(f"{n+1}-d")
print(n+1)

```

Try it online!

* Prints `player-card` for each move.
* `player` is `1` to `4`.
* `card` is `1` to `6` or `l` for llama or `d` for draw.
* Simply prints winner's number at the end.
> 1 votes

# Answer
# Charcoal, ~~127~~ 121 bytes

```
Ｆl123456Ｆ⁸⊞υι≔⟦⟧θＷυ«≔‽υι⊞θι≔Φυ⁻λ⌕υιυ»≔Ｅ⁴Ｅ⁶⊟θη≔⊟θζ≔⁰εＷ⌊η«≔§ηεδＩ⊕ε-¿⊙δ›²﹪⁻ΣκΣζ⁷«Ｆ¬№δζ≔⎇⁼6ζlＩ⊕Σζζ§≔ηεΦδ⁻λ⌕δζζ»«⊞δ⊟θd»⸿≔﹪⊕ε⁴ε

```

Try it online! Link is to verbose version of code. Outputs `l` for llama and `d` for draw. Winner is person who last played a card. Explanation:

```
Ｆl123456Ｆ⁸⊞υι≔⟦⟧θＷυ«≔‽υι⊞θι≔Φυ⁻λ⌕υιυ»

```

Create and shuffle the deck.

```
≔Ｅ⁴Ｅ⁶⊟θη≔⊟θζ

```

Deal.

```
≔⁰ε

```

Start with player 1.

```
Ｗ⌊η«

```

Repeat until someone wins.

```
≔§ηεδ

```

Get the current player's hand.

```
Ｉ⊕ε-

```

Output the current player.

```
¿⊙δ›²﹪⁻ΣκΣζ⁷«

```

If they have a playable card:

```
Ｆ¬№δζ

```

if they don't have a matching card,

```
≔⎇⁼6ζlＩ⊕Σζζ

```

then increment the last discard, rolling over to `l` for llama;

```
§≔ηεΦδ⁻λ⌕δζ

```

remove the playable card from their hand;

```
ζ

```

and print their play.

```
»«⊞δ⊟θd»

```

Otherwise draw a card and print that action.

```
⸿

```

Move to the start of the next line.

```
≔﹪⊕ε⁴ε

```

Update to the next player.
> 1 votes

---
Tags: code-golf, card-games
---


title: Inter-language 2-cycle quine

text:
# Question
Title: Inter-language 2-cycle quine
# Challenge

Create 2 programs A and B

* The output of program A is exactly program B
* The output of program B is exactly program A
* Neither program should depend on inputs to yield the correct output
* A and B are not identical programs
* A and B are of different programming languages
* Neither program may be equivalent to itself in the other language. For example, if the chosen languages are C and C++, the C++ program must not be a valid and equivalent C program, else the "inter-language" requirement is redundant

A solution should include:

# Scoring

The score for a solution is:

* The length of the shortest program +
* The combined length of the names of both programming languages, as they appear on tio.run

The reason for this unusual scoring is because this constitutes the combined length of the minimum information necessary to communicate your solution.

---

This is my first post to Code Golf. Any edits to this post to increase clarity or appropriate vocabulary are welcome.

# Answer
> 3 votes
# \>\<\> and Gol\>\<\>, 18 bytes + 3 + 6 = 27

```
'3d*:5-0@o~r{?H>o<

```

Try it online!

and

```
"3d*:5-0@o~r{?H>o<

```

Try it online!

Both output the same program, but with the first character flipped between `'` and `"`. Neither program is equivalent to itself in the other language, since the behaviour of `@` differs.

# Answer
> 2 votes
# Jelly, 13 bytes + 8 = score 21

```
“Ṿ;⁾v`+/ŒṘ”v`

```

Try it online!

# RAD

```
'“Ṿ;⁾v`+/ŒṘ”v`'

```

Try it online!

A Jelly quine that wraps itself in single quotes, such that the resultant RAD program simply prints the original Jelly program back out.

Thanks to @JoKing for golfing the language name for the second program!

---
Tags: code-challenge, quine
---


title: Print out execution time of program

text:
# Question
Title: Print out execution time of program
## Challenge

Write a complete program that prints out the time it took to execute a certain part of itself. That part must include a process whose total number of operations (and therefore execution time) is dependent on a user-substituted numeric value - this can be denoted in any way in your code (uppercase N for example) and doesn't count as a byte.

Unlike many code golf challenges, this one is a valid use case - in environments that allow executing code from command line, you may want to have a short code snippet to roughly compare performance across different systems.

## Rules

* Execution time is denoted as a nonnegative integer or decimal value, followed by the corresponding time unit (let's accept **ns**, **µs**/**us**, **ms**, **s**, **m** and **h**). A space between the number and unit is optional, more spaces are also allowed (but not newline characters).
* Output must include the execution time exactly once. There can be additional text around it, as long as no part of it could be matched with the execution time itself. This allows using standard functions for timing code execution that may use various formats for printing out the execution time.
* Output goes to STDOUT. Anything in STDERR is disregarded.
* You can import any standard libraries before the actual code, without any cost to the total number of bytes, but you are not allowed to change the library name in the import declaration.
* Do not just use sleep to control the execution time, as that does not increase the number of operations (and also doesn't work as a performance benchmark). The execution time must also depend on the user-substituted value linearly, exponentially or polynomially (before you ask, a constant polynomial doesn't count).

## Scoring

This is code golf, so the shortest answer in bytes wins.

## Example

This is an unnecessarily long program written in Python:

```
import time

start_time = time.time()

for i in range(N):
    pass

end_time = time.time()

print("%fs" % (end_time - start_time))

```

Program description:

* imports the standard `time` library (this adds no bytes to the code size)
* stores the current time in seconds
* loops N times, does nothing each iteration
* stores the time after the loop
* prints the time difference in the correct format

# Answer
# Zsh, 14(?) bytes

*If `N` is substituted in place of `$1` (as described in the prompt), then **14 bytes**. If `N` is given as an argument, then **16 bytes**.*

---

```
time (: {0..$1})

```

Try it online!

Uses the builtin `time` (you can verify that this is a Zsh builtin: run `type time`). The time to expand the brace expansion increases with the input.

You might think to use `time sleep $1`, but `sleep` is an external program, not pure Zsh.
> 7 votes

# Answer
# APL (Dyalog Unicode), 12 bytesSBCS

Full program. Returns elapsed time in seconds, followed an "s". Runtime on TIO is roughly linear with N, with a coefficient of about 6×10-10. Uses the dfns library, but per OP, import isn't counted.

```
's',⍨cmpx'⍳N'

```

Try it online!

`'⍳N'` expression generating the **ɩ**ntegers 1 through N

`cmpx` time the execution of that expression

`'s',⍨` append "s"
> 6 votes

# Answer
# , ~~29~~ 28 bytes

```
cat(system.time(!1:9e6)[3],"s")

```

Try it online!

A full program printing the number of seconds elapsed complete with unit. The `9e6` is not counted per the rules and can be replaced with any other number. Thanks to @RobinRyder for saving a byte!

An alternative would be `paste(system.time(!1:9e6),"s")`, but this also prints our four other times (the correct one is in the middle).
> 5 votes

# Answer
# , ~~16~~ ~~14~~ 19 bytes (20 - 1 for N)

```
echo's',~":6!:2'i.N'

```

Try it online!

*-2 bytes thanks to Adam -- after looking at his answer I realized I didn't need to sum the integers, just generate them*

*+6 bytes thanks to Adam for pointing out I missed the unit*

Generates the integers `0..N-1`, times it, and prints it to stdout. `'s',~` prepends the unit `s` for seconds.
> 4 votes

# Answer
# 05AB1E, ~~12~~ 10 bytes

```
ƒžc})¥O's«

```

-2 bytes thanks to *@ExpiredData*.

Either add the \\$n\\$ as leading portion (i.e. `100ƒžc})¥O's«`) or simply use \\$n\\$ as STDIN input.
Outputs the execution time in whole seconds (without space).

Try it online.

**Explanation:**

```
ƒ            # Loop in the range [0, n]:
 žd          #  Push the current time in seconds
   })        # After the loop: wrap all values on the stack into a list
     ¥       # Get the deltas (paired differences) of this list
      O      # And sum those (to get the difference between the first and last times)
       's«  '# And append a trailing "s" (without space)
             # (after which this is output implicitly to STDOUT)

```
> 4 votes

# Answer
# PowerShell, 38 bytes

```
param($n)$a={1..$n};Measure-Command $a

```

Try it online!
> 4 votes

# Answer
# Python 2.7 - 32 bytes

```
print timeit.timeit(number=N),'s'

```

We can take advantage of the different scoring rules here. timeit.timeit has been in the standard library since 2.6, so we get to ignore the `import timeit` and hence 14 bytes that would have cost.

timeit is designed to be able to take a statement for execution as a parameter, but has a default of `pass`. So the `pass` statement will be executed N times, and that is what will be timed.
> 4 votes

# Answer
## Raku (18 or 25)

Depending on one's definition of a "standard" library for Raku...

```
use Timer; # uncounted import line
say timer {[+] ^N}

```

or

```
[+] ^N;say now -BEGIN now
$/=now;[+] ^N;say now -$/

```

`[+] ^N` sums all numbers from 0 to N, so the bigger it gets, the more ops it does. The `now - BEGIN now` bit is a common idiom in Raku that virtually makes such libraries unnecessary (the phaserless alternative is as long or longer).
> 3 votes

# Answer
# C (gcc), 59 bytes

```
main(c,a){a=clock();for(c=100;c--;);printf("%dus",clock()-a);}

```

Try it online!
> 2 votes

# Answer
# Java 5/6, ~~99~~ ~~98~~ 78 bytes

```
import static java.lang.System.*;
enum A{A;{long s=nanoTime();for(int i=#;i-->0;);out.print(nanoTime()-s+"ns");}}

```

Loops the given \\$n\\$ amount of times without doing anything in the loop body.

# Java 11, ~~128~~ ~~122~~ ~~121~~ 101 bytes

```
import static java.lang.System.*;
interface M{static void main(String[]a){var s=nanoTime();"x".repeat(#);out.print(nanoTime()-s+"ns");}}

```

Creates a String of \\$n\\$ amount of `"x"` with the Java 11 `String#repeat(int)` builtin.

Try it online.

In both programs, replace the `#` for the actual number.
And both will output the execution time in nanoseconds (without space).

-20 bytes thanks to *@Holger* for remembering me to (ab)use the rule "*You can import any standard libraries before the actual code, without any cost to the total number of bytes, but you are not allowed to change the library name in the import declaration.*" by using a `static import` for `System`.
> 1 votes

# Answer
# SAS, 37 bytes

```
option stimer;data;do i=1to N;end;run;

```

This increments a loop counter `i` and outputs the final value `N` to a SAS dataset. This is not optimised out, so the run time is linearly dependent on `N`.
> 0 votes

# Answer
# Wolfram Language (Mathematica), ~~40~~ ~~29~~ ~~28~~ 26 bytes

```
First@Timing@Do[,N]~Print~s

```

Try it online!

Replace N with number of times to do the operation. Does `null` N times (doing nothing is an operation in this case, as you can observe by increasing N and time increases).
> 0 votes

# Answer
# MathGolf, ~~10~~ 9 (or 12?) bytes

```
{t}]│Σûms

```

With \\$n\\$ as STDIN input.

Try it online.

If this is not allowed, it would be 3 bytes longer instead:

```
"#"i{t}]│Σûms

```

Where the `#` is replaced with the integer \\$n\\$ (i.e. `"100"i{t}]│Σûms`).

Try it online.

Both answers output the execution time in milliseconds without space.

**Explanation:**

Uses a similar approach as my 05AB1E answer.

```
               #  Use the (implicit) input-integer
               # Or alternatively:
"#"            #  Push the integer-string
   i           #  And convert it from a string to an integer
    { }        # Loop that many times
     t         # Push the current timestamp in milliseconds
       ]       # After the loop, wrap all times in a list
        |      # Get the forward differences of this list
         Σ     # Sum those differences
          ûms  # Push the string "ms"
               # (after which the entire stack joined together is output implicitly)

```

NOTE: Simply using `100` instead of `"100"` would add three digits (`1,0,0`) to the stack instead, which is why I have to do the `"100"i` to make it universal for all possible \\$n\\$.

`]│Σ` could alternatively be `⌐-Þ` for the same byte-count: Try it online.

```
       ⌐        # Rotate all values on the stack clockwise
        -       # Subtract the top two values on the stack
         Þ      # Discard everything from the stack, except for the top item

```
> 0 votes

# Answer
# PHP, 62 bytes

```
<?php $t=microtime(1);for(;$i<N;$i++);echo microtime(1)-$t.'s';

```

Try it online!

This is my first try in codeGolf, hope I get this right!

**Some explanations:**

* `microtime(true)` gets timestamp in seconds as a float with the precision of microseconds
* taking advatange that errors are discarded, so `$i` is not initialized
* using automatic type conversions
> 0 votes

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


title: Arrays Start at \$\pi\$

text:
# Question
Title: Arrays Start at \$\pi\$
Your task is to take an array of numbers and a real number and return the value at that point in the array. Arrays start at \\$\pi\\$ and are counted in \\$\pi\\$ intervals. Thing is, we're actually going to interpolate between elements given the "index". As an example:

```
Index:    1π   2π   3π   4π   5π   6π
Array: [ 1.1, 1.3, 6.9, 4.2, 1.3, 3.7 ]

```

Because it's \\$\pi\\$, we have to do the obligatory trigonometry, so we'll be using cosine interpolation using the following formula:

\\${\cos(i \mod \pi) + 1 \over 2} * (\alpha - \beta) + \beta\\$

where:

* \\$i\\$ is the input "index"
* \\$\alpha\\$ is the value of the element immediately before the "index"
* \\$\beta\\$ is the value of the element immediately after the "index"
* \\$\cos\\$ takes its angle in radians

# Example

Given \[1.3, 3.7, 6.9\], 5.3:

Index 5.3 is between \\$1\pi\\$ and \\$2\pi\\$, so 1.3 will be used for `before` and 3.7 will be used for `after`. Putting it into the formula, we get:

\\${\cos(5.3 \mod \pi) + 1 \over 2} * (1.3 - 3.7) + 3.7\\$

Which comes out to 3.165

# Notes

* Input and output may be in any convenient format
* You may assume the input number is greater than \\$\pi\\$ and less than `array length` * \\$\pi\\$
* You may assume the input array will be at least 2 elements long.
* Your result must have at least two decimal points of precision, be accurate to within 0.05, and support numbers up to 100 for this precision/accuracy. (single-precision floats are more than sufficient to meet this requirement)

Happy Golfing!

# Answer
# , ~~59~~ 53 bytes

```
function(x,i)x[0:1+i%/%pi]%*%c(a<-cos(i%%pi/2)^2,1-a)

```

Try it online!

Nothing too clever here - just an R version of the formula in the question. Thanks @MickyT for saving a byte, and to @Giueseppe and indirectly @xnor for another two, and thanks to @RobinRyder for saving a further 3.
> 5 votes

# Answer
# Python 3.8 (pre-release), ~~85~~ 74 bytes

-8 bytes thanks to @xnor
-2 bytes thanks to @Quintec

This takes advantage of the Python 3.8 pre-release's new `:=` assignment operator. Other than that, this is really just the equation written out in Python.

```
import math
lambda l,i:cos(i%math.pi/2)**2*(l[(j:=int(i/pi))-1]-l[j])+l[j]

```

Usage:

```
>>> p=lambda l,i:cos(i%math.pi/2)**2*(l[(j:=int(i/pi))-1]-l[j])+l[j]
>>> print(p([1.3, 3.7, 6.9],5.3))
3.165249203414993

```

Try it online!
> 4 votes

# Answer
# Jelly, 17 bytes

```
d©ØPṪÆẠ‘H×I_@Ḋ}®ị

```

A full program accepting \\$i\\$ and the array which prints the interpolated value.

**Try it online!**

### How?

Interpolates between all neighbours using \\$\frac{\cos(i \mod \pi)+1}2\\$ then picks the relevant value.

```
d©ØPṪÆẠ‘H×I_@Ḋ}®ị - Link: number, i; list of numbers, A
  ØP              - pi (ish) = 3.141592653589793
d                 - divmod = [i//pi, i%pi]
 ©                - (copy to register for later)
    Ṫ             - tail (gets i%pi leaving register copy as [i//pi])
     ÆẠ           - cosine = cos(i%pi)
       ‘          - increment
        H         - halve
         ×        - multiply by A (vectorises)
          I       - increments -- i.e. (cos(i%pi)+1)(r-l)/2 for neighbours [l,r]
             Ḋ}   - dequeue A
           _@     - swapped arg subtract (vectorises) -- i.e. r-(cos(i%pi)+1)(r-l)/2
                  -                                         = r+(cos(i%pi)+1)(l-r)/2
               ®  - recall value from the register
                ị - index into (vectorises) -- i.e. [β+(cos(i%pi)+1)(α-β)/2]
                  - implicit print of Jelly representation (only 1 entry so [] wont appear)

```
> 3 votes

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

```
n=>m=>(Math.Cos(m%Math.PI)+1)/2*(n[m=(int)(m/Math.PI)-1]-n[++m])+n[m]

```

~~I beat Python!~~ ~~Darn it, Python beat me.~~ I beat Python again!

Try it online!
> 3 votes

# Answer
# Röda, 51 bytes

```
f a,i{j=i//PI;[(cos(i%PI)+1)/2*(a[j-1]-a[j])+a[j]]}

```

Try it online!
> 2 votes

# Answer
# Japt, ~~47~~ ~~46~~ 38 bytes

```
u0;J=V/MP[A=UgJc) nUgJf))½McVuMP)Ä]×+A

```

To be continued... (golfing)

Try it online!
> 1 votes

# Answer
# APL+WIN, ~~39~~ 37 bytes

2 bytes saved thanks to Adám

```
2⊃m+(-/m←⎕[0 1+⌊n÷○1])÷2÷1+2○(○1)|n←⎕

```

Try it online!Dyalog Classic

Explanation:

```
n←⎕ prompt for input of integer

2÷1+2○(○1)|n evaluate first term of formula

[0 1+⌊n÷○1] identify indices of alpha and beta

m←⎕[...] prompt for input of vector and select alpha and beta

-/m alpha-beta

2⊃m+ take result of adding beta to complete the equation

```
> 1 votes

# Answer
# Stax, 17 bytes

```
≈ëBü☺ÆssÅ¢â)KjjïΔ

```

Run and debug it

Unpacked, ungolfed, and commented it looks like this.

```
VP|%    divmod with pi;  push div and mod results separately
|7^h    do (cos(modpart) + 1) / 2
sX      swap the original div result to top of stack, store it in the x register
v       decrement
;:-     pairwise differences of array
@       get element at index
N*      negate and multiply
;x@     get element from the original array at the x index, where x is the register
+       add

```

Run this one
> 1 votes

# Answer
# Haskell, 65 bytes

```
v!i|(c,r)<-properFraction$i/pi=cos(r*pi/2)^2*(v!!(c-1)-v!!c)+v!!c

```

Try it online!

Note: the array is represented as a list.

Thanks to @xnor for the half-angle tip.
> 1 votes

# Answer
# Ruby, 67 bytes

```
->a,i{z=Math::PI;Math.cos(i%z/2)**2*(a[-1+j=(i/z).to_i]-a[j])+a[j]}

```

Try it online!
> 1 votes

# Answer
# Jelly, ~~23~~ ~~20~~ 18 bytes

```
³%ØPÆẠ×_++H
÷ØPịÇ/

```

Try it online!

```
÷ØPịṁØ½µ³%ØPÆẠ×I_@SH    Dyadic link, arguments x (index) and Z (array):
÷ØP                     x/pi
   ị                    Index (into Z).
                        When x/pi is an integer, returns that elt of Z.
                        Otherwise returns 2 elements at floor and ceiling.
     Ø½                   [1,2] (generic 2 element array)
    ṁØ½                 Mold; shape like [1,2] to ensure we have 2 elements.
       µ                Start a new, monadic chain with the result [a,b]
        ³%ØPÆẠ×I_@SH    Monadic chain
        ³               x
         %ØP            x mod pi
            ÆẠ          Unarccosine; cos(x mod pi).
               I          Increment; b-a.
              ×I        (b-a) cos(x mod pi)
                  S       a+b
                _@S     a + b - (b-a) cos(x mod pi)
                   H    Halve; this is equivalent to our desired result.

```
> 0 votes

# Answer
# 05AB1E, ~~22~~ ~~21~~ ~~20~~ 19 bytes

```
žq‰`Å¾>;UÝèÐÁ-θX*-θ

```

Try it online or verify some more test cases.

**Explanation:**

```
žq‰        # Take the divmod PI of the (implicit) input-decimal
           # (part = input integer-divided by PI, remainder = input modulo-PI)
           #  i.e. 5.3 → [1, 2.158...]
   `       # Push both values separately to the stack
    Å¾     # Take the cosine of the remainder
           #  i.e. 2.158... → -0.554...
      >    # Increase it by 1
           #  i.e. -0.554... → 0.554...
       ;   # Halve it
           #  i.e. 0.554... → 0.222...
        U  # Pop and store it in variable `X`
    Ý      # Pop the part, and push a list in the range [0, part]
           #  i.e. 1 → [0, 1]
     è     # (0-based) index all of them into the (implicit) input-list
           #   i.e. [1.3, 3.7, 6.9] and [0, 1] → [1.3, 3.7]
Ð          # Triplicate this list
 Á         # Rotate the last copy once towards the right
           #  i.e. [1.3, 3.7] → [3.7, 1.3]
  -        # Subtract the values in the top two lists from one another
           #  i.e. [1.3, 3.7] and [3.7, 1.3] → [-2.4, 2.4]
   θ       # Pop and only leave the last value of this list
           #  i.e. [-2.4, 2.4] → 2.4
    X*     # Multiply it by `X`
           #  i.e. 2.4 * `X`=0.222... → 0.534...
     -     # Subtract it from each of the values in the list we triplicated
           #  i.e. [1.3, 3.7] - 0.534... → [0.765..., 3.165...]
      θ    # And only leave the last value of this list
           #  i.e. [0.765..., 3.165...] → 3.165...
           # (which is output implicitly as result)

```
> 0 votes

# Answer
# C (GCC) ~~99~~ 79 bytes

-20 bytes ceilingcat

```
float P=3.141593;b;
#define f(i,a)(cos(fmod(i,P))+1)/2*(a[b=i/P-1]-a[++b])+a[b]

```

Try it online!

Calling code

```
int main() {
  float a[3] = {1.3,3.7,6.9};
  printf("%f\n", f(5.3,a));
}

```

note that it needed the compiler flag `-lm` to link with math libraries, so +3 bytes if you count that.
> 0 votes

# Answer
# Attache, 54 bytes

```
${Cos[y%PI/2]^2*&`-@(j:=x[1'-1*Floor[y'-y/PI]-1])+j@1}

```

Try it online!

## Explanation

```
${Cos[y%PI/2]^2*&`-@(j:=x[1'-1*Floor[y'-y/PI]-1])+j@1}
${                                                   }  parameters: x, y
  Cos[y%PI/2]^2                                         the scaling function factor
               *                                        times
                     j:=                                set j to
                        x[                     ]        the element in x at
                          1'-1*Floor[y'-y/PI]-1         the closest indices scaled by PI
                &`-@(                           )       spread subtraction over bounds
                                                 +j@1   add the upper bound

```
> 0 votes

---
Tags: code-golf, array
---


# Question
Title: Linear dependences over the field with two elements
The \\$d\\$-dimensional vector space \\$\mathbb{F}\_2^d\\$ over the field with two elements \\$\mathbb{F}\_2\\$ is the set of vectors of \\$d\\$ bits. Addition of vectors is bitwise xor. A linear dependence is a set of vectors whose total (xor them all together) is \\$0\\$. Every set of \\$d+1\\$ vectors in \\$\mathbb{F}\_2^d\\$ contains a linear dependence. We will represent the elements of \\$\mathbb{F}\_2^d\\$ as the integers \\$0\\$ through \\$2^{d}-1\\$ using the binary expansion.

## Task

Input: a positive integer \\$d\\$ and a list of \\$d+1\\$ positive integers between \\$1\\$ and \\$2^{d}-1\\$. You may assume that the list is sorted and you may assume that the entries are distinct.

Output: A nonempty subset of the \\$d+1\\$ numbers whose bitwise xor is zero.

## Scoring:

This is code golf so shortest answer in bytes wins.

## Examples:

```
Input: (3, [1,3,4,7])
Output: [3, 4, 7]

```

In binary, these are 001, 011, 100, and 111. We see that 100 xor 011 xor 111 = 000. In this case this is the only solution, so we must output \[3, 4, 7\].

## Test cases:

```
Input: (3, [1,3,4,7])
Output: [3, 4, 7]

Input: (4, [1, 2, 6, 10, 30])
Output: Behavior undetermined because 30 > 15 = 2^4 - 1.

Input: (5, [3, 5, 6, 9, 14])
Output: [3, 5, 6]

Input: (5, [4, 8, 10, 12, 14])
Output: [4, 8, 12] or [4, 10, 14], or [8, 10, 12, 14].

Input: (6, [4, 15, 17, 21, 49, 51, 57])
Output: [4, 17, 21]

Input: (6, [1, 7, 8, 15, 39, 55, 57])
Output: [7, 8, 15] or [1, 15, 55, 57] or [1, 7, 8, 55, 57]

Input: (6, [13, 14, 24, 33, 35, 36, 63])
Output: [13, 14, 24, 36, 63]

Input: (6, [10, 11, 25, 28, 40, 59, 62])
Output: [10, 25, 40, 59] or [10, 28, 40, 62], or [25, 28, 59, 62]

Input: (6, [1, 3, 5, 11, 19, 32, 63])
Output: [1, 3, 5, 11, 19, 32, 63]

```

# Answer
# Jelly, 7 bytes

```
ŒPḊ^/ÞḢ

```

A monadic Link accepting the list of distinct integers representing the vectors which yields a subset representing the linear dependence. (May be employed as a dyadic Link also accepting the number of dimensions on the right.)

**Try it online!**

### How?

```
ŒPḊ^/ÞḢ - Link: list of distinct integers   e.g. [1,3,4,7]
ŒP      - power-set                              [[],[1],[3],[4],[7],[1,3],[1,4],[1,7],[3,4],[3,7],[4,7],[1,3,4],[1,3,7],[1,4,7],[3,4,7],[1,3,4,7]],[3,4,7],[1,3,4,7]]
  Ḋ     - dequeue                                [[1],[3],[4],[7],[1,3],[1,4],[1,7],[3,4],[3,7],[4,7],[1,3,4],[1,3,7],[1,4,7],[3,4,7],[1,3,4,7]],[3,4,7],[1,3,4,7]]
     Þ  - sort by:
    /   -   reduce by:
   ^    -     XOR                              ( [1,3,4,7,2,5,6,7,4,3,6,5,2,0,1] )
        - }                                      [[3,4,7],[1],[1,3,4,7],[1,3],[1,4,7],[3],[4,7],[4],[3,7],[1,4],[1,3,7],[1,7],[1,3,4],7,[3,4]]
      Ḣ - head                                   [3,4,7]

```
> 6 votes

# Answer
# Perl 6, 39 bytes

```
{first {![+^] $_},.combinations(1..$_)}

```

Try it online!

Returns the first combination of the input that is zero when reduced XOR. I wish `{![+^] $_}` could be changed to `!*.&[+^]`.
> 5 votes

# Answer
# Pyth, 6 bytes

```
hxFDty

```

Try it online!

To explain, back to front:

* `y` generates all subsets of the input.
* `t` (tail) removes the first, empty subset.
* `D` means order by the following function:
* `F` means reduce on:
* `x` is the xor function.
* `h` (head) takes the first element of the sorted list.

The lists that xor to 0 will be sorted to the front.
> 5 votes

# Answer
# Haskell, 79 bytes

```
import Data.Bits
p[a]=[[a]]
p(a:b)=map(a:)(p b)++p b
filter((1>).foldl xor 0).p

```

Try it online!

Defines the power set (ignoring the empty set) as `p`, then our solution is:

```
filter((1>).foldl xor 0).p

```

Or in english:

> Get the power set and then select all the members whose xor sum is less than 1 (i.e. zero).
> 3 votes

# Answer
# 05AB1E, 8 bytes

```
æ¦.Δ.»^>

```

**Try it online!**

### How?

```
æ¦.Δ.»^> - implicitly take input
æ        - power-set
 ¦       - tail
  .Δ     - keep first which is 1 under:
    .»   -   reduce by:
      ^  -     XOR
       > -   increment
         - implicit print

```
> 3 votes

# Answer
# Python 3.8, 74 bytes

```
f=lambda a,s=[],v=0:s*(v<1)or a and(f(n:=a[1:],s+a[:1],v^a[0])or f(n,s,v))

```

**Try it online!**
> 3 votes

# Answer
# JavaScript (ES6),  ~~84 60~~  58 bytes

Ignores \\$d\\$. Returns \\$0\\$ if there's no solution.

```
f=([v,...a],x,o=[])=>x<1?o:v?f(a,x,o)||f(a,x^v,[...o,v]):0

```

Try it online!

### Commented

```
f = (                        // f is a recursive function taking:
  [v,                        //   v   = next value from the input set
      ...a],                 //   a[] = array of remaining values
  x,                         //   x   = 'XOR total', initially undefined
  o = []                     //   o[] = output subset
) =>                         //
  x < 1 ?                    // if x is defined and equal to 0:
    o                        //   success: return o[]
  :                          // else:
    v ?                      //   if v is defined:
      f(a, x, o) ||          //     try a recursive call where v is ignored
      f(a, x ^ v, [...o, v]) //     try a recursive call where v is used
    :                        //   else:
      0                      //     failed

```
> 2 votes

# Answer
# Ruby, 78 bytes

```
f=->a{(1..a.size).map{|x|a.combination(x).map{|x|return x if x.reduce(:^)<1}}}

```

Try it online!

:^)

Probably golfable.
> 2 votes

# Answer
# , 36 bytes

```
0-.~1{ ::0[:(#~0=XOR/"1)]#~2#:@i.@^#

```

Try it online!
> 2 votes

# Answer
# Mathematica, 61 bytes

```
f[d_,l_]:=NullSpace[IntegerDigits[#,2,d]&/@l,Modulus->2][[1]]

```

This gives a bitmask (well a list of zeros and ones) of which elements of the list are in the set, as was allowed by the OP.
> 2 votes

# Answer
# Mathematica, 38 bytes

```
Select[Rest@Subsets@#,BitXor@@#==0&]&

```

Returns the list of solutions or an empty list if no solutions exist.

Try it online!
> 2 votes

# Answer
# x86 machine code, 27 bytes

```
578B7C240831C04031D231C90FA3C8730333148F67E2F575EE5FC3

```

Iterating through bit masks and XORing together the items as selected by the mask. In MASM-format assembly:

```
_lindep PROC
    push edi
    mov edi, [esp + 8]
    xor eax, eax
_loop:
    inc eax
    xor edx, edx
    xor ecx, ecx
_inner:
    bt eax, ecx
    jnc _skip
    xor edx, [edi + 4 * ecx]
_skip:
    byte 67h
    loop _inner
    jnz _loop
    pop edi
    ret
_lindep ENDP

```

It's a cdecl function, not stdcall.

There is an odd requirement: the input array must be padded to 65536 items long, but only 32 items are actually used. That's because I used a 16-bit `loop` and relied it on it wrapping from 0 to 65535, The padding has to exist in order to make the program not die with an access violation.

Using `loop` this way, in addition to gaining the benefit from it being small, means the zero flag is not modified between the `xor` and the `jnz` of the outer loop. Almost any other construct would need an extra instruction just to re-test whether `edx` is zero, except using `lea` to increment the loop counter and `bt ecx, 5` to stop when it hits 32, which is bigger.

Driver program in case you want to run it:

```
#include <iostream>
extern "C" int lindep(int* vecs, int d);
int vecs[65536] = { 1, 3, 4, 7 };
int main()
{
    std::cout << lindep(vecs, 3) << "\n";
}

```
> 1 votes

# Answer
# Charcoal, 32 bytes

```
ＩΦＥＸ²ＬθΦθ﹪÷ιＸ²μ²∧ι⬤↨⌈θ²¬﹪Σ÷ιＸ²μ²

```

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

```
    ²                               Literal 2
   Ｘ                                Raised to power
      θ                             Input array
     Ｌ                              Length
  Ｅ                                 Map over implicit range
        θ                           Input array
       Φ                            Filtered where nonzero
           ι                        Outer index
          ÷                         Integer divide by
             ²                      Literal 2
            Ｘ                       Raised to power
              μ                     Inner index
         ﹪                          Modulo
               ²                    Literal 2
 Φ                                  Filter powerset where
                 ι                  Current subset (is not empty)
                ∧                   Logical And
                     θ              Input array
                    ⌈               Maximum
                   ↨                Convert to base
                      ²             Literal 2
                  ⬤                 Has all values where
                           ι        Current powerset
                          ÷         Vectorised integer divide by
                             ²      Literal 2
                            Ｘ       Raised to power
                              μ     Inner index
                         Σ          Sum
                        ﹪           Modulo
                               ²    Literal 2
                       ¬            Is zero
Ｉ                                   Cast to string
                                    Implicitly print

```
> 1 votes

# Answer
# Burlesque, 16 bytes

```
peR@{{$$}r[n!}fe

```

Try it online!

Takes arguments as `d {1 2 3 4...}`

```
pe      # Read vals and push to stack
R@      # Generate all subsets
{
 {$$}r[ # Reduce by xor
 n!     # Boolean not
}fe     # Find first element

```
> 1 votes

---
Tags: code-golf, abstract-algebra, linear-algebra
---


title: Is this quadrilateral tangential?

text:
# Question
Title: Is this quadrilateral tangential?
Related: Is this quadrilateral cyclic?

## Background

A tangential quadrilateral is a quadrilateral which has an incircle:

Examples include any square, rhombus, or a kite-like shape. Rectangles or parallelograms in general are not tangential.

## Task

Given the four vertices of a quadrilateral (as Cartesian coordinates), determine if it is tangential.

## Input & output

For input, it is allowed to use any format that unambiguously specifies the four vertices' coordinates (eight real or floating-point numbers). You can assume the following on the input:

* The points specify a simple convex quadrilateral, i.e. all internal angles are strictly less than 180 degrees, and the edges meet only at the vertices.
* The points are specified in counter-clockwise order (or the other way around if you want).

For output, you can use one of the following:

* Truthy/falsy values as defined by your language of choice (swapping the two is allowed), or
* Two consistent values for true/false respectively.

It is acceptable if your code produces wrong output due to floating-point inaccuracies.

## Test cases

### Tangential

```
(0, 0), (0, 1), (1, 1), (1, 0)  # unit square
(-2, 0), (0, 1), (2, 0), (0, -1)  # rhombus
(1, -2), (-2, -1), (-1, 2), (4, 2)  # kite
(0, 0), (50, 120), (50, 0), (32, -24)  # all four sides different

```

### Not tangential

```
(0, 0), (0, 1), (2, 1), (2, 0)  # rectangle
(0, 0), (1, 1), (3, 1), (2, 0)  # parallelogram

```

## Scoring & winning criterion

Standard rules apply. The shortest code in bytes wins.

# Answer
# MATL, ~~11~~ 10 bytes

```
5:)d|2e!sd

```

Input is a vector of four complex numbers. Output is `0` (which is falsy) if tangential, or nonzero (which is truthy) if not tangential.

Try it online! Or verify all test cases.

### Explanation

The code computes the difference between sums of lengths of opposite sides. This difference is zero if and only if the quatrilateral is tangential.

```
5:   % Range [1 2 3 4 5]
)    % Implicit input: complex vector of length 4. Index into it modularly.
     % This repeats the first vertex after the last
d    % Consecutive differences
|    % Absolute value, element-wise
2e   % Reshape as a 2-column matrix, in column-major order
!    % Transpose
s    % Sum of each column. Gives a vector of length 2
d    % Consecutive difference

```
> 11 votes

# Answer
# Python 3, ~~89~~ \\$\cdots\\$ ~~59~~ 55 bytes

```
lambda l:sum((-1)**i*abs(l[i-1]-l[i])for i in range(4))

```

Try it online!

A list of vertices as complex numbers is passed in. The lengths of the sides \\$(a, b, c, d)\\$ are calculated and uses \\$a+c=b+d\\$ for a tangential quadrilateral. Returns's a falsy value (0) for a tangential or a truthy value (nonzero) otherwise.
> 5 votes

# Answer
# Python 3, 47 bytes

```
f=lambda l,i=3:i+1and abs(l[i]-l[i-1])-f(l,i-1)

```

Try it online!

Take complex number input. Outputs as Truthy/Falsey swapped. Test cases from Noodle9.

---

**48 bytes**

```
lambda a,b,c,d:A(a-b)+A(c-d)-A(b-c)-A(d-a)
A=abs

```

Try it online!
> 5 votes

# Answer
# Jelly, ~~9~~ 8 bytes

```
ṁ5ạƝŒœ§E

```

Try it online!

## Explanation

```
5ị€       | Modular index 1,2,3,4,5 into list
   ạƝ     | Absolute difference of neighbouring pairs
     Œœ   | Split into odd and even indices
       §  | Sum of inner lists
        E | Equal

```

A monadic link taking a list of complex coordinates and returning 1 for tangential and 0 for not.

Based on @LuisMendo’s MATL answer so be sure to upvote that one!

Thanks to @JonathanAllan for saving a byte!
> 4 votes

# Answer
# JavaScript (ES6), 74 bytes

Takes input as a list of coordinate pairs. Returns \\$0\\$ (falsy) for tangential or a non-zero value (truthy) for non-tangential.

```
a=>(g=_=>Math.hypot(([x,y]=a[i],[X,Y]=a[++i&3],x-X),y-Y))(i=0)-g()+g()-g()

```

Try it online!
> 2 votes

# Answer
# APL (Dyalog Unicode), ~~17~~ 11 bytesSBCS

-6 bytes thanks to Bubbler

outputs 1 if tangential, 0 if not

```
0=-/|2-/5⍴⎕

```

Try it online!

Explanation:

```
0=-/|2-/5⍴⎕

          ⎕ take 4 complex numbers as evaluated input
        5⍴   reshape to 5
     2-/     difference between each pair of numbers
    |        absolute value
  -/         alternating sum
0=           the quadrilateral is tangential if the final result is 0

```

## Previous answer

```
=/+/⍉2 2⍴|2-/5⍴⎕

```

Try it online!

Explanation:

```
=/+/⍉2 2⍴|2-/5⍴⎕

                ⎕  take 4 complex numbers as evaluated input
              5⍴    reshape to 5
           2-/      find the difference between each pair of numbers
          |         absolute value
      2 2⍴          reshape to 2x2 matrix
    ⍉              transpose
  +/                sum the rows
=/                  are they both equal?

```
> 2 votes

# Answer
# Wolfram Language (Mathematica), 24 bytes

Returns `Sphere` if the quadrilateral is tangential, `Insphere` if it is not.

```
Head@Insphere@Polygon@#&

```

Try it online!

---

# Wolfram Language (Mathematica), 38 bytes

Returns `True` if the quadrilateral is tangential, `False` if it is not.

```
0=={1,-1,1,-1}.Norm/@(#-RotateLeft@#)&

```

Try it online!
> 1 votes

# Answer
# 05AB1E, 9 bytes

```
ĆüαnOtιOË

```

Try it online!

Port of Nick Kennedy's Jelly answer. It turned out pretty short, despite 05AB1E's lack of complex numbers.
> 1 votes

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


# Question
Title: Decomposition of a matrix in \$ SL_2(\mathbb{Z}) \$
## Background

The special linear group \\$ SL\_2(\mathbb{Z}) \\$ is a multiplicative group of \\$ 2 \times 2 \\$ matrices whose elements are integers and determinant is 1.

It is known that every member of \\$ SL\_2(\mathbb{Z}) \\$ is a product of some sequence of the following two matrices \\$ S \\$ and \\$ T \\$ (reference pdf):

$$ S=\begin{pmatrix}0 & -1\\1 & 0\end{pmatrix},T=\begin{pmatrix}1 & 1\\0 & 1\end{pmatrix} $$

Note that \\$ S^{-1} \\$ and \\$ T^{-1} \\$ can also be expressed as a product of \\$ S \\$ and \\$ T \\$:

$$ S^{-1} = S^3, T^{-1} = S^3 \cdot T \cdot S \cdot T \cdot S $$

## Task

Given a \\$ 2 \times 2 \\$ integer matrix whose determinant is 1, express it as the product of a sequence of \\$ S \\$ and \\$ T \\$.

Note that there are infinitely many possible answers for any valid input. Your code needs to just output one answer for a valid input.

## Example algorithm

Here is a sample algorithm to find a decomposition; you may use different algorithms to solve the task.

First, note that

$$ M = \begin{pmatrix} a & b \\ c & d \end{pmatrix} \implies S^{-1}M = \begin{pmatrix} c & d \\ -a & -b \end{pmatrix}, T^{-1}M = \begin{pmatrix} a-c & b-d \\ c & d \end{pmatrix} $$

Using these two operations, we can use Euclidean-like algorithm to reduce the given matrix down to \\$ I \\$, and then construct the chain backwards:

1. Assume \\$ M = \begin{pmatrix} a & b \\ c & d \end{pmatrix} \\$.
2. Left-multiply \\$ S^{-1} \\$ until both \\$ a \\$ and \\$ c \\$ are positive.
3. Repeat the following until we reach \\$ c = 0 \\$:
    1. Left-multiply \\$ T^{-q} \\$ where \\$ -c \< a - qc \le 0 \\$.
    2. Left-multiply \\$ S^{-1} \\$ (exactly once). Now, \\$a\\$ and \\$c\\$ are positive again, and \\$c\\$ is smaller than the original.
4. Then the result is \\$ \begin{pmatrix} 1 & b \\ 0 & 1 \end{pmatrix} \\$, which is simply \\$ T^b \\$. (If \\$ b \< 0 \\$, we can use \\$ (SSSTSTS)^{-b} \\$ instead.) Now invert all the left-multiplications to get the representation for the original matrix.

Here is an example for \\$ M = \begin{pmatrix}17 & 29\\7 & 12\end{pmatrix} \\$.

$$ T^{-3} M = \begin{pmatrix}-4 & -7\\7 & 12\end{pmatrix} \\ S^{-1} T^{-3} M = \begin{pmatrix}7 & 12\\4 & 7\end{pmatrix} \\ T^{-2} S^{-1} T^{-3} M = \begin{pmatrix}-1 & -2\\4 & 7\end{pmatrix} \\ S^{-1} T^{-2} S^{-1} T^{-3} M = \begin{pmatrix}4 & 7\\1 & 2\end{pmatrix} \\ T^{-4} S^{-1} T^{-2} S^{-1} T^{-3} M = \begin{pmatrix}0 & -1\\1 & 2\end{pmatrix} \\ S^{-1} T^{-4} S^{-1} T^{-2} S^{-1} T^{-3} M = \begin{pmatrix}1 & 2\\0 & 1\end{pmatrix} = T^2 \\ M = T^3 S T^2 S T^4 S T^2 $$

## Input and output

You can take the input matrix in any suitable way, e.g. a matrix, a 4-element vector, two complex numbers, etc. You can assume that the input is always valid, i.e. the four elements are integers and the determinant is 1.

The output is a sequence of two distinct values (or objects) that represent \\$ S \\$ and \\$ T \\$ respectively. All of the following are accepted (using an example output \\$ STTS \\$):

```
"STTS"  # string
"0110"  # digit string
[0, 1, 1, 0]  # array of 0s and 1s
['S', 'T', 'T', 'S']  # array of characters
[(0,-1,1,0), (1,1,0,1), (1,1,0,1), (0,-1,1,0)]  # array of tuples

```

Also, by definition of empty product, an empty sequence (e.g. `""` or `[]`) is a valid answer when the input is \\$ I \\$.

## Scoring and winning criterion

Standard rules apply. Shortest code in bytes wins.

## Example I/O

Note that every valid input has infinitely many correct answers, so your code's output may differ from the sample outputs shown here.

```
[[1 0]
 [0 1]] -> empty or SSSS or SSSTSTST or ...

[[0 -1]
 [1  0]] -> S

[[1 10]
 [0  1]] -> TTTTTTTTTT

[[17 29]
 [ 7 12]] -> TTTSTTSTTTTSTT

[[-1  -7]
 [-2 -15]] -> SSTSTTSTSSTTTTSSTTT

```

# Answer
> 8 votes
# Python, 67 bytes

```
g=lambda z,w:(z/w).real>0and'T'+g(z-w,w)or z+w*w and'S'+g(w,-z)or''

```

Try it online!

*Thanks to Bubbler for cutting a byte*

Takes input as two complex numbers for the rows. The idea is simple and easy-to-see on a less-golfed version:

```
def f(a,b,c,d):
 if (a,b,c,d)==(1,0,0,1): return ''
 elif a*c+b*d>0: return 'T'+f(a-c,b-d,c,d)
 else: return 'S'+f(c,d,-a,-b)

```

From \\$ \begin{pmatrix} a & b \\ c & d \end{pmatrix}\\$, we choose whether to apply \\$S^{-1}\\$ or \\$T^{-1}\\$ based on a simple condition: whether \\$ac+bd\>0\\$. Repeating this enough times takes any matrix to the identity.

# Answer
> 7 votes
# JavaScript (ES6), 68 bytes

This is using xnor's method -- but obviously without complex numbers.

Takes the input matrix \\$\begin{pmatrix}a&b\\c&d\end{pmatrix}\\$ as 4 distinct parameters `a,b,c,d`.

Returns a string of digits (\\$0\\$ for \\$S\\$, \\$1\\$ for \\$T\\$).

```
f=(a,b,c,d)=>b|c|a-1|d-1?a*c>-b*d?1+f(a-c,b-d,c,d):0+f(c,d,-a,-b):''

```

Try it online!

---

# JavaScript (ES6),  ~~114 110~~  108 bytes

Takes the input matrix \\$\begin{pmatrix}a&b\\c&d\end{pmatrix}\\$ as a 4-element vector `[a,b,c,d]`.

Returns a string of digits (\\$0\\$ for \\$S\\$, \\$1\\$ for \\$T\\$).

Brute forces a solution, which is guaranteed to be as short as possible, except for the identity matrix.

```
f=(M,i=0)=>(F=(a,b,c,d,s='')=>s[i]?a+[,b,c,d]==M&&s:F(a,a+b,c,c+d,s+1)||F(b,-a,d,-c,s+0))(1,0,0,1)||f(M,i+1)

```

Try it online!

### Commented

```
f = (                      // f = wrapper function taking:
  M,                       //   M[] = input vector
  i = 0                    //   i   = maximum number of iterations (-1)
) => (                     //
  F = (                    // F is a recursive function taking:
    a, b, c, d,            //   the current matrix as 4 distinct parameters
    s = ''                 //   s = output string
  ) =>                     //
    s[i] ?                 // if we've reached the maximum length:
      a + [, b, c, d] == M //   if [a, b, c, d] matches the input matrix:
        && s               //     return s
    :                      // else:
      F(                   //   try a first recursive call
        a,                 //     where the matrix is multiplied by T
        a + b,             //     [ a b ]   [ 1 1 ]   [ a a+b ]
        c,                 //     [ c d ] x [ 0 1 ] = [ c c+d ]
        c + d,             //
        s + 1              //     append '1' to s
      ) ||                 //
      F(                   //   try a second recursive call
        b,                 //     where the matrix is multiplied by S
        -a,                //     [ a b ]   [ 0 -1 ]   [ b -a ]
        d,                 //     [ c d ] x [ 1  0 ] = [ d -c ]
        -c,                //
        s + 0              //     append '0' to s
      )                    //
)(1, 0, 0, 1)              // initial call to F with the identity matrix
|| f(M, i + 1)             // if it fails, try again with i + 1

```

# Answer
> 3 votes
# APL (Dyalog Extended), 47 bytesSBCS

Anonymous tacit prefix function. Gives Boolean list with 0 and 1 meaning \\$S\\$ and \\$T\\$ respectively.

```
{⍺≡⊃+.×/(r←⊤⍵)⊇2 2∘⍴¨(0 ¯1 1)(1 1 0):r⋄⍺∇1+⍵}∘1

```

Try it online! (Faster edition emulating Extended in Unicode.)

`{``}∘1` apply the following function with 1 and the given matrix as right and left arguments:

`(0 ¯1 1)(1 1 0)` the list `[[0,-1,1],[1,1,0]]`

`2 2∘⍴¨`**r**eshape each into a 2-by-2 matrix; `[[[0,-1],[1,0]],[[1,1],[0,1]]]`

`(``)⊇` select the following elements from that:

convert the right argument **T**o base **T**wo

`r←` store that in `r` (potential **r**esult)

`+.×/` reduce using matrix multiplication (this also reduces the number of dimensions from 1 to 0)

disclose (the enclosure necessitated to reduce the number of dimensions)

`⍺≡``:` if the left argument (the target matrix) matches that, then:

`r` return the **r**esult

else:

`1+⍵` increment the right argument

`⍺∇` call self with same left argument and new right argument

# Answer
> 2 votes
# 05AB1E, ~~48~~  ~~44~~  ~~43~~ 40 bytes

*Crossed out ` 44 ` is no longer 44 :)*

```
9bS[)DðýIk©d#¼vyDÁ0T·Sǝ+y2Å€(}2ôí˜]T¾ã®è

```

`9bS` and `DÁ0T·Sǝ+` could alternatively be `9Yв`/`т1ª`/`тĆS`/`TºS` and `D2ôO13Sǝ`/`DÁ2Å€0}+` for the same byte-count.

Brute-force approach with pretty bad performance (it times out for the last three test cases - the previous 48;44;43 bytes versions only timed out for the last test case).

Input \\$\begin{pmatrix}a&b\\c&d\end{pmatrix}\\$ as a space-delimited string of four integers `"a b c d"`.
Output as a string of `0`s and `1`s, where `0` is \\$S\\$ and `1` is \\$T\\$.

Try it online or verify a few test cases at once.

**Explanation:**

```
9bS                # Push 9, convert it to binary, and then to a digit-list: [1,0,0,1]
   [               # Start an infinite loop:
    )              #  Wrap all lists on the stack into a list
     D             #  Duplicate the current list of lists
      ðý           #  Join each inner list to a string with space delimiter
        Ik         #  Get the index of the input-string in this list
                   #  (the join is a work-around for lack of non-vectorizing index builtin)
          ©        #  Store it in variable `®` (without popping)
           d       #  Check if this index is non-negative (>= 0)
            #      #  And it it is: stop the infinite loop
    ¼              #  Increase the counter variable by 1
      v            #  Loop over each inner [a,b,c,d]-list `y`:
       yD          #   Push the list twice
         Á         #   Rotate the second one once towards the right: [a,b,c,d] → [d,a,b,c]
           T·S     #   Push 10 doubled as digit list: [2,0]
          0   ǝ    #   Insert a 0 at those (0-based) indices: [0,a,0,c]
               +   #   Add it to the earlier list: [a+0,b+a,c+0,d+c] → [a,b+a,c,d+c]
       y           #   Get the initial list [a,b,c,d] again
        2Å€ }      #   Apply to every 0-based 2nd item (so at indices [0,2]):
           (       #    Negate
             2ô    #   Split the list into parts of size 2: [-a,b,-c,d] → [[-a,b],[-c,d]]
               í˜  #   Reverse each, and flatten: → [[b,-a],[d,-c]] → [b,-a,d,-c]
   ]               # Close both the map and infinite loop
    T¾ã            # Take the cartesian product of 10 with the counter variable
                   #  i.e. 3 → ["111","110","101","100","011","010","001","000"]
       ®è          # And index variable `®` into this list
                   # (after which the result is output implicitly)

```

# Answer
> 2 votes
# MATL, ~~42~~ ~~38~~ 32 bytes

```
`@B"@?FT!tqh}IlhB]]Nq:"Y*]G-z}@B

```

The code enumerates all finite sequences that begin with `S`, and stops when a solution is found. It is sufficient to test sequences beginning with `S` because `S*S*S*S` equals the identity matrix (inspiration from @Adam's APL solution).

Outputs a binary sequence, where `1` corresponds to matrix `S` and `0` to matrix `T`. The produced solution is the first in lexicographical order.

Try it online!

# Answer
> 2 votes
# Python 3, ~~301~~ \\$\cdots\\$ ~~139~~ 129 bytes

```
def f(a,b,c,d,l=''):
 while c:
  while 0>a or b<0:a,b,c,d=c,d,-a,-b;l+='S'
  if c:q=-a//c;a+=q*c;b+=q*d;l+='T'*-q
 return l+'T'*b

```

Try it online!

Saved 18 bytes thanks to Arnauld!!!

Takes the 4 matrix elements as separate numbers as input and outputs a string of `'S'`s and `'T'`s.

# Answer
> 2 votes
# Jelly,  ~~24~~  22 bytes

```
⁽¬Pb3’s2$⁺⁸ṃæ×/⁼
0ç1#B

```

A monadic Link accepting the target matrix which outputs a list containing a single list of `1`s (\\$S\\$) and `0`s (\\$T\\$).
As a full program a Jelly representation of this list is printed.

Always yields a resulting equation with a leading \\$S\\$ (except for an input of \\$T\\$ itself).
Note that since \\$S^4=I\\$ this is always possible.

**Try it online!** (very slow in general).

### How?

Starts with `i=0` and increments `i` while the binary representation of `i` with digits \\$S\\$ (1) and \\$T\\$ (0) does not have a matrix-product equal to the input, then returns the normal binary representation (using 1s and 0s).

```
⁽¬Pb3’s2$⁺⁸ṃæ×/⁼ - Link 1: integer, i; target matrix, M
⁽¬P              - literal 2831
   b3            - to base three    [1,0,2,1,2,2,1,2]
     ’           - decrement        [0,-1,1,0,1,1,0,1]
      s2$        - split into twos  [[0,-1],[1,0],[1,1],[0,1]]
         ⁺       - repeat that      [[[0,-1],[1,0]],[[1,1],[0,1]]]
          ⁸ṃ     - base-decompression of i
                 -     -> i in binary using digits 1=[[0,-1],[1,0]] and 0=[[1,1],[0,1]]
            æ×/  - reduce by matrix-multiplication
               ⁼ - is equal to M?

0ç1#B            - Main Link: 2-by-2 target matrix with determinant 1, M
0                - initialise the left argument, say i, to 0
  1#             - count up finding the first match under:
 ç               -   last Link (1) as a dyad - i.e. f(i, M)
    B            - convert to binary

```

# Answer
> 0 votes
# Charcoal, 64 bytes

```
Ｗ∨§η⁰⊖§θ⁰¿‹⁰×§θ⁰§η⁰«TＵＭθ⁻κ§ηλ»«S≔±θι≔ηθ≔ιη»×TΠθ¿›⁰Πθ«SSS×TST±ΠθS

```

Try it online! Link is to verbose version of code. Based on the provided algorithm. Explanation:

```
Ｗ∨§η⁰⊖§θ⁰

```

Repeat while the first column is not `[1, 0]`.

```
¿‹⁰×§θ⁰§η⁰

```

If the product of the first column is positive...

```
«TＵＭθ⁻κ§ηλ»

```

... then print a `T` and subtract the second row from the first row...

```
«S≔±θι≔ηθ≔ιη»

```

... otherwise print an `S`, and swap the rows, while negating the second row.

```
×TΠθ

```

If the product of the first row is positive then print that many `T`s.

```
¿›⁰Πθ«

```

But if it is negative, then...

```
SSS×TST±ΠθS

```

... print `SSS`, the appropriate number of `TST`s, and a final `S`.

# Answer
> 0 votes
# Ruby, 96 bytes

```
->m{z=[['',1,0,0,1]];z.find{|a,q,w,e,r|z<<[a+?S,w,-q,r,-e]<<[a+?T,q,q+w,e,e+r];m==[q,w,e,r]}[0]}

```

Try it online!

Use the (brute) force.

# Answer
> 0 votes
# Python 3, ~~193~~ ~~192~~ 191 bytes

Takes in a 2D numpy array and returns a string of S and T. Uses the algorithm in the question.

```
import numpy
def g(m,x=0):
 if m[1,0]==0:y=m[0,1];return['T','SSSTSTS'][y<0]*abs(y)
 while(m[:,0]<[1,0]).any():x+=1;m=[[0,1],[-1,0]]@m
 q=-m[0,0]//m[1,0];return'S'*x+'T'*-q+g([[1,q],[0,1]]@m)

```

Try it online!

---
Tags: code-golf, math, matrix, linear-algebra
---


title: Expand a number

text:
# Question
Title: Expand a number
# Expand a number

Your task is to expand an integer greater than 0 in the following manner:

Split the number into decimal digits and for each digit generate a list according to these rules:

* if the digit is odd, the list starts with the digit and goes down to 1;
* if the digit is even, the list starts with the digit and goes up to 9.
* if the digit is 0, the list is empty.

Write down the lists for the odd numbers below the digits, and above for the even ones. Then top-align the columns and collect the digits in each row to make integers. As a final step add up the numbers to find the expansion of the number.

Here's an example of the above rules applied to 34607:

```
 9
 8
 79
 68
 57
346 7 ->  399 7 -> 3997 -> 9418
2   6     288 6    2886
1   5     177 5    1775
    4      66 4     664
    3      5  3      53
    2      4  2      42
    1         1       1

```

Here are the test cases:

```
1: 1
2: 44
3: 6
44: 429
217: 1270
911: 947
2345: 26114
20067: 3450
34875632: 70664504
9348765347634763: 18406119382875401

```

This is , so the shortest answers in bytes in each language win.

# Answer
# Jelly, 13 bytes

```
Dḟ0RrḂ?€9UZḌS

```

A monadic link taking and returning positive integers.

**Try it online!** or see the test-suite.

### How?

```
Dḟ0RrḂ?€9UZḌS - Link: positive integer           e.g. 702
D             - cast to a decimal list                [7,0,2]
  0           - literal zero                          0
 ḟ            - filter discard                        [7,2]
        9     - literal nine
       €      - for each:
      ?       -   if:
     Ḃ        -   ...condition: bit (modulo by 2)      1              ,0
   R          -   ...then: range ([1,...n])            [1,2,3,4,5,6,7],n/a
    r         -   ...else: inclusive range ([n,...9])  n/a            ,[2,3,4,5,6,7,8,9]
         U    - upend                                 [[7,6,5,4,3,2,1],[9,8,7,6,5,4,3,2]]
          Z   - transpose                             [[7,9],[6,8],[5,7],[4,6],[3,5],[2,4],[1,3],2]
           Ḍ  - cast from decimal lists               [79,68,57,46,35,24,13,2]
            S - sum                                   324

```
> 8 votes

# Answer
# Perl 6,  ~~68~~  66 bytes

```
{sum roundrobin(.comb».&{$_%2??($_...1)!!(9...+$_) if +$_})».join}

```

Try it

```
{sum roundrobin(.comb».&{[R,] $_%2??1..$_!!$_..9 if +$_})».join}

```

Try it

## Expanded:

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

  sum

    roundrobin( # grab from the sub lists in a round robin fashion

      .comb\             # split the input into digits
      ».&{               # for each digit do this

        [R,]             # reduce with reversed &infix:«,» (shorter than reverse)

              $_ % 2     # is the digit not divisible by 2?
          ??  1  .. $_   # from 1 to the digit
          !!  $_ ..  9   # from the digit to 9

        if +$_           # only do the above if the current digit isn't 0
                         # (has the effect of removing 0 from the list)
     }

    )».join     # join each of the sub-lists from roundrobin
}

```
> 4 votes

# Answer
# APL (Dyalog), 39 bytes

Full program body. Prompts for input from STDIN. Prints result to STDOUT.

```
+/10⊥¨0~⍨¨↓⍉↑{2|⍵:⌽⍳⍵⋄×⍵:⌽⍵,⍵↓⍳9⋄⍬}¨⍎¨⍞

```

Try it online!

To display the last test case correctly, `⎕FR` (**F**loating-point **R**epresentation) has been set to 128-bit Decimal and `⎕PP` (**P**rint **P**recision) has been set to 34 digits.

prompt for text input from STDIN

`⍎¨` execute each (gets each digit as a number)

`{` for each element, apply the following function where the argument is represented by :

`2|⍵:` if odd (lit. "if" division remainder when divided by 2), then:

reverse

the **ɩ**ntegers from 1 until

the argument

else

`×⍵:` if the argument is positive (lit. "if" signum), then:

reverse

the argument

`,` followed by

argument

elements dropped from

`⍳9` the the **ɩ**ntegers from 1 until 9

else

empty list

mix (combine) this list of lists into a single matrix, padding with zeros on the right

transpose

split this matrix into a list of lists

`0~⍨¨` remove all zeros from each list

`10⊥¨` convert each from base-10 to normal numbers (this collects the digits)

`+/` sum the numbers
> 3 votes

# Answer
# JavaScript (ES6), ~~88~~ ~~83~~ 82 bytes

```
f=(n,k=0)=>k<9&&+[...n+''].map(x=>+x&&(x=x&1?x:9-k<x||9)>k?x-k:'').join``+f(n,k+1)

```

### Note

`9 - k < x || 9` saves a byte over `9 - k >= x && 9` but generates `1` instead of `0` if the inequality is verified. It would be a problem if it leaded to `1 > k`, triggering the wrong path in the outer ternary. But it would mean that `k = 0` and therefore `9 - k = 9`, so we can't possibly have `9 - k < x` at the same time.

### Test cases

NB: Removed the last test case which exceeds JS number precision.

```
f=(n,k=0)=>k<9&&+[...n+''].map(x=>+x&&(x=x&1?x:9-k<x||9)>k?x-k:'').join``+f(n,k+1)

console.log(f(1))                // 1
console.log(f(2))                // 44
console.log(f(3))                // 6
console.log(f(44))               // 429
console.log(f(217))              // 1270
console.log(f(911))              // 947
console.log(f(2345))             // 26114
console.log(f(20067))            // 3450
console.log(f(34875632))         // 70664504
```
> 3 votes

# Answer
# Japt, 18 bytes

```
ì f ®òZu ª9 wÃy xì

```

Try it online!
> 3 votes

# Answer
# Java 11, ~~210~~ ~~209~~ ~~191~~ 181 bytes

```
n->{long r=0;var a="0".repeat(9).split("");for(int d:(n+"").getBytes())for(int k=0,x=d-48,y=9;x>0&(k<1||(d%2<1?y-->x:x-->1));a[k++]+=d%2<1?y:x);for(var q:a)r+=new Long(q);return r;}

```

Ok, this took quite a while (mainly because I made a mistake at first, so had to write down each step to better understand what I did wrong). Can most likely be golfed some more.

-18 bytes thanks to *@ceilingcat*.

**Explanation:**

Try it here.

```
n->{                             // Method with long as both parameter and return-type
  long r=0;                      //  Result-long `r`, starting at 0
  var a="0".repeat(9).split(""); //  String array `a`, filled with nine String zeroes
  for(int d:(n+"").getBytes())   //  Cast the input to a String,
                                 //   and loop over its codepoints as integers:
    for(int k=0,                 //   Row-index `k`, starting at
        x=d-48,                  //   Temp integer `x`, set to the current digit
        y=9                      //   Temp integer `y`, set to 9
        ;                        //   Inner loop, if:
         x>0                     //     The current digit is not a 0,
          &(k<1                  //     and if this is the first iteration,
             ||(d%2<1?           //     or if the digit is even:
                 y-->x           //      And `y` is larger than the digit
                                 //      (and afterwards decrease `y` by 1 with `y--`)
                :                //     or if the digit is odd:
                 x-->1));        //      And `x` is larger than 1
                                 //      (and afterwards decrease `x` by 1 with `x--`)
      a[k++]+=                   //    Append the current row with:
                                 //    (and afterwards increase `k` by 1 with `k++`)
       d%2<1?                    //     If the digit is even:
        y                        //      Append the row with `y`
       :                         //     Else (the digit is odd):
        x);                      //      Append the row with `x`
  for(var q:a)                   //  Loop over the String rows in the array:
    r+=new Long(q);              //   Convert it to a long, and add it to the result-sum
  return r;}                     //  Return the result

```
> 3 votes

# Answer
# Pip, 28 bytes

```
J_MS(RV{a?a%2?\,aa,tl}Ma)ZDx

```

Try it online!

### Explanation

```
                      Ma      Map this function to the digits of the 1st cmdline arg:
        a?                     If digit != 0:
          a%2?                  If digit is odd:
              \,a                Inclusive-range(digit)
                 a,t            Else (digit is even), range from digit to 10 (exclusive)
                    l          Else (digit is 0), empty list
     RV{             }         Apply reverse to the result before returning it
                              This gives us a list of lists like [9 8 7 6] or [3 2 1]
    (                   )ZDx  Zip, with a default value of empty string
J_MS                          Use map-sum to join each sublist and sum the results
                              Autoprint (implicit)

```

How the steps proceed with `34607` as the argument:

```
34607
[[1 2 3] [4 5 6 7 8 9] [6 7 8 9] [] [1 2 3 4 5 6 7]]
[[3 2 1] [9 8 7 6 5 4] [9 8 7 6] [] [7 6 5 4 3 2 1]]
[[3 9 9 "" 7] [2 8 8 "" 6] [1 7 7 "" 5] ["" 6 6 "" 4] ["" 5 "" "" 3] ["" 4 "" "" 2] ["" "" "" "" 1]]
[3997 2886 1775 664 53 42 1]
9418

```
> 2 votes

# Answer
# , ~~153~~ 146 bytes

```
function(n,m=n%/%10^(nchar(n):0)%%10)sum(strtoi(apply(sapply(m[m>0],function(x)c(r<-"if"(x%%2,x:1,9:x),rep("",9-sum(r|1)))),1,paste,collapse="")))

```

Try it online!

~~Sometimes, I can't tell if I'm just garbage at golfing, or if R is....~~ It's definitely me, saved 7 bytes thanks to user2390246, who reminded me of another way to extract digits (that I suggested myself).

You may replace `strtoi` with `as.double` to get `18406718084351604` for the last test case (which is wrong); R only has 32-bit integers.
> 2 votes

# Answer
# Pyth - 23 bytes

```
siRT.Tm*!!d@,}9d}d1dsMz

```

Test Suite.
> 2 votes

# Answer
# Haskell, ~~106~~ 104 bytes

```
import Data.List
f n=sum$map read$transpose$[reverse$[[c..'9'],['1'..c]]!!mod(read[c])2|c<-show n,c>'0']

```

Try it online!
> 2 votes

# Answer
# Perl 5, 120 + 1 (`-a`) = 121 bytes

```
$p=y/01357/ /r;$n=y/02468/ /r;map{$p=~s/9/ /g;$p=~s/\d/$&+1/ge;$n=~s/\d/$&-1/ge;$n=~s/0/ /g;@F=($p,@F,$n)}0..7;say for@F

```

Try it online!
> 1 votes

# Answer
# Python 2, 131 bytes

```
lambda n:sum(int(''.join(`n`for n in l if n))for l in map(None,*[range(n and(n%2*n or 9),(n%2<1)*~-n,-1)for n in map(int,`n*10`)]))

```

Try it online!
> 1 votes

# Answer
# 05AB1E, 16 bytes

```
0KεDÈi9ŸëL]íõζJO

```

Try it online or verify all test cases.

Or alternatively:

```
0KεDÈ8*>Ÿ{R}õζJO
0Kε9Ÿ¬L‚yèR}õζJO

```

**Explanation:**

```
0K        # Remove all 0s from the (implicit) input-integer
  ε       #  Map each digit to:
   D      #   Duplicate the digit
    Èi    #   If it's even:
      9Ÿ  #    Pop and push a list in the range [digit, 9]
     ë    #   Else (the digit is odd):
      L   #    Pop and push a list in the range [1, digit]
  ]       # Close both the if-else statement and map
   í      # Reverse each inner ranged list
     ζ    # Zip/transpose, swapping rows and columns,
    õ     # with an empty string as filler
      J   # Join each inner list together
       O  # And sum that list
          # (after which the result is output implicitly)

```
> 1 votes

# Answer
# Burlesque, 39 bytes

```
riXX:nz{J2dv{{9r@}{ro}}che!<-}m[tp)im++

```

Try it online!

```
ri      #Read as int
XX      #Return list of digits
:nz     #Filter for non-zero
{
 J2dv   #Divisible by 2?
 {
  {9r@} #Range a, 9
  {ro}  #Range 1, a
 }che!  #Run based on if divisible
 <-     #Reverse the range
}m[     #Apply to each digit
tp      #Transpose digits
)im     #Join each list into single int
++      #Sum each int

```
> 1 votes

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


title: A queen's walk across a spiral

text:
# Question
Title: A queen's walk across a spiral
In a far-off kingdom, a chess queen takes a daily walk across a spiral path, numbered from 1 to `n`, not caring to follow the spiral itself, but simply making queen's moves as she would on a chessboard. The queen is beloved by her subjects, and they make a note of every square she visits on her path. Given that the queen can start her walk on any square and ends it on any square, what is the shortest queen's walk that she can take?

**The challenge**

Given a spiral of integers on a rectangular grid, write a function that returns one of the **shortest** possible paths (counted by number of cells travelled) between two numbers on this spiral grid using a chess queen's moves.

For example, from `16` to `25`:

```
25 10 11 12 13
24  9  2  3 14
23  8  1  4 15
22  7  6  5 16
21 20 19 18 17

```

Some possible paths include `16, 4, 2, 10, 25` and `16, 5, 1, 9, 25`.

**Rules**

* The input will be any two positive integers.
* The output will be a path of integers (including both endpoints) across the spiral using only orthogonal and diagonal moves.
* The length of a path is counted by the number of cells travelled.
* Your answer may be a program or a function.
* This is code golf, so the smallest number of bytes wins.

As always, if the problem is unclear, please let me know. Good luck and good golfing!

**Test cases**

```
>>> queen_spiral(4, 5)
4, 5
>>> queen_spiral(13, 20)
13, 3, 1, 7, 20
>>> queen_spiral(14, 14)
14
>>> queen_spiral(10, 3)
10, 11, 3
>>> queen_spiral(16, 25)
16, 4, 2, 10, 25
>>> queen_spiral(80, 1)
80, 48, 24, 8, 1

```

# Answer
# APL (Dyalog Unicode), ~~59~~ 57 bytesSBCS

```
{v⍳+\v[⍺],↓⍉↑(|⍴¨×)⊃⍵⍺-.⊃⊂v←9 11∘○¨+\0,0j1*{⍵/⍨⌈⍵÷2}⍳⍺⌈⍵}

```

Try it online!

-2 bytes thanks to @ngn.

Anonymous function that accepts two endpoints as left and right arguments.

### Ungolfed & how it works

The queen moves diagonally first, so it is sufficient to pre-compute the coordinates of each number up to `max(start,end)`.

The coordinate-generating algorithm is inspired from several answers on the related challenge, but is slightly different from any of the existing answers:

* Given the necessary bound of 10
* Generate the 1-based range `r=1 2 3 4 5 6 7 8 9 10`
* Take the ceiling of half of each number `n=1 1 2 2 3 3 4 4 5 5`
* Replicate each item of `r` by `n`. `1 2 3 3 4 4 5 5 5 6 6 6 7 7 7 7 8 8 8 8 9 9 9 9 9 10 10 10 10 10`
* Take the cumulative sum of power of imaginary unit, with starting point of 0. (this part is common to various Python solutions to the linked challenge)

Then, once the vector of coordinates `v` is ready, we can easily convert between the spiral index and coordinates using `v[i]` and `v⍳coord` (finding the first index of `coord` in `v`).

```
⍝ Define a function; ⍺=start, ⍵=end
f←{
  ⍝ Construct a vector of spiral coordinates v
  v←9 11∘○¨+\0,0j1*{⍵/⍨⌈⍵÷2}⍳⍺⌈⍵
                             ⍺⌈⍵  ⍝ max of start, end
                            ⍳     ⍝ range of 1 to that number
                   {⍵/⍨⌈⍵÷2}  ⍝ for each number n of above, copy itself ceil(n/2) times
               0j1*  ⍝ raise imaginary unit to the power of above
           +\0,      ⍝ prepend 0 and cumulative sum
                     ⍝ (gives vector of coordinates as complex numbers)
    9 11∘○¨  ⍝ convert each complex number into (real, imag) pair
  v←         ⍝ assign it to v

  ⍝ Extract start and end coordinates
  a w←(⍺⊃v)(⍵⊃v)

  ⍝ Compute the path the Queen will take
  v⍳+\(⊂a),↓⍉↑(|⍴¨×)w-a
                    w-a  ⍝ coordinate difference (end-start)
              (|⍴¨×)     ⍝ generate abs(x) copies of signum(x) for both x- and y-coords
                         ⍝ e.g. 4 -> (1 1 1 1), ¯3 -> (¯1 ¯1 ¯1)
           ↓⍉↑  ⍝ promote to matrix (with 0 padding), transpose and split again
                ⍝ (gives list of steps the Queen will take)
    +\(⊂a),     ⍝ prepend the starting point and cumulative sum
                ⍝ (gives the path as coordinates)
  v⍳  ⍝ index into the spiral vector (gives the spiral numbers at those coordinates)
}

```
> 6 votes

# Answer
# Mathematica ~~615~~ 530 bytes

This constructs a number grid, converts it into a graph, and then finds a shortest path between the two numbers that were input.

---

## UnGolfed

`numberSpiral` is from Mathworld Prime Spiral. It creates an n by n Ulam Spiral (without highlighting the primes).

`findPath` converts the number grid into a graph. Edges are valid queen moves on the number grid.

---

```
numberSpiral[n_Integer?OddQ]:=
  Module[{a,i=(n+1)/2,j=(n+1)/2,cnt=1,dir=0,len,parity,vec={{1,0},{0,-1},{-1,0},{0,1}}},a=Table[j+n(i-1),{i,n},{j,n}];Do[Do[Do[a[[j,i]]=cnt++;{i,j}+=vec[[dir+1]],{k,len}];dir=Mod[dir+1,4],{parity,0,1}],{len,n-1}];a];

findPath[v1_, v2_] :=
  Module[{f, z, k},
    (*f  creates edges between each number and its neighboring squares *)
    f[sp_,n_]:=n<->#&/@(sp[[Sequence@@#]]&/@(Position[sp,n][[1]]/.{r_,c_}:>Cases[{{r-1,c},{r+1,c},{r,c-1},{r,c+1},{r-1,c-1},{r-1,c+1},{r+1,c+1}, {r+1,c-1}},{x_,y_}/; 0<x<k&&0<y<k]));k=If[EvenQ[
     z=\[LeftCeiling]Sqrt[Sort[{v1, v2}][[-1]]]\[RightCeiling]],z+1,z];
    FindShortestPath[Graph[Sort/@Flatten[f[ns=numberSpiral[k],#]&/@Range[k^2]] //Union],v1,v2]]

```

---

## Examples

```
findPath[4,5]
findPath[13,22]
findPath[16,25]
numberSpiral[5]//Grid

```

{4,5}

{13,3,1,7,22}

{16,4,1,9,25}

---

The shortest path from 80 to 1 contains 5, not 6, vertices.

```
findPath[80,1]
numberSpiral[9]//Grid

```

{80, 48, 24, 8, 1}

---

## Golfed

```
u=Module;
w@n_:=u[{a,i=(n+1)/2,j=(n+1)/2,c=1,d=0,l,p,v={{1,0},{0,-1},{-1,0},{0,1}}},
a=Table[j+n(i-1),{i,n},{j,n}];
Do[Do[Do[a[[j,i]]=c++;{i,j}+=v[[d+1]],{k,l}];d=Mod[d+1,4],{p,0,1}],{l,n-1}];a];
h[v1_,v2_]:=u[{f,z},
s_~f~n_:=n<->#&/@(s[[Sequence@@#]]&/@(Position[s,n][[1]]/.{r_,c_}:>
Cases[{{r-1,c},{r+1,c},{r,c-1},{r,c+1},{r-1,c-1},{r-1,c+1},{r+1,c+1},{r+1,c-1}},{x_,y_}/;0<x<k&&0<y<k]));
k=If[EvenQ[z=\[LeftCeiling]Sqrt[Sort[{v1,v2}][[-1]]]\[RightCeiling]],z+1,z];
FindShortestPath[g=Graph[Sort/@Flatten[f[ns=w@k,#]&/@Union@Range[k^2]]],v1,v2]]

```
> 3 votes

# Answer
# Scala (830 bytes)

Builds the spiral in a square 2D array using four mutually recursive functions. Another recursive search to build the path list.

```
def P(s:Int,e:Int):List[Int]={
import scala.math._
type G=Array[Array[Int]]
type I=Int
type T=(I,I)
def S(z:I)={def U(g:G,x:I,y:I,c:I,r:I):Unit={for(i<-0 to r.min(y)){g(y-i)(x)=c+i}
if(r<=y)R(g,x,y-r,c+r,r)}
def R(g:G,x:I,y:I,c:I,r:I)={for(i<-0 to r){g(y)(x+i)=c+i}
D(g,x+r,y,c+r,r+1)}
def D(g:G,x:I,y:I,c:I,r:I)={for(i<-0 to r){g(y+i)(x)=c+i}
L(g,x,y+r,c+r,r)}
def L(g:G,x:I,y:I,c:I,r:I)={for(i<-0 to r){g(y)(x-i)=c+i}
U(g,x-r,y,c+r,r+1)}
val g=Array.ofDim[I](z,z)
U(g,z/2,z/2,1,1)
g}
def C(n:I,g:G):T={var(x,y)=(0,0)
for(i<-g.indices){val j=g(i).indexOf(n)
if(j>=0){x=j
y=i}}
(x,y)}
def N(n:Int)=if(n==0)0 else if(n<0)-1 else 1
def Q(a:T,b:T):List[T]={val u=N(b._1-a._1)
val v=N(b._2-a._2)
if(u==0&&v==0)b::Nil else a::Q((a._1+u,a._2+v),b)}
val z=ceil(sqrt(max(s,e))).toInt|1
val p=S(z)
Q(C(s,p),C(e,p)).map{case(x,y)=>p(y)(x)}}

```

## Ungolfed

```
  import scala.math._
  type Grid=Array[Array[Int]]
  def spiral(size: Int) = {
    def up(grid:Grid, x: Int, y: Int, c: Int, r: Int): Unit = {
      for (i <- 0 to r.min(y)) {
        grid(y-i)(x) = c + i
      }
      if (r <= y)
        right(grid,x,y-r,c+r,r)
    }
    def right(grid:Grid, x: Int, y: Int, c: Int, r: Int) = {
      for (i <- 0 to r) {
        grid(y)(x+i) = c + i
      }
      down(grid,x+r,y,c+r,r+1)
    }
    def down(grid:Grid, x: Int, y: Int, c: Int, r: Int) = {
      for (i <- 0 to r) {
        grid(y+i)(x) = c + i
      }
      left(grid,x,y+r,c+r,r)
    }
    def left(grid:Grid, x: Int, y: Int, c: Int, r: Int) = {
      for (i <- 0 to r) {
        grid(y)(x-i) = c + i
      }
      up(grid,x-r,y,c+r,r+1)
    }
    val grid = Array.ofDim[Int](size,size)
    up(grid,size/2,size/2,1,1)
    grid
  }
  def findPath(start: Int, end: Int): List[Int] = {
    def findCoords(n: Int, grid: Grid): (Int, Int) = {
      var (x,y)=(0,0)
      for (i <- grid.indices) {
        val j = grid(i).indexOf(n)
        if (j >= 0) {
          x = j
          y = i
        }
      }
      (x,y)
    }
    def sign(n: Int) = if (n == 0) 0 else if (n < 0) -1 else 1
    def path(stc: (Int, Int), enc: (Int, Int)) : List[(Int, Int)] = {
      val dx = sign(enc._1 - stc._1)
      val dy = sign(enc._2 - stc._2)
      if (dx == 0 && dy == 0) {
        enc :: Nil
      } else {
        stc :: path((stc._1 + dx, stc._2 + dy), enc)
      }
    }
    val size = ceil(sqrt(max(start, end))).toInt | 1
    val spir = spiral(size)
    path(findCoords(start, spir),findCoords(end, spir)).
      map { case (x, y) => spir(y)(x) }
  }

```
> 2 votes

# Answer
# Ruby, ~~262~~ ~~218~~ 216 bytes

This is a port of my Python answer. Golfing suggestions welcome.

**Edit:** 45 bytes thanks to Jordan and their suggestions of `d=[0]*n=m*m;*e=c=0;*t=a`, `.rect`, `0<=>x` and `x,y=(e[a]-g=e[b]).rect; t<<d[(g.real+x)*m+g.imag+y]`. Another byte from `(x+y*1i)` to `(x+y.i)`.

```
->a,b{m=([a,b].max**0.5).to_i+1;d=[0]*n=m*m;*e=c=0;*t=a
n.times{|k|d[c.real*m+c.imag]=k+1;e<<c;c+=1i**((4*k+1)**0.5-1).to_i}
x,y=(e[a]-g=e[b]).rect
(x+=0<=>x;y+=0<=>y;t<<d[(g.real+x)*m+g.imag+y])while(x+y.i).abs>0
t}

```

Ungolfed:

```
def q(a,b)
  m = ([a,b].max**0.5).to_i+1
  n = m*m
  d = [0]*n
  c = 0
  *e = c   # same as e=[0]
  *t = a   # same as t=[a]

  (1..n).each do |k|
    d[c.real * m + c.imag] = k+1
    e << c
    c += 1i**((4*k+1)**0.5-1).to_i
  end

  x, y = (e[a] - g=e[b]).rect

  while (x+y.i).abs > 0 do
    if x<0
      x += 1
    elsif x>0
      x += -1
    end

    if y<0
      y += 1
    elsif y>0
      y -= 1
    end

    t << d[(g.real+x)*m+g.imag+y]
  end

  return t
end

```
> 2 votes

# Answer
# Python 3, 316 bytes

This answer looks at the coordinates of `a` and `b` on the spiral (using complex numbers) and adds the diagonal moves first, then the orthogonal moves.

```
def q(a,b):
 m=int(max(a,b)**.5)+1;d=[];c=0;e=[c];t=[a]
 for i in range(m):d+=[[0]*m]
 for k in range(m*m):d[int(c.real)][int(c.imag)]=k+1;e+=[c];c+=1j**int((4*k+1)**.5-1)
 z=e[a]-e[b];x,y=int(z.real),int(z.imag)
 while abs(x+y*1j):x+=(x<0)^-(x>0);y+=(y<0)^-(y>0);t+=[d[int(e[b].real)+x][int(e[b].imag)+y]]
 return t

```

**Ungolfed:**

```
def queen_spiral(a,b):
    square_size = int(max(a,b)**.5)+1
    complex_to_spiral = []
    complex = 0
    spiral_to_complex = [c] # add 0 first, so that it's 1-indexed later
    result = [a]

    for i in range(square_size):
        complex_to_spiral.append([0]*square_size) # the rows of the spiral

    for k in range(square_size**2):
        row = int(complex.real)
        column = int(complex.imag)
        complex_to_spiral[row][column] = k+1 # 1-indexing

        spiral_to_complex.append(complex)

        quarter_turns = int((4*k+1)**.5-1)
        complex += 1j**quarter_turns

    z = spiral_to_complex[a] - spiral_to_complex[b]
    v = spiral_to_complex[b]
    x, y = int(z.real), int(z.imag)
    r, s = int(v.real), int(v.imag)

    while abs(x+y*1j):
        if x < 0:
            x += 1
        elif x > 0:
            x += -1
        # else x == 0, do nothing
        if y < 0:
            y += 1
        elif y > 0:
            y += -1

        vertex = complex_to_spiral[r+x][s+y]
        result.append(vertex)
    return result

```
> 1 votes

---
Tags: code-golf, path-finding, chess
---


title: Drum fill generator

text:
# Question
Title: Drum fill generator
Create a program that generates a drum fill. Your program will output a pattern of `L` (left hand hits), 'R' (right hand hits), and `K` for kick drum hits.

## Rules

* The pattern must never have more than 2 of the same hits consecutively.
* The pattern must be loopable, so it mustn't have more than 2 of the same hits when it loops.
* Your program accepts 1 argument which is the length of the pattern. You can assume this will always be an integer \> 1.
* Program output must be random each time it's ran. It should be properly random each time, so that every combination is possible, so for an input of 2 for example: LR, LK, RL, RK, KL, KR all have a chance of being generated.
* IO can be used with any convenient method.
* Standard loopholes are forbidden.
* This is code-golf, so smallest program wins!

**Example valid output:**

```
RLRRKKLL
LRLLKKLR
LKKRLRKLRRKL
LRLR

```

**Example invalid output:**

```
LRLL // 3 characters when looped
LRLRRRLLR // 3 characters in a row
RRLRLLRR // 4 characters when looped

```

# Answer
> 6 votes
# 05AB1E, 15 bytes

```
…LRKãʒDJÅγà3‹}Ω

```

Try it online!

```
…LRK                # literal "LRK"
    ã               # strings made of `input` of those letters
     ʒ       }      # filter:
      DJ            #  concatenate the string with itself
        Åγ          #  run-length encode
          à         #  maximum (largest run length)
           3‹       #  less than 3?
              Ω     # get a random element

```

# Answer
> 7 votes
# Jelly, 15 bytes

```
“LRK”ṗ;`E3Ƥ$ÐṂX

```

A monadic Link accepting an integer which yields a list of characters.

**Try it online!**

### How?

Pretty similar to Nick Kennedy's Jelly answer...

```
“LRK”ṗ;`E3Ƥ$ÐṂX - Link: integer, n
“LRK”           - "LRK"
     ṗ          - Cartesian power (all length n strings with alphabet "LRK")
            ÐṂ  - keep those entries which are minimal under:
           $    -   last two links as a monad:
      ;`        -     concatenate with itself
         3Ƥ     -     for each infix of length 3:
        E       -       all equal?
              X - random element

```

# Answer
> 6 votes
# , 67 bytes

```
n=scan();while(max(rle(c(x<-sample(c("L","R","K"),n,T),x))$l)>2)0;x

```

Try it online!

A full program taking an integer, n and implicitly printing the drum pattern.

# Answer
> 4 votes
# Jelly, 16 bytes

```
“LRK”ṗ;`ŒɠṀ<ʋƇ3X

```

Try it online!

A monadic link taking the length \\$n\\$ and returning a Jelly string of the drum pattern. Like the other answers, assumes that \\$n \> 1\\$

## Explanation

```
“LRK”ṗ           | Cartesian power of "LRK" and n
            ʋƇ   | Keep those where the following is true:
      ;`         | - Concatenate to itself
        Œɠ       | - Lengths of runs
          Ṁ      | - Max
           <  3  | - Less than 3
               X | Pick one at random

```

# Answer
> 3 votes
# Python 3, ~~115~~ \\$\cdots\\$ ~~112~~ 104 bytes

```
from random import*
f=lambda n,s='L':any(b*3in s*3for b in'LRK')and f(n,''.join(choices('LRK',k=n)))or s

```

Try it online!

Saved a byte thanks to Chas Brown!!!
Saved 8 bytes thanks to Jonathan Allan!!!

# Answer
> 3 votes
# APL (Dyalog Unicode), 30 bytesSBCS

Anonymous tacit prefix function.

```
{'LRK'[?⍺⍴3]}⍣{~1∊≢¨3∪/⍺,2↑⍺}⍨

```

Try it online!

`{``}` apply the following function using the single argument also as left argument:

`'LRK'[``]` index into the string `"LRK"` using the following indices:

`⍺⍴3` reshape the number three into the length indicated by the left argument

`?` random indices in those ranges

`⍣{``}` keep applying that function until the following is true:

`2↑⍺` take the first two characters of the previously generated string

`⍺,` prepend the previously generated string

`3∪/` the unique elements in each window of width three (lit, the union-reduction)

`≢¨` the length of each set

`1∊` is one a member thereof?

`~` negate

# Answer
> 3 votes
# , 75 bytes

```
`?`=diff;n=scan();while(!all(??c(x<-sample(9+c(2,3,9),n,T),x)))0;LETTERS[x]

```

Try it online!

Rejection sampling until an allowable pattern is found. Samples \\$x\_i\\$ from the set \\$\\{11, 12, 18\\}\\$ (the positions in the alphabet of K, L, R). Agreeably, these numbers are such that a pattern is allowable iff \\$\forall i, (x\_{i+1}-x\_i)-(x\_i-x\_{i-1})\neq 0\\$. This condition is verified by calling `diff` twice (`diff` computes lagged differences, and here we want the lagged differences of the lagged differences).

# Answer
> 3 votes
# Ruby, 57 bytes

```
->x{0while /(.)\1\1/=~(w=(%w(L K R)*x).sample(x)*'')+w;w}

```

Try it online!

# Answer
> 2 votes
# JavaScript (ES6),  ~~77~~  74 bytes

Assumes that the input is greater than \\$1\\$.

```
n=>(g=s=>s[n-1]?/(.)\1\1/.test(s+s)?g``:s:g(s+'LRK'[Math.random()*3|0]))``

```

Try it online!

# Answer
> 2 votes
# Charcoal, 26 bytes

```
Ｎθ≔KηＷ⊙KLR№×η³×κ³≔⭆θ‽KLRηη

```

Try it online! Link is to verbose version of code. Hangs for an input of `1` (could be changed to output a random hit at a cost of 1 byte). Explanation:

```
Ｎθ

```

Input the number of hits.

```
≔Kη

```

Initialise the output to an illegal value.

```
Ｗ⊙KLR№×η³×κ³

```

Repeat while the output is illegal, determined by tripling the output and each of the three letters `K`, `L` and `R`, and checking whether one contains any of the others.

```
≔⭆θ‽KLRη

```

Assign the desired number of randomly selected letters to the output.

```
η

```

Output the final legal result.

# Answer
> 2 votes
# Perl 5 `-pa`, 86 bytes

```
$_=R x("@F"+2);1while s|(.)(?=\1\1)|(R,L,K)[rand 3]|e;s/..$//;($_.$_)=~/(.)\1\1/&&redo

```

Try it online!

# Answer
> 2 votes
# Ruby, 97 bytes

```
->x,y=->{[*1..x].map{%w[L R K].sample}}{a=y[];a=y[]while(a+a).chunk{|n|n}.any?{|_,e|e[2]};a.join}

```

Try it online!

This is a lambda function, which takes the length input as `x`. It creates a function `y` which generates a list of length `x` containing random characters from the list `["L", "R", "K"]`. It then checks to see if there are any repeating occurrences of more than 2, and if so recreates a random string.

The `chunk` method on an array groups consecutive elements.

I check for any repetitions on `(a+a)` (where `a` is the generated drum loop), to find any looping-round repetitions.

## Golfy Tricks

* Using `e[2]` instead of `e.size > 2` \- this works as everything is truthy in Ruby except `nil` and `false`, and indexing out of bounds in an array returns `nil`.
* Using `%w[L R K]` instead of `["L","R","K"]` or `[?L,?R,?K]` \- This is ruby's whitespace-separated word array.

# Answer
> 1 votes
# Red, ~~141~~ 112 bytes

```
func[n][until[s: copy""loop n[append s random/only"LRK"]parse
rejoin[s s][any[copy t skip opt t ahead not t]]]s]

```

Try it online!

# Answer
> 1 votes
# Perl 6, 55 bytes

```
{({S:g{.}=<R L K>.pick}...{!/(.)$0$0/}o*x 2).tail}o\*x*

```

Try it online!

Anonymous code block that takes an integer and returns a string of `RKL`s.

### Explanation:

```
                                                  o\*x*  # Generate a string of n *s
{                                                }  # And pass to code block
 (                     ...                 ).tail   # Get the last element of the sequence
  {                   }      # Where each element is
   S:g{.}=       # Substitute each character of the previous string with
          <R K L>.pick   # A random character
                          {          }      # Until
                                      o*x 2 # The double of the string
                           !                # Does not
                            /(.)$0$0/       # Contain three of the same character in a row

```

# Answer
> 0 votes
# Burlesque, 43 bytes

```
pe"LRK"jCB{J?+gw)-]>]3.<}f[sa0#Rx/x/jrn-]!!

```

Try it online!

Made trickier by the fact there is no "select random element from list" as far as I am aware. 15 bytes are just trying to select a random element.

```
pe      # Push inputs onto stack takes "SEED N"
"LRK"   # Literal LRK
jCB     # Form all combinations of length N
{
 J?+    # Double string
 gw     # Zip with length of consecutive vals
 )-]    # Take length
 >]     # Maximum
 3.<    # Less than 3
}f[     # Filter for
sa0     # Find number of matches
#Rx/x/j # Fiddle stack to get SEED 0 num_matches
rn      # Gen random ints
-]!!    # Select the first

```

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