title: Palindromizing the strings

text:
# Question
Title: Palindromizing the strings
### Introduction

For the ones who don't know, a palindrome is when a string is equal to the string backwards (with exception to interpunction, spaces, etc.). An example of a palindrome is:

```
abcdcba

```

If you reverse this, you will end up with:

```
abcdcba

```

Which is the same. Therefore, we call this a palindrome. To palindromize things, let's take a look at an example of a string:

```
adbcb

```

This is not a palindrome. To palindromize this, we need to merge the reversed string into the initial string **at the right of the initial string**, leaving both versions intact. The shorter, the better.

The first thing we can try is the following:

```
adbcb
bcbda
^^ ^^

```

Not all characters match, so this is not the right position for the reversed string. We go one step to the right:

```
adbcb
 bcbda
 ^^^^

```

This also doesn't match all characters. We go another step to the right:

```
adbcb
  bcbda

```

This time, **all characters match**. We can *merge* both string *leaving the intact*. The final result is:

```
adbcbda

```

This is the *palindromized string*.

---

### The Task

Given a string (with at least one character) containing only **lowercase letters** (or uppercase, if that fits better), output the **palindromized string**.

---

### Test cases

```
Input     Output

abcb      abcba
hello     hellolleh
bonobo    bonobonob
radar     radar
hex       hexeh

```

This is , so the submission with the least amount of bytes wins!

# Answer
# Jelly, ~~11~~ 10 bytes

```
ṫỤfU$Ḣœ^;U

```

Try it online!

### How it works

```
ṫỤfU$Ḣœ^;U  Main link. Argument: s (string)

 Ụ          Yield all indices of s, sorted by their corr. character values.
ṫ           Tail; for each index n, remove all characters before thr nth.
            This yields the list of suffixes of s, sorted by their first character,
            then (in descending order) by length.
    $       Combine the two links to the left into a chain:
   U        Upend; reverse all suffixes.
  f         Filter; only keep suffixes that are also reversed suffixes.
            This gives the list of all palindromic suffixes. Since all of them
            start with the same letter, they are sorted by length.
     Ḣ      Head; select the first, longest palindromic suffix.
      œ^    Multiset symmetric difference; chop the selected suffix from s.
         U  Upend; yield s, reversed.
        ;   Concatenate the results to the left and to the right.

```
> 7 votes

# Answer
# Pyth (commit b93a874), 11 bytes

```
.VkI_IJ+zbB

```

Test suite

This code exploits a bug in the current version of Pyth, commit b93a874. The bug is that `_IJ+zb` is parsed as if it was `q_J+zbJ+zb`, which is equivalent to `_I+zb+zb`, when it should (by the design intention of Pyth) be parsed as `q_J+zbJ`, which is equivalent to `_I+zb`. This allows me to save a byte - after the bug is fixed, the correct code will be `.VkI_IJ+zbJB`. I'll explain that code instead.

Basically, the code brute forces over all possible strings until it finds the shortest string that can be appended to the input to form a palindrome, and outputs the combined string.

```
.VkI_IJ+zbJB
                z = input()
.Vk             For b in possible strings ordered by length,
       +zb      Add z and b,
      J         Store it in J,
    _I          Check if the result is a palindrome,
   I            If so,
          J     Print J (This line doesn't actually exist, gets added by the bug.
          B     Break.

```
> 15 votes

# Answer
## Python, 46 bytes

```
f=lambda s:s*(s==s[::-1])or s[0]+f(s[1:])+s[0]

```

If the string is a palindrome, return it. Otherwise, sandwich the first letter around the recursive result for the remainder of the string.

Example breakdown:

```
f(bonobo)
b  f(onobo) b
b o f(nobo) o b
b o n f(obo) n o b
b o n obo n o b

```
> 13 votes

# Answer
## Haskell, 36 bytes

```
f s|s==reverse s=s|h:t<-s=h:f t++[h]

```

More readably:

```
f s
 |s==reverse s = s
 |(h:t)<-s     = h:(f t)++[h]

```

If the string is a palindrome, return it. Otherwise, sandwich the first letter around the recursive result for the tail of the string.

The string `s` is split into `h:t` in the second guard, obviating a filler `1>0` for this case. This is shorter than doing `s@(h:t)` for the input.
> 9 votes

# Answer
# Pyth - ~~16~~ 12 bytes

*4 bytes saved thanks to @FryAmTheEggman.*

FGITW, much golfing possible.

```
h_I#+R_Q+k._

```

Test Suite.
> 5 votes

# Answer
# Brachylog, ~~16~~ ~~6~~ 5 bytes (Non-competing)

```
:Ac.r

```

Try it online!

When I posted my initial answer, it was still on the old implementation in Java. Since I have reprogrammed everything in Prolog, it now works as it should have in the first place.

### Explanation

```
(?):Ac.        Output is the concatenation of Input with another unknown string A
      .r(.)    The reverse of the Output is the Output

```

Backpropagation makes it so that the first valid value for `A` it will find will be the shortest that you can concatenate to Input to make it a palindrome.

### Alternate solution, 5 bytes

```
~@[.r

```

This is roughly the same as the above answer, except that instead of stating "Output is the concatenation of the Input with a string `A`", we state that "Output is a string for which the Input is a prefix of the Output".
> 5 votes

# Answer
# Retina, ~~29~~ 25

```
$
¶$_
O^#r`.\G
(.+)¶\1
$1

```

Try it online!

Big thanks to Martin for 11 bytes saved!

This just creates a reversed copy of the string and smooshes them together. The only really fancy part of this is the reversing method: `O^#r`.\G`, which is done by using sort mode. We sort the letters of the second string (the ones that aren't newlines and are consecutive from the end of the string, thanks to the `\G`) by their numeric value, which, since there are no numbers, is 0. Then we reverse the order of the results of this stable sort with the `^` option. All credit for the fancy use of `\G` belongs to Martin :)
> 4 votes

# Answer
## JavaScript (ES6), 92 bytes

```
(s,a=[...s],r=a.reverse().join``)=>s.slice(0,a.findIndex((_,i)=>r.startsWith(s.slice(i))))+r

```

Computes and slices away the overlap between the original string and its reversal.
> 4 votes

# Answer
# CJam, 18

```
q__,,{1$>_W%=}#<W%

```

Try it online

**Explanation:**

```
q         read the input
__        make 2 copies
,,        convert the last one to a range [0 … length-1]
{…}#      find the first index that satisfies the condition:
  1$>     copy the input string and take the suffix from that position
  _W%=    duplicate, reverse and compare (palindrome check)
<         take the prefix before the found index
W%        reverse that prefix
          at the end, the stack contains the input string and that reversed prefix

```
> 3 votes

# Answer
# Octave, ~~78~~ 75 bytes

Saved 3 bytes thanks to Eʀɪᴋ ᴛʜᴇ Gᴏʟғᴇʀ!

```
function p=L(s)d=0;while~all(diag(s==rot90(s),d++))p=[s fliplr(s(1:d))];end

```

ideone still fails for named functions, but here is a test run of the code as a program.
> 3 votes

# Answer
## Lua, ~~89~~ 88 Bytes

I beat the Javascript! \o/ **Saved 1 byte thanks to @LeakyNun ^^**

It's a full program, takes its input as command-line argument.

```
i=1s=...r=s:reverse()while s:sub(i)~=r:sub(0,#r-i+1)do i=i+1 end print(s..r:sub(#r-i+2))

```

## ungolfed

```
i=1                             -- initialise i at 1 as string are 1-indexed in lua
s=...                           -- use s as a shorthand for the first argument
r=s:reverse()                   -- reverse the string s and save it into r
while(s:sub(i)~=r:sub(0,#r-i+1))-- iterate while the last i characters of s
do                              -- aren't equals to the first i characters of r
  i=i+1                         -- increment the number of character to skip
end
print(s..r:sub(#r-i+2))         -- output the merged string

```
> 3 votes

# Answer
# Prolog, 43 bytes

```
a(S):-append(S,_,U),reverse(U,U),writef(U).

```

This expects a codes string as input, e.g. on SWI-Prolog 7: `a(`hello`).`

### Explanation

This is basically a port of my Brachylog answer.

```
a(S) :-               % S is the input string as a list of codes
    append(S,_,U),    % U is a list of codes resulting in appending an unknown list to S
    reverse(U,U),     % The reverse of U is U
    writef(U).        % Write U to STDOUT as a list of codes

```
> 3 votes

# Answer
# Perl, 37 bytes

Based on xnor's answer.

Includes +2 for `-lp`

Run with input on STDIN, e.g.

```
palindromize.pl <<< bonobo

```

`palindromize.pl`:

```
#!/usr/bin/perl -lp
s/.//,do$0,$_=$&.$_.$&if$_!~reverse

```
> 2 votes

# Answer
# Vyxal, 2 bytes

```
Ṙ⋎

```

Try it Online!

```
 ⋎ # Merge on longest prefix/suffix with...
Ṙ  # Input reversed

```
> 2 votes

# Answer
# 05AB1E, 18 bytes

Code:

```
Â©gF¹ðN×®«ðñD®åi,q

```

Uses **CP-1252** encoding. Try it online!
> 1 votes

# Answer
## Pyke, 15 bytes

```
D_Dlhm>m+#D_q)e

```

Try it here!
> 1 votes

# Answer
## J, 20 bytes

```
,[|.@{.~(-:|.)\.i.1:

```

This is a monadic verb. Try it here. Usage:

```
   f =: ,[|.@{.~(-:|.)\.i.1:
   f 'race'
'racecar'

```

## Explanation

I'm using the fact that the palindromization of **S** is **S + reverse(P)**, where **P** is the shortest prefix of **S** whose removal results in a palindrome. In J, it's a little clunky to do a search for the first element of an array that satisfies a predicate; hence the indexing.

```
,[|.@{.~(-:|.)\.i.1:  Input is S.
        (    )\.      Map over suffixes of S:
         -:             Does it match
           |.           its reversal? This gives 1 for palindromic suffixes and 0 for others.
                i.1:  Take the first (0-based) index of 1 in that array.
 [   {.~              Take a prefix of S of that length: this is P.
  |.@                 Reverse of P.
,                     Concatenate it to S.

```
> 1 votes

# Answer
# MATL, ~~17~~ 16 bytes

Loosely inspired in @aditsu's CJam answer.

```
`xGt@q:)PhttP=A~

```

**Try it online!**

### Explanation

```
`        % Do...while loop
  x      %   Delete top of stack, which contains a not useful result from the
         %   iteration. Takes input implicitly on first iteration, and deletes it
  G      %   Push input
  t      %   Duplicate
  @q:    %   Generate range [1,...,n-1], where n is iteration index. On the  first
         %   iteration this is an empty array
  )      %   Use that as index into copy of input string: get its first n elements
  Ph     %   Flip and concatenate to input string
  t      %   Duplicate. This will be the final result, or will be deleted at the
         %   beginning of next iteration
  tP     %   Duplicate and flip
  =A~    %   Compare element-wise. Is there some element different? If so, the
         %   result is true. This is the loop condition, so go there will be a
         %   new iteration. Else the loop is exited with the stack containing
         %   the contatenated string
         % End loop implicitly
         % Display stack contents implicitly

```
> 1 votes

# Answer
## Haskell, 68 bytes

```
import Data.List
f i=[i++r x|x<-inits i,i++r x==x++r i]!!0
r=reverse

```

Usage example: `f "abcb"` -\> `"abcba"`.

Search through the `inits` of the input `i` (e.g. `inits "abcb"` -\> `["", "a", "ab", "abc", "abcb"]`) until you find one where it's reverse appended to `i` builds a palindrome.
> 1 votes

# Answer
# Ruby, 44 bytes

This answer is based on xnor's Python and Haskell solutions.

```
f=->s{s.reverse==s ?s:s[0]+f[s[1..-1]]+s[0]}

```
> 1 votes

# Answer
# Oracle SQL 11.2, 195 bytes

```
SELECT MIN(p)KEEP(DENSE_RANK FIRST ORDER BY LENGTH(p))FROM(SELECT:1||SUBSTR(REVERSE(:1),LEVEL+1)p FROM DUAL WHERE SUBSTR(:1,-LEVEL,LEVEL)=SUBSTR(REVERSE(:1),1,LEVEL)CONNECT BY LEVEL<=LENGTH(:1));

```

Un-golfed

```
SELECT MIN(p)KEEP(DENSE_RANK FIRST ORDER BY LENGTH(p))
FROM (
       SELECT :1||SUBSTR(REVERSE(:1),LEVEL+1)p
       FROM   DUAL
       WHERE  SUBSTR(:1,-LEVEL,LEVEL)=SUBSTR(REVERSE(:1),1,LEVEL)
       CONNECT BY LEVEL<=LENGTH(:1)
     );

```
> 1 votes

# Answer
## Seriously, 34 bytes

```
╩╜lur`╜╨"Σ╜+;;R=*"£M`MΣ;░p╜;;R=I.

```

The last character is a non-breaking space (ASCII 127 or `0x7F`).

Try it online!

Explanation:

```
╩╜lur`╜╨"Σ╜+;;R=*"£M`MΣ;░p╜;;R=I.<NBSP>
╩                                        push inputs to registers (call the value in register 0 "s" for this explanation)
 ╜lur                                    push range(0, len(s)+1)
     `              `M                   map (for i in a):
      ╜╨                                   push all i-length permutations of s
        "        "£M                       map (for k in perms):
         Σ╜+                                 push s+''.join(k) (call it p)
            ;;R=                             palindrome test
                *                            multiply (push p if palindrome else '')
                      Σ                  summation (flatten lists into list of strings)
                       ;░                filter truthy values
                         p               pop first element (guaranteed to be shortest, call it x)
                          ╜;;R=I         pop x, push s if s is palindromic else x
                                .<NBSP>  print and quit

```
> 1 votes

# Answer
# C#, 202 bytes

I tried.

```
class P{static void Main(string[]a){string s=Console.ReadLine(),o=new string(s.Reverse().ToArray()),w=s;for(int i=0;w!=new string(w.Reverse().ToArray());){w=s.Substring(0,i++)+o;}Console.WriteLine(w);}}

```

Ungolfed:

```
class P
{
    static void Main(string[] a)
    {
        string s = Console.ReadLine(), o = new string(s.Reverse().ToArray()), w = s;
        for(int i = 0; w!=new string(w.Reverse().ToArray());)
        {
            w = s.Substring(0, i++) + o;
        }
        Console.WriteLine(w);
        Console.ReadKey();
    }

}

```

Can anyone provide me with any ideas to group the two calls to .Reverse().ToArray() ? A separate method is more bytes.
> 1 votes

# Answer
# Jelly, 9 bytes

```
Ṗ;¥ƤUŒḂƇḢ

```

Try it online!

## How it works

```
Ṗ;¥ƤUŒḂƇḢ - Main link. Takes a string S on the left
    U     - Reverse s
  ¥       - Group the previous 2 links into a dyad f(p, r):
Ṗ         -   Remove the last element of p
 ;        -   Concatenate the truncated p to r
   Ƥ      - Over each prefix p of s, yield f(p, rev(s))
       Ƈ  - Keep those for which the following is true:
     ŒḂ   -   Is a palindrome?
        Ḣ - Take the first

```
> 1 votes

# Answer
# K (ngn/k), 24 bytes

```
{t@*&{x~|x}'t:x,/:|',\x}

```

Try it online!

Feels like it could be golfed more...

* `,\x` make list of prefixes of input
* `t:x,/:\'` append the reverse of each prefix to the original input, storing in `t`
* `*&{x~|x}'` identify the index of the first item in the list that is a palindrome
* `t@` retrieve that list item and return it from the function
> 1 votes

# Answer
# Haskell, 46 bytes

```
f l|l==reverse l=l|(h:t)<-l=l!!0:(f$tail l)++[l!!0]

```

I'm wondering if there's a way to remove the parenthesis in `(f$tail l)++[l!!0]`...
> 0 votes

# Answer
## QBIC, 41 bytes

```
;_FA|C=A{a=a+1~C=_fC||_XC\C=A+right$(B,a)

```

Explanation:

```
;_FA|    Read A$ from the cmd line, then flip it to create B$
C=A      Set C$ to be A$
{        Start an infinite DO-loop
a=a+1    Increment a (not to be confused with A$...)
~C=_fC|  If C$ is equal to its own reversed version
|_XC     THEN end, printing C$
\C=A+    ELSE, C$ is reset to the base A$, with
right$(B the right part of its own reversal
,a)      for length a (remember, we increment this each iteration
         DO and IF implicitly closed at EOF

```
> 0 votes

---
Tags: code-golf, string, palindrome
---


title: Invert a Non-commutative Function

text:
# Question
Title: Invert a Non-commutative Function
## Intro

Imagine a list of elements and their outcomes when some non-commutative function is applied to them. For example, we will use the elements `Rock`, `Paper`, and `Scissors`, the outcomes `Win`, `Lose`, and `Tie`, and an operator `*` such that `X*Y` = what would happen if you played `X` against `Y`

As a list, you might write it this way:

```
[Rock*Rock=Tie,     Rock*Paper=Loss,    Rock*Scissors=Win,
Paper*Rock=Win,     Paper*Paper=Tie,    Paper*Scissors=Loss,
Scissors*Rock=Loss, Scissors*Paper=Win, Scissors*Scissors=Tie]

```

In table form, it might look like this:

| top\*left | Rock | Paper | Scissors |
| --- | --- | --- | --- |
| **Rock** | Tie | Win | Loss |
| **Paper** | Loss | Tie | Win |
| **Scissors** | Win | Loss | Tie |

One might observe that for any pair of elements, there is a pair of outcomes. For the unordered pair `(Rock,Paper)`, `Rock*Paper` gives `Loss` and `Paper*Rock` gives `Win`.

You might think of a function which takes a pair of elements and outputs a pair of outcomes given by the table. In our initial example, that'd be `(Rock,Paper) => (Loss,Win)`

A few more examples:

```
     (Rock,Rock) => (Tie,Tie)
(Paper,Scissors) => (Win,Loss)
   (Paper,Paper) => (Tie,Tie)

```

Note that order of input and output doesn't really matter here, since we're just asking which outcomes exist at all between the two elements.

Finally, consider the inverse to this function, which takes a pair of outcomes as input and outputs tall pairs of elements which can have both outcomes.

Here are all possible distinct inputs and their outputs for the example case:

```
  (Win, Win) =>
 (Win, Loss) => (Rock,Paper), (Paper,Scissors), (Scissors,Rock)
  (Win, Tie) =>
(Loss, Loss) =>
 (Loss, Tie) =>
  (Tie, Tie) => (Rock,Rock), (Paper,Paper), (Scissors,Scissors)

```

Note again that order doesn't matter here, so

```
(Win,Loss) => (Rock,Paper), (Paper,Scissors), (Scissors,Rock)
(Loss,Win) => (Rock,Paper), (Paper,Scissors), (Scissors,Rock)
(Win,Loss) => (Paper,Rock), (Scissors,Paper), (Scissors,Rock)
(Win,Loss) => (Scissors,Rock), (Rock,Paper), (Paper,Scissors)

```

are all valid.

Implementing this inverse is your challenge.

## Challenge

Write a program or function which does the following:

* Takes a list of ordered element pairs and their outcomes when some non-commutative function is applied, referred to as the "Interaction Table" from here onward. This can be done in any consistent reasonable format, specified by the solver.
* Takes a single unordered pair of outcomes `x,y` as a second input, referred to as the "Given Pair" from here onward. This can be done in any consistent reasonable format, specified by the solver.
* Outputs a list of all unique unordered pairs of elements `a,b` such that, according to the Interaction Table, `a*b` is one of `x,y` and `b*a` is the other. This can be done in any consistent reasonable format, specified by the solver.

This is , So shortest code in bytes wins.

## More specification

* The Interaction Table does not actually have to be a literal table. It can be taken in any reasonable format, standard I/O etc. Just remember to specify exactly how you take input, especially if it's somewhat unusual.
* Instead of taking the Given Pair as a second input, your program/function may take only the Interaction Table as input and output a program/function which takes the Given Pair as its only input and provides the expected output for the challenge.
* You may restrict elements and outcomes to a reasonable degree, e.g. "only integers" / "only alphabetical strings" is fine, but "only digits 0-9" is not.
* Since outputs will always be pairs of elements, you don't need to use a second delimiter to separate pairs, only individual elements. e.g. both `(A B) => (1 2) (3 4)` and `A B => 1 2 3 4` are both valid formats.
* You may assume that there are no missing interactions, i.e. every element within the Interaction Table will be paired with every other element and itself in each possible permutation.
* You may assume that the Interaction Table is given in some standard order, if that helps you in some way.
* You may **not** assume that every Given Pair will have an output. In these cases, any falsy output or no output is fine, so long as you don't output an element pair.
* You may **not** output duplicate pairs. `(A,B) => (1,2),(1,2)` is **not** valid, and since pairs are unordered, `(A,B) => (1,2),(2,1)` is also **not** valid.

## More examples

Here is another example of a possible Interaction Table input

```
(("AxA=1","AxB=1","AxC=2"),("BxA=2","BxB=3","BxC=2"),("CxA=1","CxB=2","CxC=1"))

```

Which can correspond to this literal table

| x | A | B | C |
| --- | --- | --- | --- |
| **A** | 1 | 2 | 1 |
| **B** | 1 | 3 | 2 |
| **C** | 2 | 2 | 1 |

Some example Given Pairs and their outputs

```
(1,1) => (A,A),(C,C)
(2,2) => (B,C)
(2,3) =>
(1,2) => (A,B),(A,C)

```

Another possible Interaction Table input

```
["What","What","Yeah"],["What","Who","Yeah"],["Who","What","Nah"],["Who","Who","Yeah"]

```

Which can correspond to this literal table

| x | What | Who |
| --- | --- | --- |
| **What** | Yeah | Nah |
| **Who** | Yeah | Yeah |

Some example Given Pairs and their outputs

```
 "Nah" "Yeah" => "Who" "What"
 "Yeah" "Nah" => "Who" "What"
  "Nah" "Nah" =>
"Yeah" "Yeah" => "What" "What" "Who" "Who"

```

One more possible Interaction Table input

```
"0 0 a 0 1 b 1 0 c 1 1 d"

```

Which can correspond to this literal table

| x | 0 | 1 |
| --- | --- | --- |
| **0** | a | c |
| **1** | b | d |

# Answer
> 5 votes
# Curry (PAKCS), 56 bytes

-2 bytes thanks to @Wheat Wizard.

```
(!)#p|[x!y,y!x]==(p?reverse p)&&x<=y=(x,y)where x,y free

```

Try it online!

Takes the Interaction Table as a function and the pair as a list with two elements.

For example, the Interaction Table of Rock-Paper-Scissors is given by the following function:

```
f "Rock" "Rock" = "Tie"
f "Rock" "Paper" = "Loss"
f "Rock" "Scissors" = "Win"
f "Paper" "Rock" = "Win"
f "Paper" "Paper" = "Tie"
f "Paper" "Scissors" = "Loss"
f "Scissors" "Rock" = "Loss"
f "Scissors" "Paper" = "Win"
f "Scissors" "Scissors" = "Tie"

```

And `f # ["Loss", "Win"]` would give the result:

```
("Rock","Scissors")
("Paper","Rock")
("Paper","Scissors")

```

# Answer
> 4 votes
# Vyxal, 24 bytes

```
vh'Ḃ"ƛ£¹'h¥⁼;ht;s⁰s⁼;vsU

```

Try it Online!

A mess.

## How?

```
vh'Ḃ"ƛ£¹'h¥⁼;ht;s⁰s⁼;vsU
vh                       # Get the first item of each of the (implicit) first input
  '                      # Filter-keep for:
   Ḃ"                    #   Pair with reverse
     ƛ                   #   For both:
      £                  #     Store in register
       ¹'                #     Filter-keep for first input:
         h¥⁼             #       Is the first item equal to the contents of the register? (non-vectorizing)
            ;            #     Close filter
             ht          #     Get the first item of the results of the filter, and get the last item of that
               ;         #   Close map
                s        #   Sort the results
                 ⁰s⁼     #   Is it equal to the first input sorted? (non-vectorizing)
                    ;    # Close filter
                     vs  # Sort each
                       U # Uniquify

```

# Answer
> 3 votes
# C (GCC), 118 bytes

```
f(n,e,t,x,y,i,j)int**t,*e;{for(i=0;i<n;++i)for(j=0;j<n;++j)t[i][j]-x|t[j][i]-y|x==y&i>=j||printf("%d %d ",e[i],e[j]);}
```

Attempt This Online!

Arguments description:

* `n` is the number of elements;
* `e` is a vector of `n` items, each representing an element;
* `t` is the table, represented as an array of arrays;
* `x` and `y` are the two result which form the pair to invert;
* `i` and `j` are dummy arguments.

# Answer
> 3 votes
# , 116 bytes

```
function(t,x,r=function(x)sub('(.*) (.*)','\\2 \\1',x),d=names(t),f=paste(t[d],t[r(d)]),c=d[f==x|f==r(x)])c[c<=r(c)]

```

Try it online!

R version 4 saves 14 bytes because you can say \\(x) rather than function but isn't supported by TIO.

This is a pretty straightforward approach, taking input as ('a,b') in string format (so no commas is the constraint for inputs/outputs). The table is a named vector to use R's indexing abilities to compute preimages and apply functions, and we build the function f (an unnamed vector on domain d) that takes (a,b) to (t(a,b),t(b,a)). Then we deduplicate at the end.

1 byte freed by replacing gsub with sub.

Improved to 112 bytes by https://codegolf.stackexchange.com/users/55372/pajonk, and R version 4 improves this to 98 bytes.

---
Tags: code-golf
---


title: fastest matrix multiplication on x86

text:
# Question
Title: fastest matrix multiplication on x86
*This challenge requires integration with C, so you can stop reading if you're not interested.*

Matrix multiplication is a simple operation, but the performance depends a lot on how efficiently the code is written.

Let's compute `m = x * y`. The following code is the implementation of the textbook algorithm.

```
for (int i = 0; i < n; ++i) {
    for (int j = 0; j < n; ++j) {
        float s = 0;
        for (int k = 0; k < n; ++k) {
            s += x[i * n + k] * y[k * n + j];
        }
        m[i * n + j] = s;
    }
}

```

It looks fine, but actually performs quite bad for various reasons.

Simply reordering the operations to let only row access happen is a significant optimization.

```
//m is zeroed
for (int i = 0; i < n; ++i) {
    for (int j = 0; j < n; ++j) {
        float e = x[i * n + j];
        for (int k = 0; k < n; ++k) {
            m[i * n + k] += e * y[j * n + k];
        }
    }
}

```

This version is about *9.5 times* faster than the upper one on my PC. Well, it's quite an optimal environment because in the actual implementation, I gave the compiler a lot of hints to make it auto-vectorize the second version up to the point where I couldn't gain any performance by manually vectorizing. But that's one of the problems of the first version. Column-accessing makes vectorization almost impossible to be done automatically and often not worthy to be done manually.

However, both versions are just the implementation of the most basic algorithm we all might know. I'd like to see what else could be done for a faster matrix multiplication on a restricted x86 environment.

The following restrictions are for *simpler* and *clearer* comparison between the algorithms.

* At most one thread can run during the program.
* The allowed x86 extensions are AVX2 and FMA.
* You must provide a **C interface** with the following prototype.

```
void (*)(void *m, void *x, void *y)

```

It **does not** have to be implemented in C, but you have to provide a way to be called from C.

`m`, `x`, and `y` point to 3 different arrays of `64 * 64 = 4096` `float`s that are aligned on a 32-byte boundary. These arrays represent a 64x64 matrix in row-major order.

You will be given randomly initialized matrices as input. When all outputs are done, first, the time taken will be measured, and then, a simple checksum will be calculated to check the correctness of the operation.

The table shows how much time the two example implementations shown earlier, each named `mat_mul_slow` and `mat_mul_fast`, takes to finish the test.

| `mat_mul_slow` | `mat_mul_fast` |
| --- | --- |
| ~19.3s | ~2s |

The measurement will be done on my machine with an Intel Tiger Lake CPU, but I will not run code that seems to be slower than `mat_mul_fast`.

Built-ins are fine, but it should be open source so that I can dig in their code to see what they've done.

The attached code is the tester and the actual implementation of the examples, compiled by `gcc -O3 -mavx2 -mfma`.

```
#include <stdio.h>
#include <stdalign.h>
#include <string.h>
#include <time.h>
#include <math.h>
#include <x86intrin.h>

enum {MAT_N = 64};

typedef struct {
    alignas(__m256i) float m[MAT_N * MAT_N];
} t_mat;

static void mat_rand(t_mat *_m, int n) {
    unsigned r = 0x55555555;
    for (int i = 0; i < n; ++i) {
        float *m = _m[i].m;
        for (int j = 0; j < MAT_N * MAT_N; ++j) {
            r = r * 1103515245 + 12345;
            m[j] = (float)(r >> 16 & 0x7fff) / 0x8000p0f;
        }
    }
}

static unsigned mat_checksum(t_mat *_m, int n) {
    unsigned s = 0;
    for (int i = 0; i < n; ++i) {
        float *m = _m[i].m;
        for (int j = 0; j < MAT_N * MAT_N; ++j) {
            union {float f; unsigned u;} e = {m[j]};
            s += _rotl(e.u, j % 32);
        }
    }
    return s;
}

__attribute__((noinline))
static void mat_mul_slow(void *_m, void *_x, void *_y) {
    enum {n = MAT_N};
    float *restrict m = __builtin_assume_aligned(((t_mat *)_m)->m, 32);
    float *restrict x = __builtin_assume_aligned(((t_mat *)_x)->m, 32);
    float *restrict y = __builtin_assume_aligned(((t_mat *)_y)->m, 32);
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            float s = 0.0f;
            for (int k = 0; k < n; ++k) {
                s = fmaf(x[i * n + k], y[k * n + j], s);
            }
            m[i * n + j] = s;
        }
    }
}

__attribute__((noinline))
static void mat_mul_fast(void *_m, void *_x, void *_y) {
    enum {n = MAT_N};
    float *restrict m = __builtin_assume_aligned(((t_mat *)_m)->m, 32);
    float *restrict x = __builtin_assume_aligned(((t_mat *)_x)->m, 32);
    float *restrict y = __builtin_assume_aligned(((t_mat *)_y)->m, 32);
    memset(m, 0, sizeof(t_mat));
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            float e = x[i * n + j];
            for (int k = 0; k < n; ++k) {
                m[i * n + k] = fmaf(e, y[j * n + k], m[i * n + k]);
            }
        }
    }
}

/*static void mat_print(t_mat *_m) {
    int n = MAT_N;
    float *m = _m->m;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; j += 8) {
            for (int k = 0; k < 8; ++k) {
                printf("%f ", m[i * n + j + k]);
            }
            putchar('\n');
        }
    }
    putchar('\n');
}*/

static void test(void (*f)(void *, void *, void *), t_mat *xy, t_mat *z,
int n) {
    clock_t c = clock();
    for (int i = 0; i < n; ++i) {
        f(z + i, xy + i * 2, xy + i * 2 + 1);
    }
    c = clock() - c;
    printf("%u %f\n", mat_checksum(z, n), (double)c / (double)CLOCKS_PER_SEC);
}

#define TEST(f) test(f, xy, z, n)

int main() {
    enum {n = 0x20000};
    static t_mat xy[n * 2];
    static t_mat z[n];
    mat_rand(xy, n * 2);
    puts("start");
    for (int i = 0; i < 2; ++i) {
        TEST(mat_mul_slow);
        TEST(mat_mul_fast);
    }
    return 0;
}

```

https://godbolt.org/z/hE9b9vhEx

# Answer
# C (GCC), 2.65× faster than `mat_mul_fast`

(Compiled with `gcc -O3 -mavx2 -mfma`, measured on my Intel Comet Lake i7-10710U.)

```
#include <x86intrin.h>

enum { MAT_N = 64 };

void mat_mul_simd(void *_m, void *_x, void *_y) {
  enum { n = MAT_N };
  float(*m)[n] = _m, (*x)[n] = _x, (*y)[n] = _y;
  for (int i = 0; i < n; ++i) {
    __m256 mi[n / 8];
    for (int k = 0; k < n / 8; ++k)
      mi[k] = _mm256_setzero_ps();
    for (int j = 0; j < n; ++j) {
      __m256 xij = _mm256_broadcast_ss(&x[i][j]);
      for (int k = 0; k < n / 8; ++k)
        mi[k] = _mm256_fmadd_ps(xij, _mm256_load_ps(&y[j][k * 8]), mi[k]);
    }
    for (int k = 0; k < n / 8; ++k)
      _mm256_store_ps(&m[i][k * 8], mi[k]);
  }
}

```

https://godbolt.org/z/xxvr45b67

## C (GCC 11)

This completely auto-vectorized code is very nearly as fast as the above in GCC 11 (`gcc -O3 -mavx2 -mfma`), but regresses significantly in GCC 12. Auto-vectorization is fragile.

```
enum { MAT_N = 64 };

void mat_mul_auto(void *_m, void *_x, void *_y) {
  enum { n = MAT_N };
  float(*restrict m)[n] = __builtin_assume_aligned(_m, 32);
  float(*restrict x)[n] = __builtin_assume_aligned(_x, 32);
  float(*restrict y)[n] = __builtin_assume_aligned(_y, 32);
  for (int i = 0; i < n; ++i) {
    float mi[n] = {};
    for (int j = 0; j < n; ++j)
      for (int k = 0; k < n; ++k)
        mi[k] += x[i][j] * y[j][k];
    for (int k = 0; k < n; ++k)
      m[i][k] = mi[k];
  }
}

```

https://godbolt.org/z/h4GEqGjGW
> 11 votes

---
Tags: matrix, fastest-code, optimization, c, x86-family
---


title: Counting Rhythms

text:
# Question
Title: Counting Rhythms
## The Narrative

You are a bad musician. You never bothered to learn how to count rhythms. To remedy this shortcoming, you decide to write a program that will tell you how to count in any given time signature. You are still a bad musician, but you can at least pretend that you can count rhythms.

## The Objective

Given a time signature, output a possible counting pattern for said time signature.

**For those who don't know musical terms:**
A measure is, essentially, a group of notes, useful for organizing music and making sure the musicians don't lose their place in the music.
A time signature is a set of numbers in a piece of music which tells you how many beats are in a measure, and which note-length is the beat. For example, a `3/4` time signature tells you that each measure has `3` beats, and the quarter note (`4`) is the beat. An `11/16` T.S. tells you that there are `11` sixteenth note beats (`16`) in one measure.
A counting pattern is a way to verbally express the division of a measure. For example, a song in `3/4` can simply be counted as `"1 2 3"`. `11/16` can be counted as `"1 la li 2 e & a 3 e & a"` (this is more intuitive than counting to 11; I will define this later)
*It's important to note that the bottom number of almost all T.S.'s are a power of 2. For this challenge, we will ignore irrational T.S.'s. We will also not look at T.S.'s with a beat greater than 16.*

**How to Generate a Counting Pattern:**
Time signatures with a `X/1`, `X/2`, or `X/4` can simply be counted with numbers (`4/2` can be counted as `"1 2 3 4"`).
T.S.'s with a `X/8` or `X/16` are a bit more tricky. These can be counted by grouping beats together to form larger beats (`6/8`, despite having `6` 'beats', is very often treated as `2` beats with a triplet subdivision). **For this challenge, beats should be grouped in groups of `1`(`"1"`), `2`(`"1 &"`), `3`(`"1 la li"`), or `4`(`"1 e & a"`)**
For `X/8`, groups of `3` should be prioritized over `2`, but `1` should be avoided if possible. (For `7/8`, even though `3+3+1` prioritizes `3`'s, `3+2+2` is better because it avoids `1`)
For `X/16`, groups of `3` should be prioritized over `4`, but `2` and `1` should be avoided if possible. (For `11/16`, even though `3+3+3+2` prioritizes `3`'s, `3+4+4` is better because it avoids `2`)
*It is important to note that the ordering of the groups is not important, i.e. `3+2` and `2+3` are both acceptable groupings of `5/8`. This would be important normally, but you are a bad musician.*
*Also note that T.S.'s 'larger' than `1/8` can be grouped entirely with `2`'s and `3`'s; T.S.'s 'larger' than `5/16` can be grouped entirely with `3`'s and `4`'s.*

Whew! What a mouthful!

## The Specs

**You will take a time signature as input.** this may be formatted within reason (use common sense!).
**You will output an acceptable counting pattern.** This will be a string of counts (`1`, `la`, `&`, etc.) separated by spaces. Your output should not include leading or trailing whitespace.
**Test Cases:**
*To clarify, the 'numerator' is a positive integer, and the 'denominator' is `1`, `2`, `4`, `8`, or `16`.*
*Again, note that some T.S.'s have multiple valid outputs.*

```
"Input", "Output"
"1/1", "1"
"3/2", "1 2 3"
"4/4", "1 2 3 4"
"1/8", "1"
"10/8", "1 la li 2 la li 3 & 4 &"
"2/16", "1 &"
"5/16", "1 la li 2 &"
"29/16", "1 la li 2 la li 3 la li 4 la li 5 la li 6 la li 7 la li 8 e & a 9 e & a"

"Input", "Invalid Output"
"6/4", "1 la li 2 la li"
"7/8", "1 la li 2 la li 3"
"10/8", "1 & 2 & 3 & 4 & 5 &"
"12/16", "1 e & a 2 e & a 3 e & a"

```

This is , so the shortest answer in bytes wins!

# Answer
> 4 votes
# Jelly, 46 bytes

```
Œṗi@€o⁸Ṁ;ṢƊɗÞ:5×6Œ?Ɗ}Ḣị““&“la li“e & a”Ė¹Ƈ€K€K

```

A full program that accepts the beats and the note-length and prints the result

**Try it online!**

### How?

```
Œṗi@€o⁸Ṁ;ṢƊɗÞ:5×6Œ?Ɗ}Ḣị“...”Ė¹Ƈ€K€K - Main Link: beats, B; note-length L
Œṗ                                  - all integer partitions of B
                    }               - using L:
                   Ɗ                -   last three links as a monad - f(L):
                                                             e.g. 1,2,4,8,16
             :5                     -     integer divide by 5  -> 0,0,0,1,3
               ×6                   -     multiply by six      -> 0,0,0,6,18
                 Œ?                 -     shortest permutation of [1..N] which has that
                                            lexicographic 1-based-index in a list of all
                                            permutaions of [1..N]
                                                               -> [],[],[],[3,2,1],[3,4,2,1]
                                                                  (our ordering)
            Þ                       - sort (the partitions) by:
           ɗ                        -   last three links as a dyad - f(Partition, Ordering)
    €                               -     for each (run-length, R) in the partition:
  i@                                -       first 1-indexed index of R in Ordering or 0
     o⁸                             -       logical OR with the Partition (vectorises)
                                              (replaces 0s with the larger, original Rs)
          Ɗ                         -       last three links as a monad - f(X):
       Ṁ                            -         maximum of X
         Ṣ                          -         sorted X
        ;                           -         concatenate
                     Ḣ              - head
                       “...”        - ["", "&", "la li", "e & a"]
                      ị             - index into
                            Ė       - enumerate (i.e. [A, B, ...] -> [[1,A],[2,B],...])
                               €    - for each:
                             ¹Ƈ     -   keep truthy (i.e. drop the "" entries)
                                K€  - join each with spaces
                                  K - join with spaces
                                    - implicit print

```

# Answer
> 5 votes
# C (gcc), ~~372~~ ~~354~~ ~~308~~ ~~301~~ ~~299~~ ~~260~~ ~~240~~ ~~237~~ 233 bytes

```
#define p!printf(" %d%s"+!i++,i,a
#define q(x,y,z)(j=n%3-z/4)|n<z?p[x]),~j:p[y])+p[y])-z;
*a[]={""," &"," la li"," e & a"};f(n,d,i,j){for(i=0;d<5&&n--;)p[0]);n+=d-8?0:q(j,1,4)for(n+=d<16?0:n<2?p[0])-n:q(j=j?j+3:1,3,8)n>0;n-=3)p[2]);}

```

Try it online!

*-24 bytes thanks to ceilingcat*

*-46 bytes thanks to ceilingcat*

*-7 bytes thanks to ceilingcat*

*-2 bytes thanks to ceilingcat*

*-39 bytes thanks to both Juan Ignacio Díaz and ceilingcat*

*-20 bytes thanks to both Juan Ignacio Díaz and ceilingcat*

*-3 bytes thanks to ceilingcat*

*-4 bytes thanks to ceilingcat*

# Answer
> 3 votes
# 05AB1E, 52 bytes

```
5‹iLëÅœΣ4LRIg·†3†Rsk{}θε…e&aN>©š®D'&‚®…ÿ…å´à)ćè]˜ðý?

```

Two separated inputs \\$a\\$ and \\$b\\$, where \\$b\\$ is the beat and \\$a\\$ are the amount of notes in the measure.
If the input was as strict as the output, a trailing `'/¡`©` (+5 bytes) could be added and the `I` could be replaced with `®`.

Try it online or verify all test cases or try it online with strict input format.

`4LR®g·†3†R` could alternatively be `4L14S.I®gè` for the same byte-count: verify all test cases.

**Explanation:**

```
5‹i            # If the first (implicit) input is smaller than 5 (1, 2, or 4):
   L           #  Push a list in the range [1, second (implicit) input]
ë              # Else (it's 8 or 16 instead):
 Åœ            #  Get all lists of positive integers that sum to the second
               #  (implicit) input
   Σ           #  Sort it by:
    4LR        #   Push list [4,3,2,1]
       I       #   Push the second input again
        g      #   Pop and push its length
         ·     #   Double it
          †    #   Filter that value to the front
           3†  #   Then filter 3 to the front
             R #   And then reverse the list
               #   (we now have [1,4,2,3] for input=8
               #   and [1,2,4,3] for input=16)
    s          #  Swap so the current list
     k         #  Get the index of each in this list (or -1 if higher)
      {        #  Sort that list from lowest to highest
   }θ          #  After the sort: leave the last list
               #  (so `Σ...}θ` acted as a maximum-by builtin)
 ε             #  Map that resulting list to:
  …e&a         #   Push string "e&a"
      N>       #   Push the 1-based map-index
        ©      #   Store it in variable `®` (without popping)
         š     #   Convert the string to a list, and append it:
               #    ["e","&","a",index]
  ®            #   Push index `®` again
  D            #   And again, with a duplicate
   '&‚        '#   Pair it with "&"
  ®            #   And yet again
   …ÿ…å´à      #   Push dictionary string "ÿ la li",
               #   where the `ÿ` is replaced with this index
  )            #   Wrap all values into a list
   ć           #   Extract the head; the current list of the map
    è          #   Modular 0-based index those into the list
]              # Close both the map and if-else statement
 ˜             # Flatten the list of lists
  ðý           # Join it with a space delimiter
    ?          # Explicitly print it without trailing newline

```

See this 05AB1E tip of mine (section *How to use the dictionary?*) to understand why `…ÿ…å´à` is `"ÿ la li"`.

# Answer
> 2 votes
# Python 2, ~~136~~ 135 bytes

*-1 byte thanks to Kevin Cruijssen*

```
def f(m,b,r='',i=1):
 while m:k=b<5or[m,3-(m<5)+(6<m<9)*b/9][m>2+b/8];m-=k;r+=' '+`i`+[' e & a',' la li',' &',''][-k];i+=1
 print r[1:]

```

Try it online!

Takes input as `f(m,b)` where `m` is the numerator and `b` is the denominator

### Explanation

```
while m:

```

Loop while `m` \> 0

```
k=b<5or[m,3-(m<5)+(6<m<9)*b/9][m>2+b/8]

```

Determine the size of the next group. Essentially the logic is as follows:

* `b in [1,2,4]` =\> **1**
* `b == 8 and m == 4` =\> **2**
* `b == 16 and m in [7,8]` =\> **4**
* `(b == 8 and m <= 3) or (b == 16 and m <= 4)` =\> **m**
* otherwise =\> **3**

```
m-=k;r+=' '+`i`+[' e & a',' la li',' &',''][-k];i+=1

```

Decrease `m` by the group size. Append the following to `r`: First a space, then the current group index, then the appropriate suffix based on the group size. Increment the group index

```
print r[1:]

```

Output the constructed string, removing the leading space

# Answer
> 2 votes
# Charcoal, 70 bytes

```
ＮθＮη⪫Ｅ⊟Φ…⟦Ｅθ¹Ｅ÷⁺²θ³⁻³‹ι﹪±θ³Ｅ÷θ³⁺³‹ι﹪θ³⟧⊕÷η⁸⁼θΣι⁺⊕κ§⪪“/^e)R⁼0⁷Ｖⅉ8⮌✳”,ι

```

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

```
ＮθＮη

```

Input the time signature.

```
⟦Ｅθ¹Ｅ÷⁺²θ³⁻³‹ι﹪±θ³Ｅ÷θ³⁺³‹ι﹪θ³⟧

```

Try to create three beat patterns: all single beats, as many groups of three as possible with the rest two, and as many groups of three as possible with the rest four.

```
…...⊕÷η⁸

```

Only consider the first or first two patterns depending on the denominator.

```
Φ...⁼θΣι

```

Only keep those patters that actually sum to the whole bar. (This prevents e.g. `5/16` from trying to use groups of three and four).

```
⪫Ｅ⊟...⁺⊕κ§⪪...,ι

```

Take the last successful pattern and replace each group with its beat number and group suffix obtained by splitting the compressed string  `e & a,, &, la li`, finally joining the groups with spaces.

# Answer
> 2 votes
# Vyxal, 56 bytes

```
5<[ɾ|Ṅµ1k½d⁰LǔJ3Jvḟs;tṘ¨2›:£`e&a`fJ¥:\&"¥«cb|«"ṄWḣi;]fṄ₴

```

Try it Online!

Port of 05AB1E. Quite slow.

---
Tags: code-golf, music
---


# Question
Title: Calculate the Lowest Even-Harmonic of the Values in a List
**PROBLEM**

For a list of numbers, `list`: Find the *lowest possible* integer, `x`, which is optimally close to the whole number even-harmonics of the values in list.

* `list` has a length of n, and all of the values in list are \<= 2000
* `x` has a precision of 1.0 (integers only), and must be a value in the range \[20, 100\]
* An even-harmonic is a number that is divisible by `list` an even number of times. 20 is an even harmonic of 80 (because 80/20=**4**) -- but an odd harmonic of 60 (because 60/20=**3**).
* In this case, "optimally close" simply means to minimize the absolute cumulative remainder, relative to the nearest even harmonic of the input value(s).
    + Minimizing the absolute cumulative error takes priority over choosing the "lowest allowable value" for `x`.
    + Given `list = [151, 450, 315]` and a candidate guess of `x=25` the absolute cumulative remainder is 0.64 because 25 goes into `list` \[6.04, 18, 12.6\] times, respectively. The nearest even-harmonics for each instance are \[6, 18, 12\].

**EXAMPLE**

`list = [100, 300, 700, 1340]`

* `x = 20` is a bad solution because it is an exact or almost-exact odd-harmonic of all of the values of `list`. The number 20 goes into `list` \[5, 15, 35, 67\] times, respectively (odd numbers = odd harmonics = the opposite of even-harmonics).
    + The absolute cumulative remainder is 4.0 in this case (which is the maximum possible error for this instance of `list`).
* `x = 25` is a *good* solution, but not the best, because it is a exact or almost-exact even-harmonic of all of the values of list. In this case, 25 is an exact even-harmonic in all cases except for 1340. The number 25 goes into `list` \[4, 12, 20, 53.6\] times, respectively (even numbers).
    + The absolute cumulative remainder is 0.4 in this case.

**BONUS**

Same prompt and problem, except x has a maximum precision of 0.1 (non-integer)

# Answer
# Factor \+ `math.unicode`, ~~83~~ ~~78~~ 77 bytes

```
[ 20 100 [a,b] [ v/n [ 2 mod dup 1 > 2 0 ? - abs ] map Σ ] with infimum-by ]

```

Try it online!

* `20 100 [a,b]` Create a range from 20 to 100, inclusive.
* `[ ... ] with infimum-by` Find the number in the range that is smallest when `[ ... ]` is applied to it. `with` takes our input into the `[ ... ]` in such a way that it will be underneath each number in the range on the data stack.
* `v/n` Divide each element in the input by the current number in the range.
* `[ ... ] map Σ` Map each element to a new value with the `[ ... ]` quotation and then take the sum.
* `2 mod dup 1 > 2 0 ? - abs` Find the distance to the nearest even number.
> 5 votes

# Answer
# Jelly, 16 bytes

```
÷Ɱȷ2Ḃ2_«Ɗ§Ụ>Ƈ19Ḣ

```

A monadic Link that accepts a list of integers and yields an integer.

**Try it online!**

### How?

```
÷Ɱȷ2Ḃ2_«Ɗ§Ụ>Ƈ19Ḣ - Link: list of integers, A
  ȷ2             - 10^2 = 100
 Ɱ               - map across x in [1,100] with:
÷                -   A divided by x (vectorises)
    Ḃ            - mod 2 (vectorises)
        Ɗ        - last three links as a monad - f(v=that):
     2           -   two
      _          -   subtract v (vectorises)
       «         -   minimum with v (vectorises)
         §       - sums
          Ụ      - grade-up (one-based indices sorted by the value at that index)
            Ƈ    - filter keep if:
           > 19  -   greater than 19
               Ḣ - head

```
> 5 votes

# Answer
# JavaScript (ES6), 79 bytes

```
a=>(m=g=o=>x++>99?o:g(a.map(v=>e+=(v/=x)&1?1-v%1:v%1,e=0)|e>m?o:(m=e,x)))(x=19)

```

Try it online!
> 4 votes

# Answer
# Python 3, <sup>~~75~~</sup> 73 bytes

```
lambda l:min(range(20,101),key=lambda x:sum(min(a/x%2,-a/x%2)for a in l))

```

Try it online!

*Saved 2 bytes thanks to Steffan!!!*

Inputs a list of integers.
Returns the lowest even harmonic.
> 4 votes

# Answer
# Vyxal, 19 bytes

```
20₁ṡµ⁰$/:1%$∷1=+∑;h

```

Try it Online!

*-2 bytes thanks to emanresu A, and another -3 by porting 05AB1E*
> 4 votes

# Answer
# Burlesque, 49 bytes

```
bc20 100r@)td{?/{JR_2./2.*.-ab}ms}Z]ziq[~<m-]20.+

```

Try it online!

```
bc       # Repeat input list
20 100r@ # Range [20..100]
)td      # As doubles
{
 ?/      # Divide each
 {       # -- Find difference with nearest 2
  J      # Duplicate
  R_     # Round
  2./2.* # Closest multiple of 2
  .-     # Difference
  ab     # Abs
 }
 ms      # Map sum
}Z]      # Zip range with input and evaluate
zi       # Zip indices
q[~<m-]  # Index of minimum
20.+     # +20

```
> 4 votes

# Answer
# , 72 bytes

```
\(l,m=20:200,x=outer(l,m,`/`)%%2/2)m[order(colSums(abs(x-round(x))))[1]]
```

Attempt This Online!
> 4 votes

# Answer
# Charcoal, 25 bytes

```
≔Ｅ⁸¹Σ↔⊖﹪⊕∕θ⁺²⁰ι²ηＩ⁺²⁰⌕η⌊η

```

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

```
  ⁸¹                        Literal integer `80`
 Ｅ                          Map over implicit range
          θ                 Input array
         ∕                  Vectorised divide
              ι             Current value
           ⁺                Plus
            ²⁰              Literal integer `20`
        ⊕                   Vectorised increment
       ﹪                    Vectorised modulo
               ²            Literal integer `2`
      ⊖                     Vectorised decrement
     ↔                      Vectorised absolute
    Σ                       Take the sum
≔               η           Store in variable
                        η   List of absolute cumulative errors
                       ⌊    Find the minimum
                     ⌕      Find index in
                      η     List of absolute cumulative errors
                  ⁺         Plus
                   ²⁰       Literal integer 20
                 Ｉ          Cast to string
                            Implicitly print

```
> 3 votes

# Answer
# APL+WIN, 43 bytes

Prompts for vector of numbers in list

```
(m=⌊/m←+/¨|¨m-⌊¨m+1≤¨2|¨m←(⊂⎕)÷¨n)/n←19+⍳81

```

Try it online! Thanks to Dyalog Classic
> 3 votes

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

```
a=>Enumerable.Range(20,81).OrderBy(x=>a.Sum(k=>Math.Min(2-k/x%2,k/x%2))).First()

```

Try it online!
> 2 votes

# Answer
# 05AB1E, 15 bytes

```
20тŸΣ/D1%sÉ+O}н

```

Try it online or verify both test cases.

**Explanation:**

```
20тŸ         # Push a list in the range [20,100]
    Σ        # Sort it by:
     /       #  Divide the (implicit) input-list by this value
      D      #  Duplicate the decimal values
       1%    #  Modulo-1 to only keep the decimal portion
      s      #  Swap so the entire values are at the top again
       É     #  Check which ones are odd (ignoring the decimal portions)
         +   #  Add the values at the same positions together
          O  #  Sum this list together
    }н       # After the sort-by, keep just the first element
             # (so `Σ...}н` basically acted as a minimum-by builtin)
             # (which is output implicitly as result)

```
> 2 votes

# Answer
# C, 122 bytes

```
i,j,k;f(n,m)int*n;{float a=m,b,c;for(i=19;99/i++;k=b<a?a=b,i:k)for(j=b=0;j<m;b+=fabs(c-rint(c))*2)c=n[j++]/2./i;return k;}

```

Try it online!

### Bonus:

# C, 134 bytes

```
i,j,k;float f(n,m)int*n;{float a=m,b,c;for(i=199;999/i++;k=b<a?a=b,i:k)for(j=b=0;j<m;b+=fabs(c-rint(c))*2)c=n[j++]/.2/i;return k/10.;}

```

Try it online!
> 2 votes

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


title: Find a dual graph

text:
# Question
Title: Find a dual graph
A dual graph is defined such that for every "face" in a graph `G`, there is a corresponding vertex in the dual graph, and for every edge on the graph `G`, there is an edge in the dual graph connecting the vertices corresponding to the two faces on either side of the edge of the original graph. Note that the faces on both side may be the same face, for example the graph consisting of 2 vertices connected by a single edge (see case 3).

Here is a shamelessly borrowed example from Wikipedia:

Your goal is given a graph, find a dual graph for that graph. Note that there may not necessarily be a unique dual graph for a given graph; you need only find one. Assume all input graphs are undirected and planar.

# Input

Assume all vertices of the input graph have some consecutive integer numbering starting at any beginning integer value of your choice. An edge is described by an unordered pair of integers denoting the vertices the edge connects. For example, the blue graph shown above could be described with the following unordered multiset of edges (assuming the numbering of vertices starts at 0):

```
[(0,1), (0,2), (1,2), (2,3), (1,3), (1,4), (4,3)]

```

An alternative way to describe a multigraph is via an adjacency list. Here is an example adjacency list for the above graph:

```
[0:(1,2), 1:(0,2,3,4), 2:(0,1,3), 3:(1,2,4), 4:(1,3)]

```

Your program must take as input a multigraph of edges from any source (stdio, function parameter, etc.). You may assume the input graph is connected. You may use any notation desired so long as the no additional non-trivial information is communicated to your program. For example, having an extra parameter denoting the number of input edges is perfectly acceptable, but passing in a full or partially formed dual graph as an extra parameter is not. Similarly, passing in an unordered multiset of edges, adjacency list, or adjacency matrix is fine.

# Output

The output of your program should be in one of the formats allowed for the input; it needs not be the same as the input format. The output may be to any sink desired (stdio, return value, output parameter, etc.).

# Examples

All following examples use unordered multisets of edges with 0-based indices. One possible output is given. As a side note, all of the test case outputs are also valid inputs for your program, and an example output is the corresponding input.

**case 1:**

```
input:
[(0,1), (0,2), (1,2), (2,3), (1,3), (1,4), (4,3)]
output:
[(0,1), (0,2), (1,0), (0,3), (0,3), (1,2), (2,3)]

```

**case 2:**

```
input:
[(0,1),(0,2),(1,2)]
output:
[(0,1),(0,1),(0,1)]

```

**case 3:**

```
input:
[(0,1)]
output:
[(0,0)]

```

**case 4:**

```
input:
[]
output:
[]

```

**case 5:**

```
input:
[(0,1),(0,2),(2,1),(3,1),(3,4),(2,4)]
output:
[(0,2),(0,2),(1,0),(1,2),(1,2),(1,2)]

```

# Scoring

This is code golf; shortest code wins. Standard loopholes apply. You may use any built-ins not specifically designed to solve this problem.

# Answer
# Python3, 416 bytes:

```
S=sorted
T=tuple
def C(n,o,l,p=[]):
 if n==o and p:yield T(map(T,S(p)));return
 for i in l[n]:
  if(s:=S([n,i]))not in p:yield from C(i,o,l,p+[s])
def f(e):
 K,s=0,{min(r,key=len)for i in e if(r:=[*C(i,i,e)])}
 if not s and e:return[(0,0)]
 E={(K:=K+1):set(i) for i in s}
 l=[((a,b),j)for a in E for b in E if a<b and(j:=E[a]&E[b])]
 return[(0,i)for i in E for _ in E[i]-{x for _,y in l for x in y}]+[a for a,_ in l]

```

Try it online!
> 2 votes

---
Tags: code-golf, graph-theory
---


title: Is My Swipe Pattern Legal?

text:
# Question
Title: Is My Swipe Pattern Legal?
Most Android smartphones allow the user to use a swipe pattern to open their phone:

Certain patterns are legitimate, and others are impossible. Given an input swipe pattern, return a truthy or falsy indicating if the given input pattern is legal or not.

## Input

The grid is labelled row-wise 1 through 9:

```
1 2 3
4 5 6
7 8 9

```

The input is a number comprised of the nodes visited from first to last. For example, the swipe pattern above is 12357.

Input can be a decimal number, string or list of numbers. It will not contain 0 because there is no node 0.

Amendment: indexing 0-8 is allowed since a lot of languages index from 0. If you use 0-8, it'll be necessary to indicate as such at the beginning of your answer and adjust the test cases accordingly.

## Rules

* Every node starts as unvisited initially and may only be visited once. Any pattern which visits a node more than once is falsy.
* A truthy pattern must contain at least one swipe, so a minimum of 2 nodes.
* It's not possible to skip over an unvisited node directly in line with another. For example, 13 is falsy because 2 is unvisited and directly in line.
* It is only possible to skip over a visited node. 42631 is an example of this.
* Lines may cross otherwise. For example, 1524 is truthy.
* Assume node widths are insignificant and ignore practical issues (finger thickness, etc). So 16 is truthy even though it may be slightly harder to achieve in reality.

## Test Cases

```
1 -> false
12 -> true
13 -> false
16 -> true
31 -> false
33 -> false
137 -> false
582 -> true
519 -> true
1541 -> false
12357 -> true
15782 -> true
19735 -> false
42631 -> true
157842 -> true
167294385 -> true
297381645 -> false
294381675 -> true

```

This is , so the fewest number of bytes wins.

# Answer
# JavaScript (ES6), 64 bytes

Takes input as an array of numbers. Falsy values are **0** or **NaN**. Truthy values are strictly positive integers.

```
a=>a[p=1]*a.every(n=>a[p=a[n&p&p*n%5<0|~(p-=n)==9&&p/2]&&-n]^=p)

```

Try it online!

## How?

### Preamble

Two digits are vertically, horizontally or diagonally opposed if:

* they are both odd, different from each other and different from 5 (figure 1)
* OR they are both even and their sum is 10 (figure 2)

Besides, the digit standing between two opposed digits **n** and **p** is equal to **(n + p) / 2**.

### Formatted source code

```
a =>
  // force a falsy result if a[1] is undefined
  a[p = 1] *
  // walk through all values n in a[]
  a.every(n =>
    // access either a[-n] or a[undefined]
    a[
      // set p to either -n or undefined
      p =
        // read either a[0] or a[in_between_digit]
        a[
          n & p & p * n % 5 < 0 | ~(p -= n) == 9
          && p / 2
        ]
        && -n
    ]
    // toggle the flag
    ^= p
  )

```

### Keeping track of previous digits

Flags for visited digits are stored at negative indices in the input array **a**, so that they don't collide with its original elements.

* If **p** is set to **-n**:

If the current digit **n** was not previously selected, `a[-n] ^= -n` will set the flag and let the `every()` loop go on with the next iteration. Otherwise, it will clear the flag and force the loop to fail immediately.
* If **p** is set to **undefined**:

`a[undefined] ^= undefined` results in **0**, which also forces the loop to fail.

### Detecting opposed digits

The following expression is used to test whether the current digit **n** and the previous digit **-p** are opposed digits, as defined in the preamble:

```
n & p & ((p * n) % 5 < 0) | ~(p -= n) == 9

```

which is equivalent to:

```
n & p & ((p * n) % 5 < 0) | (p -= n) == -10

```

*Note: In JS, the result of the modulo has the same sign as the dividend.*

It can be interpreted as:

```
(n is odd AND -p is odd AND (neither -p or n is equal to 5)) OR (n + -p = 10)

```

Therefore, this expression returns **1** if and only if **n** and **-p** are opposed digits *or* they are the same odd digit. Because a digit can't be selected twice, this latter case is correctly taken care of anyway.

If this expression returns **1**, we test **a\[p / 2\]** (where **p** is now equal to the negated sum of the digits) in order to know whether the 'in-between digit' was previously visited. Otherwise, we test **a\[0\]** which is guaranteed to be truthy.

### About the first iteration

The first iteration is a special case, in that there is no previous digit and we want it to be unconditionally successful.

We achieve that by initializing **p** to **1**, because for any **n** in **\[1 .. 9\]**:

* `(1 * n) % 5` can't be negative
* `~(1 - n)` can't be equal to 9

---

# Original answer, 90 bytes

*Removed from this post so that it doesn't get too verbose. You can see it here.*
> 71 votes

# Answer
# x86 32-bit machine code, ~~62~~ 60 bytes

Hexdump:

```
33 c0 60 8b f2 33 db 99 80 f9 02 72 2d ad 50 0f
ab c2 72 25 3b c3 77 01 93 2b c3 d1 e8 72 14 68
92 08 0e 02 0f a3 5c 04 ff 5f 73 07 03 d8 0f a3
da 73 06 5b e2 d7 61 40 c3 58 61 c3

```

It receives the length of the list in `ecx` and a pointer to the first element in `edx`, and returns the result in `al`:

```
__declspec(naked) bool __fastcall check(int length, const int* list)

```

There are 8 lines that contain a node in the middle:

```
1 - 3
4 - 6
7 - 9
1 - 7
2 - 8
3 - 9
1 - 9
3 - 7

```

I grouped them according to the difference between the bigger and the smaller number.

```
Difference 2: 3 lines (starting at 1, 4 or 7)
    1 - 3
    4 - 6
    7 - 9
Difference 4: 1 line (starting at 3)
    3 - 7
Difference 6: 3 lines (starting at 1, 2 or 3)
    1 - 7
    2 - 8
    3 - 9
Difference 8: 1 line (starting at 1)
    1 - 9

```

Then, I converted that to a 2-D lookup table indexed by half-difference and smaller number:

```
76543210
--------
10010010 - half-difference 1
00001000 - half-difference 2
00001110 - half-difference 3
00000010 - half-difference 4

```

This makes a "magic" bitmap of 32 bits. To index it, the code pushes it into the stack. Then, it extracts one byte using one index, and from that byte, it extracts one bit using the other index. All this using one instruction:

```
bt byte ptr [esp + eax - 1], ebx; // -1 because half-difference is 1-based

```

If the bitmap indicates that there is a node in the middle, it's easy to calculate - add half the difference to the smaller number.

Assembly source:

```
    xor eax, eax;   // prepare to return false
    pushad;         // save all registers
    mov esi, edx;   // esi = pointer to input list
    xor ebx, ebx;   // ebx = previously encountered number = 0
    cdq;            // edx = bitmap of visited numbers = 0

    cmp cl, 2;      // is input list too short?
    jb bad_no_pop;  // bad!

again:
    lodsd;          // read one number
    push eax;

    bts edx, eax;   // check and update the bitmap
    jc bad;         // same number twice? - bad!

    cmp eax, ebx;   // sort two recent numbers (ebx = minimum)
    ja skip1;
    xchg eax, ebx;
skip1:

    // Check whether the line crosses a node
    sub eax, ebx;   // calculate half the difference
    shr eax, 1;
    jc skip_cross;  // odd difference? - no node in the middle

    push 0x020e0892;// push magic bitmap onto stack
    bt byte ptr [esp + eax - 1], ebx; // is there a node in the middle?
    pop edi;
    jnc skip_cross; // no - skip the check

    add ebx, eax;   // calculate the node in the middle
    bt edx, ebx;    // was it visited?
    jnc bad;        // no - bad!

skip_cross:
    pop ebx;
    loop again;

    // The loop was finished normally - return true
    popad;          // restore registers
    inc eax;        // change 0 to 1
    ret;            // return

    // Return false
bad:
    pop eax;        // discard data on stack
bad_no_pop:
    popad;          // restore registers
    ret;            // return

```
> 45 votes

# Answer
# Python 2, ~~140~~ ~~131~~ ~~114~~ ~~104~~ 99 bytes

-2 bytes thanks to Jonathan Frech
-5 bytes thanks to Chas Brown

```
v={0};k=input()
for l,n in zip(k,k[1:])or q:(2**n+~2**l)%21%15%9==5<v-{l+n>>1}==v>q;v|={l};n in v>q

```

Try it online!

## Explanation:

```
# full program, raising a NameError for invalid input
v={0}            # set of visited nodes
k=input()        # load pattern
# iterate through adjacent pairs, if there is no pair, raise a NameError
for l,n in zip(k,k[1:])or q:
  # detect moves skipping over nodes, details below
  (2**n + ~2**l) % 21 % 15 % 9 == 5 < v - {l+n >> 1} == v > q
  v |= {l}       # add the last node to the set of visited nodes
  n in v > q     # if the current node was previously visited, raise a NameError

```

Try it online!

Only 8 pairs of nodes have a node in between them. A pair of nodes can be represented as a single integer by the formula `2^a-2^b-1`. This number can be shortened by repeated modulo:

```
a  b  2^a-2^b-1  (2^a-2^b-1)%21%15%9
1  3         -7                    5
1  7       -127                    5
1  9       -511                    5
2  8       -253                    5
3  1          5                    5
3  7       -121                    5
3  9       -505                    5
4  6        -49                    5
6  4         47                    5
7  1        125                    5
7  3        119                    5
7  9       -385                    5
8  2        251                    5
9  1        509                    5
9  3        503                    5
9  7        383                    5

```

`(2**n+~2**l)%21%15%9==5` first checks if such a pair is present, then `v-{l+n>>1}==v` tests whether the node in between, which is given by `(a+b)/2`, was not visited yet and `q` raises a NameError. By using chained comparison between these pairs, the next comparison is only executed when the previous returned `True`.
> 23 votes

# Answer
# Jelly,  ~~24 22 19 18~~  17 bytes

 -2 since we are no longer required to handle an empty list
-1 switching from join, `j@`, to concatenate, `;` (the missed item does not *need* to be encountered in the middle for the method employed, being at the start of the trio is fine)
-2 switching from `P¬aSH` to `oSH`(OK to have two results since we flatten, half of `1` is `0.5` which is filtered out anyway, and having multiple equal results has no affect on the method employed either)
-1 Thanks to Mr. Xcoder (0-indexed input is allowed)
-1 using the (newer) invariance quick, `Ƒ`, and filter-keep quick alias, `Ƈ`.

```
d3ZIỊoSH;µƝFḞƑƇQ⁼

```

A monadic link taking a list of integers in `[0,8]` and returning a truthy value (`1`) if legal and a falsey value (`0`) if not.

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

### How?

Looks at each adjacent pair of 0-indexed nodes in the input list. If the integer division by three of the two differs by 2 they are on the top and bottom rows, if the modulo by three of the two differs by 2 they are in the left and right columns. The sum of such pairs divided by two is either the 0-indexed mid-node of a three-node-line or a non-integer value -- so these values are first inserted in-front of the 0-indexed pair and then any bogus nodes (like `0.5` or `3.5`) are removed, the resulting list of lists is flattened and then de-duplicated (to yield order-preserved, unique entries) and finally compared to the input - for a legal swipe all of this will end up being a no-op while illegal ones will add missing mid-nodes and/or remove duplicate nodes (note that no special casing is required for an input list of length 1 since it has no adjacent pairs):

```
d3ZIỊoSH;µƝFḞƑƇQ⁼ - left input is a list of integers   e.g. [3,4,7,1,2,8,3]
         µƝ       - perform the chain to the left for adjacent pairs:
                  - e.g. for [a,b] in:   [3,4]         [4,7]         [7,1]         [1,2]         [2,8]         [8,3]
d3                -   divmod by 3        [[1,0],[1,1]] [[1,1],[2,1]] [[2,1],[0,1]] [[0,1],[0,2]] [[0,2],[2,2]] [[2,2],[1,0]]
  Z               -   transpose          [[1,1],[0,1]] [[1,2],[1,1]] [[2,0],[1,1]] [[0,0],[1,2]] [[0,2],[2,2]] [[2,1],[2,0]]
   I              -   differences        [0,1]         [1,0]         [-2,0]        [0,1]         [2,0]         [-1,-2]
    Ị             -   abs(v)<=1          [1,1]         [1,1]         [0,1]         [1,1]         [0,1]         [1,0]
      S           -   sum (of [a,b])      7            11            8              3            10            11
     o            -   OR (vectorises)    [1,1]         [1,1]         [8,1]         [1,1]         [10,1]        [1,11]
       H          -   halve (vectorises) [0.5,0.5]     [0.5,0.5]     [4,0.5]       [0.5,0.5]     [5,0.5]       [0.5,5.5]
        ;         -   concatenate        [0.5,0.5,3,4] [0.5,0.5,4,7] [4,0.5,7,1]   [0.5,0.5,1,2] [5,0.5,2,8]   [0.5,5.5,8,3]
           F      - flatten              [0.5,0.5,3,4,  0.5,0.5,4,7,  4,0.5,7,1,    0.5,0.5,1,2,  5,0.5,2,8,    0.5,5.5,8,3]
              Ƈ   - keep those for which:
             Ƒ    -   is invariant under?:
            Ḟ     -     floor            [        3,4,          4,7,  4,    7,1,            1,2,  5,    2,8,           ,8,3]
               Q  - deduplicate          [3,4,7,1,2,5,8]
                ⁼ - equal to the input?  e.g. 0 (here because 5 was introduced AND because 3 was removed from the right)

```

---

Previous method

Jelly,  ~~36~~  35 bytes

```
9s3;Z$;“Æ7a‘DZ¤;U$;©0m€2iị®oµƝFQ⁼ȧȦ

```

Try it online! or see a test-suite.

### How?

Similar to the above but constructs all three-node-line possibilities and performs look-up (rather than checking as it goes using divmod to test and halving the sum for the mid-node).

Firstly the construction of the list of three-node-lines:

```
9s3;Z$;“Æ7a‘DZ¤;U$;©0
9s3                   - nine (implicit range) split into threes = [[1,2,3],[4,5,6],[7,8,9]]
     $                - last two links as a monad:
    Z                 -   transpose = [[1,4,7],[2,5,8],[6,7,9]]
   ;                  -   concatenate = [[1,2,3],[4,5,6],[7,8,9],[1,4,7],[2,5,8],[3,6,9]]
              ¤       - nilad followed by link(s) as a nilad:
       “Æ7a‘          -   code-page index list = [13,55,97]
            D         -   decimal (vectorises) = [[1,3],[5,5],[9,7]]
             Z        -   transpose = [[1,5,9],[3,5,7]]
      ;               - concatenate = [[1,2,3],[4,5,6],[7,8,9],[1,4,7],[2,5,8],[3,6,9],[1,5,9],[3,5,7]]
                 $    - last two links as a monad:
                U     -   upend = [[3,2,1],[6,5,4],[9,8,7],[7,4,1],[8,5,2],[9,6,3],[9,5,1],[7,5,3]]
               ;      -   concatenate = [[1,2,3],[4,5,6],[7,8,9],[1,4,7],[2,5,8],[3,6,9],[1,5,9],[3,5,7],[3,2,1],[6,5,4],[9,8,7],[7,4,1],[8,5,2],[9,6,3],[9,5,1],[7,5,3]]
                    0 - literal zero (to cater for non-matches in the main link since ị, index into, is 1-based and modular the 0th index is the rightmost)
                  ;   - concatenate = [[1,2,3],[4,5,6],[7,8,9],[1,4,7],[2,5,8],[3,6,9],[1,5,9],[3,5,7],[3,2,1],[6,5,4],[9,8,7],[7,4,1],[8,5,2],[9,6,3],[9,5,1],[7,5,3],0]
                   ©  - copy the result to the register

```

Now the decision making:

```
...m€2iị®oµƝFQ⁼ȧȦ - left input is a list of integers               e.g. [4,5,8,2,3,9,4]
          µƝ      - perform the chain to the left for adjacent pairs:
                  - i.e. for [a,b] in [[4,5],[5,8],[8,2],[2,3],[3,9],[9,4]]
...               -   perform the code described above = [[1,2,3],[4,5,6],[7,8,9],[1,4,7],[2,5,8],[3,6,9],[1,5,9],[3,5,7],[3,2,1],[6,5,4],[9,8,7],[7,4,1],[8,5,2],[9,6,3],[9,5,1],[7,5,3],0]
   m€2            -   modulo-2 slice €ach = [[1,3],[4,6],[3,9],[1,7],[2,8],[6,9],[1,9],[3,7],[3,1],[6,4],[9,7],[7,1],[8,2],[9,3],[9,1],[7,3],[0]]
      i           -   index of [a,b] in that (or 0 if not there)    e.g. [0,0,13,0,6,0]
        ®         -   recall from register = [[1,2,3],[4,5,6],[7,8,9],[1,4,7],[2,5,8],[3,6,9],[1,5,9],[3,5,7],[3,2,1],[6,5,4],[9,8,7],[7,4,1],[8,5,2],[9,6,3],[9,5,1],[7,5,3],0]
       ị          -   index into (1-based & modular)     e.g. [0,0,[8,5,2],0,[3,6,9],0]
         o        -   OR [a,b]           e.g. [[4,5],[5,8],[8,5,2],[2,3],[3,6,9],[9,4]]
            F     - flatten                          e.g. [4,5,5,8,8,5,2,2,3,3,6,9,9,4]
             Q    - deduplicate                                    e.g. [4,5,8,2,3,6,9]
              ⁼   - equal to the input?                            e.g. 0 (here because 6 was introduced AND because 4 was removed from the right)
                Ȧ - any and all? (0 if input is empty [or contains a falsey value when flattened - no such input], 1 otherwise)
               ȧ  - AND (to force an empty input to evaluate as 1 AND 0 = 0)

```
> 19 votes

# Answer
# Stax, 28 bytes

```
æ¡_t¿♂≥7▼├öä▒╨½╧£x╪╨┌i╒ë╖¢g•

```

Run it

It produces 0 for false, and positive integers for true. The corresponding ascii representation of the same program is this.

```
cu=x%v*x2BF1379E-%_|+YA=!*yhxi(#+*

```

The general idea is calculate several necessary conditions for legal swipe patterns and multiply them all together.

```
cu=                                 First: no duplicates
   x%v*                             Second: length of input minus 1
       x2B                          Get all adjacent pairs
          F                         For each pair, execute the rest
           1379E-%                  a) Any digits that are not 1, 3, 7, 9?
                  _|+Y              Get sum of pair, and store in Y register
                      A=!           b) Sum is not equal to 10?
                         *          c) multiply; logical and: a, b
                          yh        half of y; this will be equal to the
                                        number directly between the current
                                        pair if there is one
                            xi(#    d) has the middle number been observed yet?
                                +   e) plus; logical or: c, d
                                 *  multiply by the accumulated value so far

```
> 16 votes

# Answer
# JavaScript, 112 bytes

```
x=>/^(?!.*(.).*\1|[^5]*(19|28|37|46|91|82|73|64)|[^2]*(13|31)|[^8]*(79|97)|[^4]*(17|71)|[^6]*(39|93))../.test(x)

```

Maybe some regex based language should be more shorter. But I don't know.

```
f=
x=>/^(?!.*(.).*\1|[^5]*(19|28|37|46|91|82|73|64)|[^2]*(13|31)|[^8]*(79|97)|[^4]*(17|71)|[^6]*(39|93))../.test(x)
```

```
<input id=i oninput=o.value=(f(i.value)?'':'in')+'valid'> is <output id=o>
```

Thanks to Neil, change `)(?!` to `|` save 3 bytes.
> 11 votes

# Answer
# Husk, ~~25~~ 20 bytes

```
S=öufΛ¦1ΣẊ§Jzo½+em‰3

```

Takes a list of integers with 0-based indexing. Returns 0 or 1. Try it online!

## Explanation

I stole some ideas from Jonathan Allan's Jelly answer. The idea is the same: insert a new "average node" between each adjacent pair, filter out those that are not actual nodes, remove duplicates and compare to the original list. If the original list contains duplicates, the result is falsy. If the list skips an unvisited node, then it is present in the processed list between the corresponding pair, and the result is falsy. If the input is a singleton, the processed list is empty, and the result is falsy. Otherwise, it is truthy.

```
S=öufΛ¦1ΣẊ§Jzo½+em‰3  Implicit input, say [0,4,6,7,1]
                 m‰3  Divmod each by 3: L = [[0,0],[1,1],[2,0],[2,1],[0,1]]
         Ẋ§Jzo½+e     This part inserts the middle node between adjacent nodes.
         Ẋ            Do this for each adjacent pair, e.g. [1,1],[2,0]:
          §           Apply two functions and combine results with third.
            zo½+      First function:
            z         Zip with
               +      addition,
             o½       then halve: N = [3/2,1/2]
                e     Second function: pair: P = [[1,1],[2,0]]
           J          Combining function: join P with N: [[1,1],[3/2,1/2],[2,0]]
                      Result is a list of such triples.
        Σ             Concatenate: [[0,0],[1/2,1/2],[1,1],[1,1],[3/2,1/2],...,[0,1]]
    f                 Keep only those pairs
     Λ                both of whose elements
      ¦1              are divisible by 1, i.e. are integers: [[0,0],[1,1],[1,1],,...,[0,1]]
   u                  Remove duplicates: [[0,0],[1,1],[2,0],[2,1],[0,1]]
S=ö                   Is the result equal to L? Implicitly print 1 or 0.

```
> 8 votes

# Answer
# Retina 0.8.2, 98 bytes

Influenced by tsh's answer. I tried to "rephrase" it to be the opposite, matching invalid swipes, then Anti-grepping.

```
A`(.).*\1|^([^5]*(19|28|37|46|91|82|73|64)|[^2]*(13|31)|[^8]*(79|97)|[^4]*(17|71)|[^6]*(39|93)|.$)

```

**Try it online**
> 7 votes

# Answer
## C++, ~~267~~ 256 bytes

```
#define R)return 0
#define H(a,q)if(d==q&&n==a&&!m[a]R;
int v(int s[],int l){if(l<2 R;int m[10]{},i=1,p=s[0],d,n;for(;i<l;++i){m[p]=1;if(m[s[i]]R;d=(d=p-s[i])<0?-d:d;if(d%2<1){n=(p+s[i])/2;H(5,4)H(5,8)H(2,2)H(5,2)H(8,2)H(4,6)H(5,6)H(6,6)}p=s[i];}return 1;}

```

To check if the pattern does not skip over a unvisited node, it does several things :

1. Calculate `d` where `d` is the numerical difference between the current node and the last node.
2. If `d` is odd, then there's no need to check, it can't skip over a node.
3. If `d` is equal to `4` or `8`, then the jump is between nodes `1-9` or `3-7`, so check node `5`
4. If `d` is 2, and the middle node ( `(last_node + current_node)/2` ) is either 2,5 or 8, then check the middle node
5. If `d` is 6, same check as before but with `4`,`5` or `6`

The parameters are an `int[]` and it's element count. It returns an `int` which can be interpreted as a `bool` type
> 4 votes

# Answer
# MATL, ~~42~~ ~~41~~ 39 bytes

```
9:IeXKi"Ky@=&fJ*+XK+y&fJ*+Em~zw0@(]z8<v

```

This produces

* a non-empty column vector containing only *non-zero numbers* as truthy output; or
* a non-empty column vector containing *at least a zero* as falsy.

Here you can read why these outputs are respectively truthy and falsy. **Try it online!**

Or **verify all test cases**, with footer code that includes the standard test for truthiness/falsiness.
> 3 votes

# Answer
# Perl, 135 bytes (134 + `-n`)

```
@a{split//}=1;(@{[/./g]}==keys%a&&/../)||die();for$c(qw/132 465 798 174 285 396 195 375/){$c=~/(.)(.)(.)/;/^[^$3]*($1$2|$2$1)/&&die()}

```

Slightly ungolfed version

```
@a{split//} = 1;
(@{[/./g]} == keys %a && /../) || die();
for $c (qw/132 465 798 174 285 396 195 375/) {
  $c=~/(.)(.)(.)/;
  /^[^$3]*($1$2|$2$1)/&&die()
}

```

Outputs via exit code. `0` is truthy, any other value is falsy. As per meta consensus, STDERR output in the failure case is ignored.

There's probably a quicker way to check the "can't jump over" rule than simply listing all the possibilities.
> 3 votes

# Answer
# Stax, ~~73~~ ~~72~~ ~~66~~ 65 bytesCP437

```
ÉWyƒ▬ºJOTƒw-H┌↓&ⁿç↨¼<ü6π║¢S○j⌂zXΣE7≈╩╕╤ö±÷C6▒☼■iP-↑⌐¥]╩q|+zΦ4Φ·¥Ω

```

79 bytes when unpacked,

```
d4{cAs-5F132396978714EEL3/{xs:IBc0<A*++cEd:-1=sccHs|M=s{U>m|A**mEx%2<xu%x%=!L|+

```

Run and debug online!

or run the batch test, where `meX` is a header so that Stax can process multiline input.

Implementation without using hash.Outputs strictly positive number (actually the number of failed tests) for **falsy** cases and `0` for **truthy** ones.

## Explanation

`d` clears the input stack. The input is in variable `x` anyway.

`4{cAs-5F` generates first part of the middle-node list.

`132396978714EE` hardcodes the second part of the middle-node list.

`L3/` Collects all elements in main stack and divide into parts each containing 3 elements, the result is array `a`, which is just the array of all invalid 3-node groups.

`{xs:IBc0<A*++cEd:-1=sccHs|M=s{U>m|A**mE` For each invalid node list, perform the following checks. The result of the check results are `and`ed using the `**`. Since there are 8 invalid node lists, the result of this code will be an array of 8 elements. The final `E` dispatches the array to its individual elements on the main stack.

`xs:I` get the index of the node list elements in the input array.

`Bc0<A*++` If the index of "middle node" (e.g. `5` in the node set `1,5,9`) is `-1` (which means it doesn't exist in the input array), change the index to `9`.

`cEd:-1=` test whether the two "terminal nodes" (e.g. `1,5` in the node set `1,5,9`) are adjacent in the input array.

`sccHs|M=` test whether the transformed index of the "middle node" is larger than those of the two "terminal nodes", which includes two cases: the "middle node" is missing, or the "middle node" comes after the two "terminal nodes"

`s{U>m|A` tests whether both indexes of the "end nodes" are nonnegative. (i.e. they both appear in the input).

Two additional tests are performed,

`x%2<` tests whether the input array is a singleton.

`xu%x%=!` tests whether are nodes that have been visited twice.

There are 10 test result on the main stack (one for each of the invalid node list, plus two additional tests).

`L|+` collects the 10 elements and adds them. `|a` could have also been used which simply checks whether there are any truthy elements on the array.

Implicit output.
> 3 votes

# Answer
## Java, ~~375~~ 355 bytes

-20 bytes thanks to Zacharý

```
int v(int s[]){int[]m=new int[10];int i=1,p=s[0],d,n,l=s.length;if(l<2)return 0;for(;i<l;++i){m[p]=1;if(m[s[i]]!=0)return 0;d=(d=p-s[i])<0?-d:d;if(d%2==0){n=(p+s[i])/2;if((d==4||d==8)&&n==5&&m[5]==0)return 0;if(d==2&&(n==2&&m[2]==0||n==5&&m[5]==0||n==8&&m[8]==0))return 0;if(d==6&&(n==4&&m[4]==0||n==5&&m[5]==0||n==6&&m[6]==0))return 0;}p=s[i];}return 1;}

```

This is a port of this answer and it works on the same principles
> 3 votes

# Answer
# Python 2, 97 bytes

Based on ovs' answer but 2 bytes shorter and less cryptic. Just converts indexes to 2d coordinates and tests parity. Assumes 0-8 indexes.

```
v={9}
s=input()
for n,l in zip(s[1:]or q,s):n/3+l/3&1|n%3+l%3&1or n+l>>1in v or q;v|={l};n in v>q

```

Try it online!
> 3 votes

# Answer
# Japt, 35 bytes

```
eUä@[(Xu3 aYu3)¥1ªX+Y ÷2XY]Ãc f9o)â

```

Try it online!

### Slightly ungolfed & How it works

```
eUä@[(Xu3 aYu3)¥1ªX+Y ÷2XY]Ãc f9o)â

Implicit beginning U(input) and some arbitrary sequence conversions

UeUä@[(Xu3 aYu3)==1||X+Y ÷2XY]} c f9o)â

  Uä             Convert the input array into length-2 subsections and map...
    @[ ... ]}      function of X,Y which returns an array of...
      Xu3 aYu3==1||X+Y ÷2          (abs(X%3 - Y%3)==1||X+Y)/2,
                         XY        X, Y
  c              Flatten the result of mapping
    f9o          Intersect with range(9)
        â        Take unique elements, preserving order
Ue             Is the result the same as original array?

```

Ported the idea from this Jelly solution, with some difference in determining potential jumps:

* The Jelly answer uses divmod to see if a pair has difference of 2 when applied `/3` or `%3`.
* This answer uses only `%3` and checks if the difference is 0 or 2. If the difference is 0, the two cells are vertically aligned, and non-jumps still share the property of `(X+Y)%2 != 0`.
> 2 votes

# Answer
# Vyxal, 26 bytes

```
2lƛ∑n3vḋ∩vƒ-vṅv∨½p;f~¨=⌊U⁼

```

Try it Online!

Port of Jelly.
> 2 votes

# Answer
# Pyth, 33 bytes

```
q{@U9.nm+mc|g1aZksd2-MC.DR3d_dC,t

```

**Test suite.**

Uses 0-based indexing.

## Explanation

```
q{@U9.nm+mc|g1aZksd2-MC.DR3d_dC,t –> Full program. Input: a list L from STDIN.

                               ,t –> Pair L with L without the first element.
                              C   –> Transpose.
       m                          –> Map over the list of pairs (2-element lists):
        +mc|g1aZksd2-MC.DR3d      –> The function to be mapped (variable: d):
                         R d          –> For each element of d ...
                       .D 3           –> ... Take its divmod by 3.
                      C               –> Tranpose.
                    -M                –> Reduce each by subtraction.
         m                            –> For each difference (variable: k):
            g1aZl                     –> Is |k| ≤ 1?
           |     sd                   –> If that's falsy, replace it by the sum of d.
          c        2                  –> Divide by 2.
        +                   _d    –> Append the reverse of d to the result of mapping.
     .n                           –> Flatten.
  @U9                             –> Take the intersection with (ℤ ∩ [0; 9)).
 {                                –> Deduplicate.
q                                 –> And check whether the result equals L.

```

Alternative approach for **34 bytes**:

```
q{sI#I#+Fm+,hdcR2+MCd]edCtBK.DR3QK

```
> 1 votes

# Answer
# Haskell, 97 bytes

```
(%)=elem
f(h:t)=t>[]&&and[x%a<(gcd(x*v)10>1&&x+v/=10||div(x+v)2%a)|x:a@(v:_)<-scanl(flip(:))[h]t]

```

Try it online!

Make sure `t>[]` (so length ≥ 2), and then: for each reversed-prefix matching `x:a@(v:_)`, check whether visiting `x` when coming from `v` (and having visited all of `a` so far) is valid.

Going from `v` to `x` is legal under these conditions:

* `x%a<` — we have not yet visited `x`, and…
* `gcd(x*v)10>1&&x+v/=10``v` and `x` are *not* opposites, or
    + `div(x+v)2%a` — if they are, at least we've visited the number between them.

Flipped back around, our "opposites check" is `gcd(x*v)10==1||x+v==10`. The `gcd` trick works because `x*v` can only be coprime to 10 if both of `x` or `v` are among `[1,3,7,9]` (opposing corners). Then, `x+v==10` takes care of the even digits.
> 1 votes

# Answer
# 05AB1E, 25 bytes

```
ü‚εODÈ*y3‰øÆÄ2@·÷0Ky«}˜ÙQ

```

Port of *@JonathanAllan*'s Jelly answer, so make sure to upvote him!!

Input as a 0-based list of digits.

Try it online or verify all test cases.

**Explanation:**

```
ü‚             # Create overlapping pairs of the (implicit) input-list:
               #  i.e. [3,4,7,1,2,8,3] → [[3,4],[4,7],[7,1],[1,2],[2,8],[8,3]]
  ε            # Map each pair `y` to:
   O           #  Take the sum of the pair
               #   → [7,11,8,3,10,11]
    DÈ         #  Duplicate the sum, and check whether it's even (1 if truhy; 0 if falsey)
               #  → [0,0,1,0,1,0]
      *        #  And multiply it by the sum
               #  → [0,0,8,0,10,0]
   y           #  Push the current pair again
    3‰         #  Take the divmod-3 on both values
               #   → [[[1,0],[1,1]],[[1,1],[2,1]],[[2,1],[0,1]],[[0,1],[0,2]],[[0,2],[2,2]],[[2,2],[1,0]]]
      ø        #  Zip/transpose; swapping rows/columns
               #   → [[[1,1],[0,1]],[[1,2],[1,1]],[[2,0],[1,1]],[[0,0],[1,2]],[[0,2],[2,2]],[[2,1],[2,0]]]
       Æ       #  Reduce each by subtracting
               #   → [[0,-1],[-1,0],[2,0],[0,-1],[-2,0],[1,2]]
        Ä      #  Take the absolute value of each
               #   → [[0,1],[1,0],[2,0],[0,1],[2,0],[1,2]]
         2@    #  Check for each that it's >=2 (1 if truthy; 0 if falsey)
               #   → [[0,0],[0,0],[1,0],[0,0],[1,0],[0,1]]
           ·   #  Double each
               #   → [[0,0],[0,0],[2,0],[0,0],[2,0],[0,2]]
            ÷  #  (Integer-)divide the earlier sum by this,
               #  where dividing by 0 results in 0 in this 05AB1E version
               #   → [[0,0],[0,0],[4,0],[0,0],[5,0],[0,0]]
 0K            #  Remove all 0s
               #   → [[],[],[4],[],[5],[]]
   y«          #  Merge the pair to it
               #   → [[3,4],[4,7],[4,7,1],[1,2],[5,2,8],[8,3]]
}˜             # After the map: flatten the list
               #  → [3,4,4,7,4,7,1,1,2,5,2,8,8,3]
  Ù            # Uniquify it
               #  → [3,4,7,1,2,5,8]
   Q           # And check whether it's equal to the (implicit) input-list
               #  → 0 (falsey)
               # (after which this result is output implicitly)

```
> 0 votes

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


title: Ascii Fibonacci spiral

text:
# Question
Title: Ascii Fibonacci spiral
Let's continue the based challenges stream, here's the next one:

## Task

Draw a Fibonacci spiral of n segments where starting from the first term:

* each nth segment has a length of nth Fibonacci term.
* each segment is joined to the end of the previous, rotated by 90 degrees taking the end of previous segment as center of rotation.
* you can choose any printable ascii character chars to draw the spiral with, although the background must be spaces.
* You can draw the spiral in any orientation and turning clockwise or counterclockwise
* Leading/trailing whitespace is allowed within reason

## Example

Let's explain it with the help of a visual example:
Beginning of segments are highlighted with an arrow character (\> \< ^ v) to indicate the direction.
End of segments highlighted with `o` to indicate the pivot for the rotation of next segment.

Taking the first 9 terms \[0,1,1,2,3,5,8,13,21\] (the first term(0) doesn't draw anything) we draw clockwise.

```
o###################<o
                     #
                     #
                     #
                     #
                     #
                     #
                     #
             o#<o    #
             v  ^    #
             # oo    #
             #       #
             #       ^
             o>######o

```

As you can see we start with one character(a segment of length 1) then add one to the right, then add two by rotating 90 degrees, then 3, then 5 .. and so on.

You can choose 0 or 1 indexing in the Fibonacci sequence, f(0) can draw anything or a single character, just be consistent on this.

# Some more examples

n==1 (0-indexed) or n==0 (1-indexed)-\> \[1\]

```
*

```

n==2 -\> \[1,1\]

```
2     1          or 21
1  or 2  or 12

```

here we used '1' for the first segment and '2' for the second

n==3 -\>\[1,1,2\]

```
1     or 12  or...
233       3
          3

```

## Rules

* This is : all the usual golfing rules apply.
* Either a function or a full program is fine.
* Input/output can be given by any convenient method.

# Answer
# MATL, 25 bytes

```
TF0i:"P!1bYs:Q1&(3MPw]Zc&

```

Try it online!

### Explanation

```
TF     % Push [1, 0]. This array will contain the two most recent Fibonacci
       % numbers in each iteration k: [f(k), f(k-1)]
0      % Push 0. This initiallizes the matrix M that will be used as output
i:"    % Input n. Do the following n times
  P!   %   Flip vertically, transpose. This rotates tmatrix M by 90 degrees
  1    %   Push 1 (*)
  b    %   Bubble up: moves the array [f(k), f(k-1)] to the top of the stack
  Ys   %   Cumulative sum: gives [f(k), f(k+1)]
  :    %   Range (uses first entry): [1, 2, ..., f(k)]
  Q    %   Add 1, element-wise: gives [2, 3, ..., f(k)+1] (**)
  1    %   Push 1 (***)
  &(   %   Write 1 (*) in M at the rows given by (**) and column 1 (***).
       %   This extends M with the new segment of the spiral, padding with 0
  3M   %   Push [f(n), f(n+1)] again
  P    %   Flip: gives [f(n+1), f(n)], ready for the next iteration
  w    %   Swap: moves the extended M to the top of the stack
]      % End
Zc     % Convert values 1 in M into char '#', and 0 to space
&      % Set alternative input/output spec for the next function, which is
       % implicit display. This causes the function to use only one input,
       % which means that only the top of the stack is displayed

```
> 3 votes

# Answer
# Python 3.8 (pre-release), 99 bytes

```
f=lambda n:' #'[2*n:]or[k:='#'+''.join(l[1:])for l in zip(*f(n-1)[::-1])]+(k:=len(k)-1)*['#'+' '*k]

```

Try it online!
> 2 votes

# Answer
# 05AB1E, 9 bytes

```
LÅf0ŽPjSΛ

```

Try it online.

0-based and the spiral goes counterclockwise starting towards the left, similar as the example in the challenge.
Input \\$n=0\\$ will always draw a single character instead of an empty output.
Draws with character `0`, but this could alternatively be any other digit, the lowercase alphabet, the input digits, the digits of the 0-based \\$n^{th}\\$ Fibonacci number, etc. by replacing the `0`.
The start and direction of the spiral can also be changed by replacing `ŽPjS` with `Ž8O` for right counterclockwise; `ŽG~S` for down counterclockwise; `ŽNāS` for left clockwise; `Ƶ‘0š` for up clockwise; `Ž9¦S` for right clockwise; or `ŽICS` for down clockwise (up counterclockwise is the only one that's a byte longer with `Ž2„0š`).

**Explanation:**

```
L          # Push a list in the range [1, (implicit) input-integer]
 Åf        # Get the (0-based) n'th Fibonacci number for each of these values
   0       # Push character "0"
    ŽPj    # Push compressed integer 6420
       S   # Pop and convert it to a list of digits: [6,4,2,0]
        Λ  # Use the Canvas builtin with these three arguments
           # (which is output immediately afterwards implicitly)

```

See this 05AB1E tip of mine (section *How to compress large integers?*) to understand why `ŽPj` is `6420`.

As for some additional information about the Canvas builtin `Λ`:
It takes 3 arguments to draw an ASCII shape:

1. Length of the lines we want to draw
2. Character/string to draw
3. The direction to draw in, where each digit represents a certain direction:

```
7   0   1
  ↖ ↑ ↗
6 ← X → 2
  ↙ ↓ ↘
5   4   3

```

`LÅf0Ž8OS` creates the following Canvas arguments:

1. Length: the first input amount of 1-based Fibonacci numbers
2. Character: `"0"`
3. Directions: `[6,4,2,0]`, which translates to \\$\[←,↓,→,↑\]\\$

Step 1: Draw 1 characters (`"0"`) in direction 6/:

```
0

```

Step 2: Draw 1-1 characters (`""`) in direction 4/:

```
0

```

Step 3: Draw 2-1 characters (`"0"`) in direction 2/:

```
00

```

Step 4: Draw 3-1 characters (`"00"`) in direction 0/:

```
 0
 0
00

```

Step 5: Draw 5-1 characters (`"000"`) in direction 6/:

```
00000
    0
   00

```

Step 6: Draw 8-1 characters (`"0000000"`) in direction 4/:

```
00000
0   0
0  00
0
0
0
0
0

```

etc.

See this 05AB1E tip of mine for an in-depth explanation of the Canvas builtin.
> 2 votes

# Answer
# Canvas, 17 bytes

```
０１⁸┤［┌┌＋｝）Ｈ#×２１╋↶

```

Try it here!
> 2 votes

# Answer
# Vyxal, 11 bytes

```
×3ʀd⁰ɽ∆f›ø∧

```

Try it Online!

*-1 byte thanks to emanresu A*
> 2 votes

# Answer
# Jelly, 22\*? 27 bytes

```
ÆḞ€R¬W€1¦t⁶;ɗ€0¦Ṛz⁶ʋ/ZṚ$⁸¡Y

```

A full program that accepts an integer and prints a spiral using `1`s.

**Try it online!**

### How?

```
ÆḞ€R¬W€1¦t⁶;ɗ€0¦Ṛz⁶ʋ/ZṚ$⁸¡Y - Main Link: integer, N
ÆḞ€                         - first N Fibbonacci numbers
   R                        - range       -> [[1],[1],[1,2],[1,2,3],[1,2,3,4,5],...]
    ¬                       - logical NOT -> [[0],[0],[0,0],[0,0,0],[0,0,0,0,0],...]
     W€1¦                   - wrap the first one
                   ʋ/       - reduce by - f(Current, Next):
            ɗ€0¦            -   apply to the final entry of Current:
         t⁶;                -     trim spaces and concatenate Next
                Ṛ           -     reverse
                 z⁶         -     transpose with spaces
                       $⁸¡  - repeat N times:
                     Z      -   transpose
                      Ṛ     -   reverse
                          Y - join with newline characters
                            - implicit print

```

---

* Awaiting clarification on whether "output can be rotated so that the last segment is always in the same direction" - 22:

```
ÆḞ€R¬W€1¦t⁶;ɗ€0¦Ṛz⁶ʋ/Y

```
> 1 votes

# Answer
# Charcoal, 18 bytes

```
⊞υ¹ＦＮ«⌈υ↶⊞υΣ…⮌υ²»¹

```

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

```
⊞υ¹

```

Start with `1`.

```
ＦＮ«

```

Repeat `n` times.

```
⌈υ

```

Output the latest Fibonacci number in unary.

Rotate ready for the next Fibonacci number.

```
⊞υΣ…⮌υ²

```

Calculate the next Fibonacci number.

```
»¹

```

Print a final character (this is because Charcoal is actually drawing the lines a character early, so it's drawing `1, 2, 3, 5, 8...` and the second `1` is missing).

It's possible to draw the lines according to the specification by rotating for the last character of the line, but in this case the spiral has to be drawn clockwise instead:

```
⊞υ¹ＦＮ«¶⌈υ¶↷⊞υΣ✂υ±²

```

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

```
⊞υ¹

```

Start with `1`.

```
ＦＮ«

```

Repeat `n` times.

```
¶⌈υ¶

```

Output the latest Fibonacci number in unary, but positioned rotated from the end of the previous one.

Rotate ready for the next Fibonacci number.

```
⊞υΣ✂υ±²

```

Calculate the next Fibonacci number, but repeating the initial `1` the first time.
> 1 votes

# Answer
# Python3, 326 bytes:

```
R=range
f=lambda n,a=1,b=1:[b]+f(n-1,b,a+b)if n else[]
def g(b,e,x,y,q,w):
 if e:x+=q;y+=w;b[x][y]=1;return g(b,e-1,x,y,q,w)
 return x,y
def d(b,r,x,y,c=1):
 if r:d(b,r,*g(b,r.pop(),x,y,0+c%2*[1,-1][c%4==1],0+(c%2==0)*[-1,1][c%4==2]),c+1)
def F(n):
 r=f(n);b=[[0 for _ in R(r[-2]+1)]for _ in R(r[-1])];d(b,r,len(b),0);return b

```

Try it online!
> 0 votes

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