title: Fond Memories of Past Primes

text:
# Question
Title: Fond Memories of Past Primes
Consider a prime number *p*, written in base 10. The **memory** of *p* is defined as the number of distinct primes strictly less than *p* that are contained as substrings of *p*.

## Challenge

Given a non-negative integer *n* as input, find the smallest prime *p* such that *p* has memory *n*. That is, find the smallest prime with exactly *n* distinct strictly lesser primes as substrings.

## Input

Input can be taken through any standard format. You must support input up to the largest *n* such that the output does not overflow. For reference, 4294967291 is the largest prime in 32 bits.

## Output

Output may be written to STDOUT or returned from a function.

## Examples

The number 2 has memory 0 since it contains no strictly lesser primes as substrings.

The number 113 is the smallest prime with memory 3. The numbers 3, 13, and 11 are the only prime substrings and no prime smaller than 113 contains exactly 3 primes as substrings.

The first 10 terms of the sequence, beginning with *n* = 0, are

```
2, 13, 23, 113, 137, 1237, 1733, 1373, 12373, 11317

```

## Note

This is A079397 in OEIS.

## Leaderboard

```
var QUESTION_ID=55406,OVERRIDE_USER=20469;function answersUrl(e){return"http://api.stackexchange.com/2.2/questions/"+QUESTION_ID+"/answers?page="+e+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+ANSWER_FILTER}function commentUrl(e,s){return"http://api.stackexchange.com/2.2/answers/"+s.join(";")+"/comments?page="+e+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+COMMENT_FILTER}function getAnswers(){jQuery.ajax({url:answersUrl(answer_page++),method:"get",dataType:"jsonp",crossDomain:!0,success:function(e){answers.push.apply(answers,e.items),answers_hash=[],answer_ids=[],e.items.forEach(function(e){e.comments=[];var s=+e.share_link.match(/\d+/);answer_ids.push(s),answers_hash[s]=e}),e.has_more||(more_answers=!1),comment_page=1,getComments()}})}function getComments(){jQuery.ajax({url:commentUrl(comment_page++,answer_ids),method:"get",dataType:"jsonp",crossDomain:!0,success:function(e){e.items.forEach(function(e){e.owner.user_id===OVERRIDE_USER&&answers_hash[e.post_id].comments.push(e)}),e.has_more?getComments():more_answers?getAnswers():process()}})}function getAuthorName(e){return e.owner.display_name}function process(){var e=[];answers.forEach(function(s){var r=s.body;s.comments.forEach(function(e){OVERRIDE_REG.test(e.body)&&(r="<h1>"+e.body.replace(OVERRIDE_REG,"")+"</h1>")});var a=r.match(SCORE_REG);a&&e.push({user:getAuthorName(s),size:+a[2],language:a[1],link:s.share_link})}),e.sort(function(e,s){var r=e.size,a=s.size;return r-a});var s={},r=1,a=null,n=1;e.forEach(function(e){e.size!=a&&(n=r),a=e.size,++r;var t=jQuery("#answer-template").html();t=t.replace("{{PLACE}}",n+".").replace("{{NAME}}",e.user).replace("{{LANGUAGE}}",e.language).replace("{{SIZE}}",e.size).replace("{{LINK}}",e.link),t=jQuery(t),jQuery("#answers").append(t);var o=e.language;/<a/.test(o)&&(o=jQuery(o).text()),s[o]=s[o]||{lang:e.language,user:e.user,size:e.size,link:e.link}});var t=[];for(var o in s)s.hasOwnProperty(o)&&t.push(s[o]);t.sort(function(e,s){return e.lang>s.lang?1:e.lang<s.lang?-1:0});for(var c=0;c<t.length;++c){var i=jQuery("#language-template").html(),o=t[c];i=i.replace("{{LANGUAGE}}",o.lang).replace("{{NAME}}",o.user).replace("{{SIZE}}",o.size).replace("{{LINK}}",o.link),i=jQuery(i),jQuery("#languages").append(i)}}var ANSWER_FILTER="!t)IWYnsLAZle2tQ3KqrVveCRJfxcRLe",COMMENT_FILTER="!)Q2B_A2kjfAiU78X(md6BoYk",answers=[],answers_hash,answer_ids,answer_page=1,more_answers=!0,comment_page;getAnswers();var SCORE_REG=/<h\d>\s*([^\n,]*[^\s,]),.*?(\d+)(?=[^\n\d<>]*(?:<(?:s>[^\n<>]*<\/s>|[^\n<>]+>)[^\n\d<>]*)*<\/h\d>)/,OVERRIDE_REG=/^Override\s*header:\s*/i;
```

```
body{text-align:left!important}#answer-list,#language-list{padding:10px;width:290px;float:left}table thead{font-weight:700}table td{padding:5px}
```

```
<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script> <link rel="stylesheet" type="text/css" href="//cdn.sstatic.net/codegolf/all.css?v=83c949450c8b"> <div id="answer-list"> <h2>Leaderboard</h2> <table class="answer-list"> <thead> <tr><td></td><td>Author</td><td>Language</td><td>Size</td></tr></thead> <tbody id="answers"> </tbody> </table> </div><div id="language-list"> <h2>Winners by Language</h2> <table class="language-list"> <thead> <tr><td>Language</td><td>User</td><td>Score</td></tr></thead> <tbody id="languages"> </tbody> </table> </div><table style="display: none"> <tbody id="answer-template"> <tr><td>{{PLACE}}</td><td>{{NAME}}</td><td>{{LANGUAGE}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr></tbody> </table> <table style="display: none"> <tbody id="language-template"> <tr><td>{{LANGUAGE}}</td><td>{{NAME}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr></tbody> </table>
```

# Answer
> 8 votes
# Pyth, 22 bytes

```
f&}TPTqQlf}YPY{sMP.:`T

```

Demonstration, Test Harness

Explanation:

```
f&}TPTqQlf}YPY{sMP.:`T
                          Implicit: Q = eval(input())
f                         Starting at T=1 and counting up, return the first T where
                    `T    repr(T)
                  .:      all substrings
                 P        except T itself
               sM         converted to integers
              {           unique examples only
         f                filter on
          }YPY            Y is in the prime factorization of Y, e.g. Y is prime.
      qQl                 Q == len of the above, that is, T has memory Q,
 &}TPT                    and T is prime, (is in its prime factorization.)

```

# Answer
> 7 votes
# CJam, ~~33~~ ~~31~~ 30 bytes

```
1{)__mp*{_mp2$s@s#)*},,easi^}g

```

This is a full program that reads the input as a command-line argument.

Try it online in the CJam interpreter.

### Test run

```
$ time cjam <(echo '1{)__mp*,{_mp2$s@s#)*},,easi^}g') 9
11317
real    0m3.562s
user    0m4.065s
sys     0m0.177s

```

### How it works

```
1       e# Push I := 1 on the stack.
{       e# Do:
  )__   e#   Increment I and push two copies.
  mp*   e#   Check the last copy for primality and multiply with the first copy.
        e#   This pushes R := I if I is prime and R := 0 if it is composite.
  {     e#   Filter; for each J in [0 ... R-1]:
    _mp e#     Push a copy of J and check for primality.
    2$s e#     Push a copy of I and cast to string.
    @s  e#     Rotate the original J on top of the stack and cast to string.
    #   e#     Find the index (-1 if not found) of the latter in the former.
    )*  e#     Increment the index and multiply it with the result from `mp'.
        e#     This yields 0 iff J is composite or not a subtring of I.
  },    e#   Keep J if the product is non-zero.
  ,     e#   Push the length of the filtered range.
  easi  e#   Cast the array of command-line arguments to string, then to integer.
  ^     e#   XOR it with the length of the filtered range.
}g      e# Repeat while theresult is non-zero.

```

# Answer
> 6 votes
# CJam, 40 bytes

```
li2sa{_)\{1$\#)},,3$-}{i{)_mp!}gsa+}w]W=

```

Try it online

I'm sure this comes as a big shocker, but it is in fact longer than the solution Dennis posted. Well, not really, since I didn't even have very high hopes myself. But I wanted to give it a shot anyway. And since it's working, looks pretty reasonable to me, and I believe it is sufficiently different to at least be of some interest, I thought I'd post it anyway.

The basic idea here is that I build a list of prime numbers in a loop, adding the next larger prime number to the list in each step. To check for termination, I count how many elements other than the last element in the list are a substring of the last element. If this count is equal to the input `n`, we're done.

Explanation:

```
li    Get input and convert to integer.
2sa   Seed list of primes with ["2"]. The primes are stored as strings to make
      the later substring search more streamlined.
{     Start of while loop condition.
  _   Copy list of primes.
  )     Pop off last prime from list.
  \     Swap remaining list to top.
  {     Start of filter block for substring matches with all smaller primes.
    1$    Copy test prime to top.
    \     Swap the smaller prime to top to get correct order for substring search.
    #     Search.
    )     Increment to get truthy value (Search returns -1 if not found).
  },    End of filter. We have a list of smaller primes that are substrings now.
  ,     Count list entries.
  3$    Copy input n to top.
  -     Subtract the two for comparison. If they are different, continue loop.
}     End of while loop condition.
{     Start of while loop body. We need to generate the next prime.
  i     The largest prime so far is still on the stack, but as string.
        Convert it to integer.
  {     Start of loop for prime candidates.
    )     Increment current candidate value.
    _mp   Check if it is prime.
    !     Negate, loop needs to continue if it is not a prime.
  }g    End loop for prime candidates. On exit, next prime is found.
  sa+   Convert it to string, and add it to list of primes.
}w    End of while loop body.
]W=   Solution is at top of stack. Discard other stack entries.

```

# Answer
> 4 votes
# Pyth - 25 bytes

Nested filter, inner to calculate memory, outer to find first that has required memory.

```
f&!tPTqlf&!tPY}`Y`TtStTQ2

```

Test Suite.

# Answer
> 3 votes
# Brachylog (2), 12 bytes, language postdates challenge

```
~{ṗ≜{sṗ}ᵘkl}

```

Try it online!

This was previously 13 bytes, using `ᶠd`, but that's now been given an abbreviation , cutting it down to 12. As the language postdates the challenge anyway, and the feature is one that wasn't added for this challenge in particular, I may as well use it.

As is usual in Brachylog, this is a function, not a full program.

## Explanation

```
~{ṗ≜{sṗ}ᵘkl}
~{         }  Find a value for which the following is true:
  ṗ             The value is prime;
   ≜            (evaluation strategy hint; avoids an infinite loop)
    {  }ᵘ       The set of unique
     sṗ         substrings which are prime
          l     has a length equal to {the input}
         k      when one element is removed.

```

This gives us the smallest prime with the property we want, because  checks values near 0 first.

# Answer
> 2 votes
## Octave / Matlab, 126 bytes

```
function p=f(n)
p=1;t=1;while t
p=p+1;t=~isprime(p)|sum(arrayfun(@(x)any(strfind(num2str(p),num2str(x))),primes(p)))~=n+1;end

```

Try it online

# Answer
> 2 votes
# JavaScript ES6, 106 bytes

```
n=>{for(a=[],i=2;a.filter(c=>(''+i).search(c)+1).length-n-1;a.push(i))while(!a.every(c=>i%c))i++;return i}

```

Here is an ungolfed version with explanation:

```
n=>{
  /**
   * a = list of primes
   * i = current integer
   * Iterate until number of members in a that are substring of i == n-1
   * After each iteration push the current value of i onto a
   */
  for(a=[],i=2; a.filter(c=>(''+i).search(c)+1).length-n-1; a.push(i)) {
    // Iterate until no member of a exactly divides i and increment i per iteration
    while(!a.every(c=>i%c)) i++;
  }
  return i;
}

```

Of course this gets horrendously slow rather quickly. However the OP has stated there is no limit on time.

# Answer
> 1 votes
# Julia, 86 bytes

```
n->for i=1:~0>>>1 isprime(i)&&sum(j->contains("$i","$j"),primes(i-1))==n&&return i;end

```

It's practically self-explanatory. Loop over all positive integers, and each time a prime is found, sum a boolean array indicating whether the set of primes less than the current one are substrings of the current one. If it finds one with the necessary number of matches, return that value.

Running time becomes sluggish for n=11, and likely for most values higher than 11 - specifically, on my laptop, n=11 takes about 33 seconds.

# Answer
> 1 votes
# Python 2, ~~163~~ 154 Bytes

I'm too tired to be golfing.. Hopefully when I wake up tomorrow I can improve this.

```
p=lambda n:all(n%x for x in range(2,n))
g=input()
s=2
while not(p(s)and len([l for l in[str(x)for x in range(2,s)if p(x)]if l in str(s)])==g):s+=1
print s

```

# Answer
> 1 votes
# Husk, 14 bytes

```
ḟ(=⁰#ṗumdQd)İp

```

Try it online!

# Answer
> 1 votes
# Vyxal, 14 bytes

```
λSǎ⌊Uæ∑?=næ∧;ṅ

```

Try it Online!

Takes input 1-indexed.

```
λ           ;ṅ # First positive integer where...
         næ    # Number is prime
           ∧   # And...
 Sǎ⌊U          # Unique substrings of number, as numbers
     æ∑        # Have a count of primes
       ?=      # Equal to the input?

```

# Answer
> 0 votes
## Haskell, ~~149~~ ~~147~~ 144 bytes

(127 bytes not counting the `import` declaration).

```
import Data.List
i x=x`elem`nubBy(((>1).).gcd)[2..x]
f n=[p|p<-[2..],i p,n==length(nub[x|x<-[read b|a<-tails$show p,b<-tail$inits a],i x])-1]!!0

```

> Prelude Data.List\> map f \[0..20\]
> \[2,13,23,113,137,1237,1733,1373,12373,11317,23719,Interrupted.

The above output was produced with the longer definition

```
i x=and$[x>1]++[rem x n>0|n<-[2..x-1]]

```

The new, 3 chars shorter, definition is much slower, I could only get 5 first numbers in the sequence before loosing patience and aborting.

# Answer
> 0 votes
# Haskell, ~~119~~ 118 bytes

```
p x=all((>0).mod x)[2..x-1]
f n=[y|y<-[2..],p y,n==sum[1|x<-[2..y-1],p x,elem(show x)$words=<<(mapM(:" ")$show y)]]!!0

```

Try it online! Usage: `f 3` yields `113`.

# Answer
> 0 votes
# PHP, 124 bytes

```
for($p=1;;){for($i=$c=0;$i-1;)for($i=++$p;$p%--$i;);$m[]=$p;foreach($m as$q)$c+=!!strstr($p,"$q");$c-1-$argv[1]?:die("$p");}

```

takes input from command line argument; run with `-r`.

**breakdown**

```
for($p=1;;)
{
    for($i=$c=0;$i-1;)for($i=++$p;$p%--$i;);    // find prime $p
    $m[]=$p;                                    // remember that prime
    foreach($m as$q)$c+=!!strstr($p,"$q");      // count memory primes
    $c-1-$argv[1]?:die("$p");                   // if memory==N, exit
}

```

# Answer
> 0 votes
# Python 2, 108 bytes

```
f=lambda n,x=2:n-sum(all(j%k for j in(i,x)for k in range(2,j))for i in range(2,x)if`i`in`x`)and f(n,x+1)or x

```

Try it online!

---
Tags: code-golf, string, primes
---


title: Stitch a hitomezashi pattern

text:
# Question
Title: Stitch a hitomezashi pattern
## Challenge

Given two binary vectors (containing two consistent values of your choice) of length \\$n\\$ and \\$m\\$, output a corresponding hitomezashi stitching pattern.

You are to fill the following pattern, where \\$n\\$ is the number of `A`-columns and \\$m\\$ is the number of `B`-rows:

```
 A A A A A
B+B+B+B+B+B
 A A A A A
B+B+B+B+B+B
 A A A A A

```

Here `A` can be one of `|` and (space), and `B` can be one of `-` and (space). The rows and columns alternate between these two values. The binary vectors indicate, whether to start in the "on" (`|`/`-`) or "off" () position for each row or column.

*You may be interested in a recent Numberphile video on that topic.*

## Rules

* \\$n,m \geqslant 1\\$
* There are \\$ n \times m \\$ `+`s.
* You may take input in any consistent order (rows first or columns first) and following any direction (right-to-left and top-to-bottom or reversed or mixed).
* Output in any reasonable format, including one of: single string with newlines, list of lines, matrix of characters. Output as char codes is allowed only if your language doesn't support strings natively.
* Trailing whitespace is optional.

## Test cases

Input: `0 1 0 1`, `0 1 1`
Working out:

```
 0 1 0 1
0+?+?+?+?
 ? ? ? ?
1+?+?+?+?
 ? ? ? ?
1+?+?+?+?
 ? ? ? ?

```

Output:

```
   |   |
 +-+ +-+
 |   |
-+ +-+ +-
   |   |
-+ +-+ +-
 |   |

```

Input: `0`, `0`
Output:

```

 +-
 |

```

Input: `1`, `1`
Output:

```
 |
-+

```

Input: `1 0 1 0 1`, `1 0 1 0 1 0 1`
Output:

```
 |   |   |
-+ +-+ +-+
   |   |
 +-+ +-+ +-
 |   |   |
-+ +-+ +-+
   |   |
 +-+ +-+ +-
 |   |   |
-+ +-+ +-+
   |   |
 +-+ +-+ +-
 |   |   |
-+ +-+ +-+
   |   |

```

# Answer
> 6 votes
# Charcoal, 29 bytes

```
Ｆ²«Ｐ⭆§θ¬ι⪫¶¶⪫Ｅ⊕Ｌ§θι§ -⁺μκ+‖Ｔ↙

```

Try it online! Link is to verbose version of code. Takes input as an array of two binary vectors. Explanation:

```
Ｆ²«

```

Loop over rows and then columns.

```
Ｐ⭆§θ¬ι⪫¶¶⪫Ｅ⊕Ｌ§θι§ -⁺μκ+

```

For each row, build up the line of `-`s or spaces and `+`s according to the initial value from the binary vector. Double-space the rows out and output the whole string without moving the cursor.

```
‖Ｔ↙

```

Reflect the entire diagram around its main diagonal. On the first pass this moves the rows to the columns, allowing the columns to be printed where the rows were, while on the second pass the rows and columns are restored to their correct placement. Additionally, the `-`s and `|`s are swapped as part of the reflection.

# Answer
> 6 votes
# Jelly, 27 bytes

```
JŻḂ+ż⁸Fð"2,4^'/ị“+ - |  +”Y

```

Try it online!

Takes input like `[[0,1,0,1],[0,1,1]]`.

```
Helper function: left input is a bit array, right input is a number

JŻḂ       Alternate [0,1,0,1,…] one longer than the bit array
   +      Add n
    ż⁸F   Interleave with the array:  [n, a0, n+1, a1, n, a2, n+1]

Main function: input is two bit arrays [A, B]

ð"2,4                  [helper(A, 2), helper(B, 4)]
     ^'/               Make a XOR table
        ị“+ - |  +”Y   Index into “+ - |  +” and join by newlines.

```

For example, for the input `[[0,1,0,1],[0,1,1]]` this computes

```
 ^ │ 2 **0** 3 **1** 2 **0** 3 **1** 2
 ──┼───────────────────
 4 │ 6 4 7 5 6 4 7 5 6
 **0** │ 2 0 3 1 2 0 3 1 2
 5 │ 7 5 6 4 7 5 6 4 7
 **1** │ 3 1 2 0 3 1 2 0 3
 4 │ 6 4 7 5 6 4 7 5 6
 **1** │ 3 1 2 0 3 1 2 0 3
 5 │ 7 5 6 4 7 5 6 4 7

```

And then translates {0, 1} → `+`, 3 → `-`, 5 → `|`, and everything else to spaces.

# Answer
> 4 votes
# APL (Dyalog Unicode), <sup>~~69~~ ~~66~~ ~~62~~ ~~58~~</sup> 54 bytes

Function that takes two binary vectors as left and right argument. Assumes index origin 0.

```
{' -|+'[↑,⍉↑(,/¯2↑¨2×↑≠\(⊂⍺),!⍵)({∊⍺3⍵}/⍉↑≠\(⊂⍵),!⍺)]}

```

Try it online!

**Commented** (outdated):

```
{∊⍺'+'⍵}/' -'[⍉↑≠\(⊂⍵),!⍺] ⍝ Generate the B-rows
                       !⍺  ⍝ A list of n 1's (factorial of 0 and 1 is 1)
                  (⊂⍵),    ⍝ prepend the right (second) input vector
              ⍉↑≠\         ⍝ the tranpose of ≠ (XOR) scan
                           ⍝   this gives a binary mask of where to place dashes
         ' -'[           ] ⍝ index with the mask into the string ' -' to get a character matrix
{∊⍺'+'⍵}/                  ⍝ for each row, insert plus's

    ,/¯2↑¨' |'[↑≠\(⊂⍺),!⍵] ⍝ Generate the A-rows
          ' |'[↑≠\(⊂⍺),!⍵] ⍝ Same as above, but with inputs swapped and not transposed
      ¯2↑¨                 ⍝ Prepend a space to each character in the matrix (this results in a nested matrix)
    ,/                     ⍝ Join each row into a single string

↑,⍉↑                       ⍝ Interleave the two lists of rows to get a single character matrix

```

# Answer
> 4 votes
# Python 3.8 (pre-release), 121 116 bytes

```
lambda h,v,i=0:[print(((i:=~i)<2>l)*((l*"-+"+len(h)*" +-+")[:len(h)*2+1]+"\n"),*["| "[k^i]for k in h])for l in[2]+v]

```

Try it online!

Uses Pythons space separated output of `print` for the vertical lines.

Thanks for @pxeger for noticing that the flag toggle (`i:=~i`) and first line check (`2>l`) can be combined, by using a numerical flag.

By using 0 and -1 instead of 0 and 1 for the flag, a further byte can be saved.

# Answer
> 4 votes
# JavaScript (ES6), 95 bytes

Expects `(a)(b)`. Returns a matrix of characters.

```
a=>b=>[...b+11].map((_,y)=>[...a+11].map((_,x)=>' |-+'[x*y%2*3|a[~-x/2]+y/2&1|b[~-y/2]*2+x&2]))

```

Try it online!

### Cell types

```
   01234    Cell types:
 0 .|.|.      crossing (+)        : x odd and y odd ⇔ x * y % 2 == 1
 1 -+-+-      vertical link (|)   : x odd and y even
 2 .|.|.      horizontal link (-) : x even and y odd
 3 -+-+-      empty (.)           : x even and y even
 4 .|.|.

```

### Commented

```
a =>                  // a[] = horizontal vector
b =>                  // b[] = vertical vector
[...b + 11]           // coerce b[] to a string and append 2 more characters,
                      // which gives b.length * 2 + 1 characters
                      // e.g. [0,1,0] -> "0,1,011"
.map((_, y) =>        // for each entry at position y:
  [...a + 11]         //   do the same thing with a[]
  .map((_, x) =>      //   for each entry at position x:
    ' |-+'[           //     character lookup:
      x * y % 2 * 3 | //       force a '+' if both x and y are odd
      a[~-x / 2]      //       attempt to get a[(x - 1) / 2],
                      //       which is undefined if x is even
      + y / 2         //       add y / 2 (resulting in NaN if x is even)
      & 1 |           //       bitwise AND with 1 to get either " " or "|"
      b[~-y / 2] * 2  //       attempt to get b[(y - 1) / 2] * 2,
                      //       which is NaN if y is even
      + x             //       add x (still NaN if y is even)
      & 2             //       bitwise AND with 2 to get either " " or "-"
    ]                 //     end of character lookup
  )                   //   end of inner map()
)                     // end of outer map()

```

# Answer
> 3 votes
# 05AB1E, ~~37~~ 33 bytes

```
"+ - |  +"Iε1ÝyĆ∍N>o+s.ι}`sδ^<èJ»

```

-4 bytes by porting *@Lynn*'s Jelly answer.

Try it online or verify all test cases.

**Original 37 byter:**

```
v„|-NèðìyD_øIN_èg>δ∍N_iø}è„ +Nèý}.ι.c

```

Input as pair \\$\[n,m\]\\$, where both \\$n\\$ and \\$m\\$ are lists of 0s/1s.

Try it online or verify all test cases.

Taking the input in the order \\$\[m,n\]\\$ instead would result in the same byte-count:

```
v„-|NèðìyD_øIN_èg>δ∍Niø}è„+ Nèý}s.ι.c

```

Try it online or verify all test cases.

**Explanation:**

```
v                    # Loop `y` over the (implicit) input-pair:
 „|-                 #  Push String "|-"
    Nè               #  Use the 0-based loop-index to index into it
      ðì             #  Prepend a space
        y            #  Push the current input-list
         D_          #  Duplicate it, and invert each 0↔1
           ø         #  Zip the two lists, creating pairs
                     #  (all 0s are now [0,1] and all 1s are now [1,0])
            I        #  Push the input-pair again
             N_      #  Push the inverted loop-index
               è     #  Use it to index into the input-pair
                g    #  Pop and push its length
                 >   #  Increase this length by 1
                  δ  #  Loop over the list of [0,1] and [1,0] pairs:
                   ∍ #   Extend each pair to the length+1 of the opposite list
 N_i }               #  If this is the second input-pair:
    ø                #   Zip/transpose it; swapping rows/columns
      è              #  Index each value into the " |" or " -" we created earlier
       „ +           #  Push string " +"
          Nè         #  Index the loop-index into it
            ý        #  Join the list of characters with this as delimiter
}.ι                  # After the loop, interleave both lists of lines on the stack
   .c                # Join this list by newlines, and center each line
                     # (after which the result is output implicitly)

```

# Answer
> 2 votes
# , ~~184~~ ~~164~~ ~~162~~ ~~136~~ ~~134~~ 129 bytes

*Edit: -28 bytes (!) thanks to pajonk, and -2 bytes thanks to Giuseppe*

```
function(n,m,`?`=length){x=array(" ",c(?n,?m)*2+1)
x[2*1:?n,p<-!0:1][c(n,!n)]="-";x=t(x)
x[2*1:?m,p][c(m,!m)]="|"
x[!p,!p]="+"
x}

```

Try it online!

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


title: AoCG2021 Day 16: Interpret Duet

text:
# Question
Title: AoCG2021 Day 16: Interpret Duet
Related to AoC2017 Day 18, Part 2. (Anyone want to add Duet to esolangs?)

---

**Duet** is an assembly-like language that involves two processes running the same program simultaneously. Each process of Duet operates with 26 registers named `a` to `z`, all initialized to zero, except for the register `p` which contains the process ID (0 or 1).

Individual instructions in Duet are as follows. `X` is a register, and `Y` and `Z` can be a register or a constant. A constant is an integer which can be positive, negative, or zero, and is written in base 10 with optional `-` sign.

* `set X Y` sets register X to the value of Y.
* `add X Y` increases register X by the value of Y.
* `mul X Y` sets register X to the result of multiplying the value contained in register X by the value of Y.
* `mod X Y` sets register X to the remainder of dividing the value contained in register X by the value of Y (that is, it sets X to the result of X modulo Y).
    + X may be assumed to be strictly non-negative and Y may be assumed to be strictly positive in this challenge.
* `jgz Y Z` jumps with an offset of the value of Z, but only if the value of Y is greater than zero. (An offset of 2 skips the next instruction, an offset of -1 jumps to the previous instruction, and so on.)
* `snd Y` sends the value of Y to the other program. These values wait in a queue until that program is ready to receive them. Each program has its own message queue, so a program can never receive a message it sent.
* `rcv X` receives the next value and stores it in register X. If no values are in the queue, the program waits for a value to be sent to it. Programs do not continue to the next instruction until they have received a value. Values are received in the order they are sent.

After each `jgz` instruction, the program continues with the instruction to which the jump jumped. After any other instruction, the program continues with the next instruction. Continuing (or jumping) off either end of the program in either process terminates the entire program (i.e. both processes), as well as being stuck in a deadlock (both programs waiting at a `rcv` instruction).

Duet does not have any I/O facility. The only observable behavior of a program is that either it terminates, or it doesn't.

Both of these programs below should terminate by a deadlock:

```
snd 1
snd 2
snd p
rcv a
rcv b
rcv c
rcv d

```

```
set i 31
set a 1
mul p 17
jgz p p
mul a 2
add i -1
jgz i -2
add a -1
set i 127
set p 680
mul p 8505
mod p a
mul p 129749
add p 12345
mod p a
set b p
mod b 10000
snd b
add i -1
jgz i -9
jgz a 3
rcv b
jgz b -1
set f 0
set i 126
rcv a
rcv b
set p a
mul p -1
add p b
jgz p 4
snd a
set a b
jgz 1 3
snd b
set f 1
add i -1
jgz i -11
snd a
jgz f -16
jgz a -19

```

Write an interpreter for Duet, which takes a valid source code as input (list of lines is OK), and runs it until the program terminates. Your interpreter should terminate if and only if the input Duet program terminates.

Standard rules apply. The shortest code in bytes wins.

Some examples that halt because one process exits early:

* Process 0 waits but Process 1 exits early by jumping over the end

```
mul p 10
jgz p p
rcv x

```
* Process 1 loops indefinitely but Process 0 halts by jumping before the start

```
jgz p 0
jgz 1 -2

```
* Process 0 loops indefinitely but Process 1 runs through the program and exits

```
add p 1
mod p 2
jgz p 0

```

Some examples that never halt:

* Both processes run an infinite loop that passes some values around

```
set a 10
snd 1
snd 2
rcv x
rcv y
jgz a -4

```
* Both processes run a tight loop

```
jgz 1 0

```

# Answer
# Pari/GP, 459 bytes

```
p->a=matrix(2,26);a[2,16]=1;c=[l=List(),l];n=[1,1];while(![m<=0||m>#p|m<-n]&&sum(k=1,2,#c[k]||Vec(p[n[k]])[1]!="r"),for(k=1,2,(g(u,v)=if(0<t=s[u]-96,a[k,t],eval(Strchr(s[u..v]))));s=Vecsmall(p[n[k]]);i=s[2]-96;v=if(i-14&&i-7,x=s[5]-96;7,5);i-7||while(s[v]-32,v++)||z=g(5,v++-2);if(i-3,y=g(v,#s);i-5||a[k,x]=y;i-4||a[k,x]+=y;i-21||a[k,x]*=y;i-15||a[k,x]%=y;i-7||(z>0&&n[k]+=y-1);i-14||listput(c[3-k],y),if(#c[k],a[k,x]=c[k][1];listpop(c[k],1),n[k]--));n[k]++))

```

Try it online!

Takes a list of lines as input.
> 4 votes

# Answer
# JavaScript, 249 bytes

```
P=>{for(Q=[...P],P.M=[],Q.M=[],I=J=Q.p=1;E=I+J&&P[P.$??=0];[P,Q]=[Q,P])with(P)I=J,J=1,([[,O],X,Y]=E.split` `).map(C=>P[C]??=0),eval({g:X+`>0&&($+=${Y}-1)`,n:`Q.M.push(${X})`,c:`M+""?${X}=M.shift():J=0`}[O]||X+{e:'=',d:'+=',u:'*=',o:'%='}[O]+Y),$+=J}

```

```
F=P=>{
  for(
      // Initial
      Q=[...P],   // P is process 0; Q is process 1
                  // We use the array for instructions,
                  // use P.a ~ P.z for registers
                  // use P._ for message queue received
                  // use P.$ for index of next instruction to execute
      P._=[],     // initial message queue
      Q._=[],
      I=J=        // is last instruction successfully executed? (not waiting message)
      Q.p=1;      // initial Process ID for Process Q
      // While not dead lock and not out of range
      E=I+J&&     // terminate if all process waiting message
      P[P.$??=0]; // next instruction to execute
      // Swap process schedule after each instruction execution
      [P,Q]=[Q,P]
  )with(P)        // use variables in process P
    I=J,J=1,      // initial success flags
    ([
      [,O],       // The second character is different for each instruction
      X, Y        // two operand
    ]=E.split` `) // parse instruction, split it by space
      .map(C=>P[C]??=0), // Initial any value used to 0
    eval({        // execute the instruction
      g:X+`>0&&($+=${Y}-1)`,              // jgz
      n:`Q._.push(${X})`,                 // snd
      c:`_+""?${X}=_.shift():J=0`         // rcv
    }[O]||
      X+{e:'=',d:'+=',u:'*=',o:'%='}[O]+Y // other math op
    ),
    $+=J          // move to next instruction if success
}

```

```
F=P=>{for(Q=[...P],P.M=[],Q.M=[],I=J=Q.p=1;E=I+J&&P[P.$??=0];[P,Q]=[Q,P])with(P)I=J,J=1,([[,O],X,Y]=E.split` `).map(C=>P[C]??=0),eval({g:X+`>0&&($+=${Y}-1)`,n:`Q.M.push(${X})`,c:`M+""?${X}=M.shift():J=0`}[O]||X+{e:'=',d:'+=',u:'*=',o:'%='}[O]+Y),$+=J}
```

```
<form onsubmit="F(T.value.trim().split(/\s*[\n;]\s*/));return false;">
<textarea id=T></textarea>
<br>
<button id=R>RUN</button>
</form>
```

-1 byte by Neil
> 4 votes

# Answer
# Rust, 576 bytes

```
|c:&[&str]|{let c:Vec<Vec<_>>=c.iter().map(|s|s.split(' ').collect()).collect();let(r,n,mut p)=(|r:&str|r.as_bytes()[0]as usize,|n:&str,f|n.parse::<i64>().unwrap_or(f),(vec![0;123],vec![0;123]));p.0[112]=1;while p.0[1]+p.1[1]<2{p=(p.1,p.0);let(c,m)=(c.get(p.0[0]as usize)?,&mut p.0);let x=r(c[1]);if c[0]=="snd"{p.1.push(n(c[1],m[x]));}else if c[0]=="rcv"{if m.len()>123{m[x]=m.remove(123);m[1]=0}else{m[1]=1;m[0]-=1}}else{let y=n(c[2],m[r(c[2])]);match c[0]{"set"=>m[x]=y,"add"=>m[x]+=y,"mul"=>m[x]*=y,"mod"=>m[x]%=y,"jgz" if n(c[1],m[x])>0=>m[0]+=y-1,_=>()}}m[0]+=1}Some(1)}

```

Try it online!

Fun!

Ungolfed:

```
|cmds: &[&str]| {
    let cmds: Vec<Vec<_>> = cmds.iter().map(|s| s.split(' ').collect()).collect(); // split commands
    let (register, number_or, mut process) = (
        |r: &str| r.as_bytes()[0] as usize,
        |n: &str, f| n.parse::<i64>().unwrap_or(f),
        (vec![0; 123], vec![0; 123]), // process state:
                                      // 0 - program counter
                                      // 1 - rcv signal
                                      // b'a'..=b'z' - registers
                                      // b'z'+1.. - rcv queue
    );
    process.0[112] = 1; // b'p' == 112
    while process.0[1] + process.1[1] < 2 { // while not deadlocked
        process = (process.1, process.0); // swap processes
        let (cmd, memory) = (cmds.get(process.0[0] as usize)?, &mut process.0);
        let x = register(cmd[1]);
        if cmd[0] == "snd" {
            process.1.push(number_or(cmd[1], memory[x]));
        } else if cmd[0] == "rcv" {
            if memory.len() > 123 {
                memory[x] = memory.remove(123);
                memory[1] = 0
            } else {
                memory[1] = 1;
                memory[0] -= 1 // don't advance program
            }
        } else {
            let y = number_or(cmd[2], memory[register(cmd[2])]);
            match cmd[0] {
                "set" => memory[x] = y,
                "add" => memory[x] += y,
                "mul" => memory[x] *= y,
                "mod" => memory[x] %= y,
                "jgz" if number_or(cmd[1], memory[x]) > 0 => memory[0] += y - 1,
                _ => (),
            }
        }
        memory[0] += 1
    }
    Some(1)
};

```
> 4 votes

# Answer
# Python3, 686 bytes:

```
import operator as o
u=lambda g,n:n.get(g,0)if g.isalpha()else int(g)
def e(s,n,i,q,w,r):
 k=i['i']
 if q and r:n[r.pop()]=q.pop();i['i']+=(not r);return
 if (v:=s[k][0])=='set':n[s[k][1]]=u((g:=s[k][2]),n);i['i']+=1
 elif v=='snd':w.append(u(s[k][1],n));i['i']+=1
 elif v=='rcv':
  if q:n[s[k][1]]=q.pop();i['i']+=1
  else:r.append(s[k][1])
 elif v=='jgz':i['i']=i['i']+(1 if not u(s[k][1],n) else u(s[k][2],n))
 else:n[s[k][1]]=getattr(o,s[k][0])(n[s[k][1]],u(s[k][2],n));i['i']+=1
def f(p):
 p=[i.split()for i in p.split('\n')]
 n,m,i,t,q,w,r,s={'p':0},{'p':1},{'i':0},{'i':0},[],[],[],[]
 while 0<=i['i']<len(p)and 0<=t['i']<len(p)and not any([r,s]):
  e(p,n,i,q,w,r);e(p,m,t,w,q,s)

```

Try it online!
> 3 votes

# Answer
# Ruby, ~~537 ...~~ 312 bytes

```
->s{g=[{},{p:1}];*q=[],[];*a=0,0;r=s.lines;(2.times{|x|l,m,n=r[a[x]].split
h="g[x][:"
eval [[k=[z=h+m+?],y=?(+z+"||0)"]*?=,t=n&&n>?9?"(#{h+n}]||0)":n]*?%,"q[x][0]?(#{z}=q[x].shift):a[x]-=1",k+?++t,z+?=+t,"q[1-x]<<#{d=m&&m>?9?y:m}","#{d}>0&&a[x]+=#{t}-1",k+?*+t][l[1].ord%37%8]
a[x]+=1}
)while a.min>=0&&r[a.max]}

```

Try it online!

A little more golfy. Still very copy-pasty.
> 3 votes

# Answer
# Charcoal, 224 bytes

```
ＷＳ⊞υ⪪ι ≔Ｅ²⊞ＯＥ²⁸∧ι⁼¹⁵λ¹θＷ∧⊙θ§κ²⁸⬤θ⁼§κ²⁶﹪§κ²⁶Ｌυ«≔§θ⁰η≔⮌θθ≔§υ§η²⁶ζ≔⌕β§ζ¹ε≔⌕β§ζ±¹δ≔⎇⊕δ§ηδＩ§ζ±¹δ≡§§ζ⁰¦¹e§≔ηεδd§≔ηε⁺§ηεδu§≔ηε×§ηεδo§≔ηε﹪§ηεδgＦ‹⁰⎇⊕ε§ηεＩ§ζ¹§≔η²⁶⁺§η²⁶⊖δc«§≔η²⁸‹§η²⁷⁻Ｌη²⁹§≔ηε§η⁺²⁹§η²⁷§≔η²⁷⁺§η²⁷§η²⁸»⊞§θ⁰δ§≔η²⁶⁺§η²⁶§η²⁸

```

Try it online! Link is to verbose version of code. Takes input as a list of newline-terminated instructions. Explanation:

```
ＷＳ⊞υ⪪ι

```

Read the instructions, splitting on spaces.

```
≔Ｅ²⊞ＯＥ²⁸∧ι⁼¹⁵λ¹θ

```

Create two threads of execution. Each thread is represented by an array of values. The first 26 represent the variables `a-z`, then comes the program counter, the receive counter, and the running flag, which is normally `1` but gets reset to `0` if a `rcv` instruction is executed when the receive counter exceeds the number of items in the send list. Any further items are the send list. Items are not removed from the send list, instead the receive counter is used to determine which the next item is.

```
Ｗ∧⊙θ§κ²⁸⬤θ⁼§κ²⁶﹪§κ²⁶Ｌυ«

```

Repeat until either both running flags are zero or at least one program counter is out of range.

```
≔§θ⁰η

```

Get the current thread.

```
≔⮌θθ

```

Schedule the other thread to become the current thread.

```
≔§υ§η²⁶ζ

```

Get the current instruction.

```
≔⌕β§ζ¹ε

```

Get the index of the first argument, assuming it's a variable.

```
≔⌕β§ζ±¹δ

```

Get the index of the last argument, assuming it's a variable.

```
≔⎇⊕δ§ηδＩ§ζ±¹δ

```

Evaluate the last argument as a variable or a constant as appropriate.

```
≡§§ζ⁰¦¹

```

Switch over the second character of the instruction, as it's unique across all instructions.

```
e§≔ηεδ

```

For `set` simply assign the evaluated last argument to the index given by the first argument.

```
d§≔ηε⁺§ηεδ

```

Add the last argument to the first argument.

```
u§≔ηε×§ηεδ

```

Multiply the first argument by the last argument.

```
o§≔ηε﹪§ηεδ

```

Modulo the first argument by the last argument.

```
gＦ‹⁰⎇⊕ε§ηεＩ§ζ¹§≔η²⁶⁺§η²⁶⊖δ

```

For `jgz` evaluate the first argument as a variable or constant and if it's positive then update the program counter by the given offset (but taking the autoincrement into account).

If this is `rcv` then...

```
§≔η²⁸‹§η²⁷⁻Ｌη²⁹

```

Calculate whether this thread is stalled.

```
§≔ηε§η⁺²⁹§η²⁷

```

Try to get the value out of the send list anyway. (If there aren't enough items, Charcoal will fetch a meaningless value, but it will be overwritten by the correct value once it's been added to the send list.)

```
§≔η²⁷⁺§η²⁷§η²⁸

```

Increment the receive pointer if there was a waiting item in the send list.

```
»⊞§θ⁰δ

```

Otherwise this is `snd` so push the last argument to the (now other thread's) send list.

```
§≔η²⁶⁺§η²⁶§η²⁸

```

Increment the program counter, unless the thread is stalled on a receive.
> 3 votes

# Answer
# TypeScript Types, 1203 bytes

```
//@ts-ignore
type a<T,A=0,N=[]>=T extends`${N["length"]}`?N:a<T,A,[...N,A]>;type b<T,P=0,N=[1,0][P]>=T extends[N,...infer T]?T:[...T,P];type c<T,U,P=0>=T extends[infer X,...infer T]?c<T,b<U,[P,[1,0][P]][X]>>:U;type d<T,U,N=[]>=T extends[infer X,...infer T]?d<T,c<U,N,X>>:N;type e<T,U>=T extends[...{[K in keyof U]:{}},...infer T]?e<T,U>:T;type f<T>=T extends`${number}`?T extends`-${infer U}`?a<U,1>:a<T>:T;type g<M,R,V>=Omit<M,R>&Record<R,V>;type h<M,A>=A extends keyof M?M[A]:A extends{}[]?A:[];type i<S,P=[]>=S extends`${infer I}\n${infer R}`?I extends`${infer O} ${infer X}${` ${infer Y}`|""}`?i<R,[...P,[O,f<Exclude<X,`${string} ${string}`>>,f<Y>]]>:0:P;type j<k,l={p:[]},m=[],n=[],o={p:[0]},p=[],q=[],r=0>=[m,`${m["length"]}`]extends[0[],keyof k]?k[m["length"]]extends[infer s,infer X,infer Y]?[h<l,X>,h<l,Y>]extends[infer t,infer u]?{set:j<k,g<l,X,u>,b<m>,n,o,p,q>,add:j<k,g<l,X,c<t,u>>,b<m>,n,o,p,q>,mul:j<k,g<l,X,d<t,u>>,b<m>,n,o,p,q>,mod:j<k,g<l,X,e<t,u>>,b<m>,n,o,p,q>,jgz:t extends 1[]?j<k,l,b<m>,n,o,p,q>:j<k,o,p,q,l,c<m,u>,n>,snd:j<k,l,b<m>,n,o,p,[...q,h<l,X>]>,rcv:n extends[infer v,...infer w]?j<k,g<l,X,v>,b<m>,w,o,p,q>:r extends 1?0:j<k,o,p,q,l,m,n,1>}[s]:0:0:0;type M<T>=j<i<`${T}
`>>

```

Try It Online!

## Ungolfed / Explanation

```
// Converts a stringified number to a tuple representation
type StrNumToTuple<T, A=0, N=[]> = T extends `${N["length"]}` ? N : StrNumToTuple<T, A, [...N, A]>

// Increment/decrement an integer stored as e.g. [0, 0] for 2, [1, 1, 1] for -3, and [] for 0
// Invoked as Inc<T> to increment, or Inc<T, 1> to decrement
type Inc<T, Pos = 0, Neg = [1, 0][Pos]> = T extends [Neg, ...infer T] ? T : [...T, Pos]

// Add/subtract two integers
// Invoked as Add<T, U> to add, or Add<T, U, 1> to subtract
type Add<T, U, P = 0> = T extends [infer X, ...infer T] ? Add<T, Inc<U, [P,[1,0][P]][X]>> : U

// Multiply two integers
type Mult<T, U, N = []> = T extends [infer X, ...infer T] ? Mult<T, Add<U, N, X>> : N

// Modulo two integers
type Mod<T, U> = T extends [...{ [K in keyof U]: {} }, ...infer T] ? Mod<T, U> : T

// Parse an argument (like "a" or "-3") into either a register ("a") or an integer ([1, 1, 1])
type ParseArg<T> = T extends `${number}` ? T extends `-${infer U}` ? StrNumToTuple<U,1> : StrNumToTuple<T> : T

// Set a register in memory
type SetArg<Mem, Reg, Val> = Omit<Mem, Reg> & Record<Reg, Val>

// Get the value of an argument
type GetArg<Mem, Arg> = Arg extends keyof Mem ? Mem[Arg] : Arg extends {}[] ? Arg : []

type ParseProgram<Str, Prog = []> =
  // Get the first line of Str
  Str extends `${infer Inst}\n${infer Rest}`
    // Garbage parsing logic
    ? Inst extends `${infer Op} ${infer X}${` ${infer Y}`|""}`
      ? ParseProgram<Rest, [...Prog, [Op, ParseArg<Exclude<X,`${string} ${string}`>>, ParseArg<Y>]]>
      : 0
    // Str is empty
    : Prog

type Run<
  Prog,
  // Active process
  MemA={p:[]},
  IpA=[],
  QueueA=[],
  MemB={p:[0]},
  // Inactive process
  IpB=[],
  QueueB=[],
  // Set to 1 when rcv is called with an empty queue; used to detect deadlock
  JustSwapped=0
> =
  // If IpA > 0 and < Prog.length
  [IpA, `${IpA["length"]}`] extends [0[], keyof Prog]
    // Store the parts of the current instruction in Op, X, and Y
    ? Prog[IpA["length"]] extends [infer Op, infer X, infer Y]
      // Get the values at X and Y and store them in XV and YV, respectively
      ? [GetArg<MemA, X>, GetArg<MemA, Y>] extends [infer XV, infer YV]
        // Switch on Op
        ? {
          set: Run<Prog, SetArg<MemA, X, YV>, Inc<IpA>, QueueA, MemB, IpB, QueueB>
          add: Run<Prog, SetArg<MemA, X, Add<XV, YV>>, Inc<IpA>, QueueA, MemB, IpB, QueueB>
          mul: Run<Prog, SetArg<MemA, X, Mult<XV, YV>>, Inc<IpA>, QueueA, MemB, IpB, QueueB>
          mod: Run<Prog, SetArg<MemA, X, Mod<XV, YV>>, Inc<IpA>, QueueA, MemB, IpB, QueueB>
          jgz:
            // If XV <= 0
            XV extends 1[]
              ? Run<Prog, MemA, Inc<IpA>, QueueA, MemB, IpB, QueueB>
              // Swap to the other process (to protect against infinite loops on only one thread)
              : Run<Prog, MemB, IpB, QueueB, MemA, Add<IpA, YV>, QueueA>
          snd: Run<Prog, MemA, Inc<IpA>, QueueA, MemB, IpB, [...QueueB, GetArg<MemA, X>]>
          rcv:
            // Get the first value in QueueA
            QueueA extends [infer Val, ...infer NewQueue0]
              ? Run<Prog, SetArg<MemA, X, Val>, Inc<IpA>, NewQueue0, MemB, IpB, QueueB>
              // QueueA is empty
              : JustSwapped extends 1
                // Deadlock
                ? 0
                // Swap to the other process, enabling JustSwapped
                : Run<Prog, MemB, IpB, QueueB, MemA, IpA, QueueA, 1>
        }[Op]
        : 0 // unreachable
      : 0 // unreachable
    // Otherwise, halt
    : 0

```
> 3 votes

# Answer
# Wolfram Language (Mathematica), 373 bytes

```
(Clear@A;P=ToExpression@StringSplit@#;S=A/@{0,1};(#@_=0;#@p=#[[1]];#@i_?NumberQ:=i;#@C={};#@N=1)&/@S;While[0<#@N<=Length@P&/@And@@S&&(#@C!={}||P[[#@N,1]]=!=rcv&/@Or@@S),(P[[#@N]]/.{i_,x_,y_:0}:>Switch[Y=#@y;i,set,#@x=Y,add,#@x+=Y,mul,#@x*=Y,mod,#@x=#@x~Mod~Y,jgz,#@x>0&&(#@N+=Y-1),snd,(1-#&/@#)@C~AppendTo~#@x,_,If[#@C!={},{{#@x},#@C}=#@C~TakeDrop~1,#[N]--]];#[N]++)&/@S])&

```

Try it online!
> 2 votes

# Answer
# Java 10, ~~630~~ ~~627~~ 625 bytes

```
import java.util.*;L->{Stack<Long>m=new Stack(),q=new Stack();long r[][]=new long[2][26],V,P,t;++r[0][15];for(int c,f=1,g=1,d=1,i=0,j=0,o,v,p;f>-g&d>0;)for(c=2;c--*d>0;d=d>=0&d<L.length?1:0)try{f=g;V=P=g=1;var l=L[d=c<1?j:i];var x=l.split(" ");o=l.charAt(1);l=x[x.length-1];v=(v=l.charAt(0))>57?v-(int)(V=97):new Integer(l);V=V>1?r[c][v]:v;t=r[c][p=x.length>2?(p=x[1].charAt(0))>57?p-(int)(P=97):new Integer(x[1]):0];P=P>1?t:p;r[c][p]=o=='e'?V:o=='d'?t+V:o>116?t*V:o=='o'?t%V:t;l=L[o=='g'&P>0?c<1?j+=V-1:(i+=V-1):0];if(o=='n')(c<1?q:m).add(0,V);if(o<100)r[c][p]=(c<1?m:q).pop();l=L[c<1?j+=g:(i+=g)];}catch(Exception e){g=0;}}

```

-5 bytes thanks to *@ceilingcat*.

Input as a String-array.

Try it online.

**Explanation:**

```
import java.util.*;          // Import for 3x Stack
L->{                         // Method with String-array parameter and no return
  Stack<Long>m=new Stack(),  //  Message-queue of process 1
             q=new Stack();  //  Message-queue of process 0
  long r[][]=new long[2][26],//  Registers, starting at 26x 0
                             //  Index 0 is process 1, index 1 is process 0
       V,P,t;                //  Value `V`, Register-position `P`, temp `t`
  ++r[0][15];                //  Increase 'p' in process 1 by 1
  for(int c,                 //  Current process
      f=1,g=1,               //  Process flag-integers
      d=1,                   //  Bounds flag-integer
      i=0,                   //  Index-integer of process 0
      j=0,                   //  Index-integer of process 1
      o,v,p;                 //  Operation `o`, Value `v`, Register-position `p`
                             //  (we use `V`/`P` as actual values, and `v`/`p`
                             //  as indices in case we need to modify data at
                             //  those positions)
      f>-g                   //  Loop as long as one process-flag is still 1,
      &d>0;)                 //  and the indices are within bounds:
    for(c=2;c--              //   Inner loop `c` in the range (2,0],
        *d>0                 //   as long as the indices are within bounds:
        ;                    //     After every iteration:
         d=d>=0&d<L.length?  //      If `d` is within bounds:
            1                //       Set it as flag to 1
           :                 //      Else:
            0)               //       Set it as flag to 0
      try{f=g;               //    Save flag-value `g` in flag-`f`
        V=P=g=1;             //    Reset flag-`g`, `V`, and `P` to 1
        var l=L[d=c<1?j:i    //    Set `d` to the index of the current process
                 ];          //    Get the current String-line
        var x=l.split(" ");  //    Split this line on spaces
        o=l.charAt(1);       //    Set `o` to the second character of the line
        l=x[x.length-1];     //    Set `l` to the last value of the split line,
                             //    which is either the third if there are three,
                             //    or the second if there are two
        v=(v=l.charAt(0))>57?//    If this is a letter:
           v-(int)(V=97)     //     Convert it to an index,
                             //     and set `V` to something larger than 1
          :                  //    Else (it's a number instead):
           new Integer(l);   //     Convert it from String to integer
        V=V>1?               //    If `V` is now larger than 1:
           r[c]              //     Get the values of the current process
               [v]           //     and set `V` to the `v`'th value
          :                  //    Else:
           v;                //     Set `V` to `v`
        t=r[c]               //    Get the values of the current process
          [p=                //    and set `t` to the `p`'th value,
                             //    where `p` is:
             x.length>2?     //     If the line has three parts:
              (p=x[1].charAt(0))>57?
                             //      If the second part is a letter:
               p-(int)(P=97) //       Convert it an index,
                             //       and set `P` to something larger than 1
              :              //      Else:
               new Integer(x[1])
                             //       Convert it from String to integer
             :               //     Else:
              0;             //      Simply set it to 0
        P=P>1?               //    If `P` is now larger than 1:
           t                 //     Set `P` to this `t`
          :                  //    Else:
           p;                //     Set `P` to `p`
        r[c][p]=             //    Set the `p`'th value to:
                o=='e'?      //     If the line is a 'set':
                 V           //      Simply set it to `V`
                :o=='d'?     //     Else-if the line is an 'add':
                 t+V         //      Set it to `t` plus `V`
                :o>116?      //     Else-if the line is a 'mul':
                 t*V         //      Set it to `t` multiplied by `V`
                :o=='o'?     //     Else-if the line is a 'mod':
                 t%V         //      Set it to `t` modulo-`V`
                :            //     Else:
                 t;          //      Keep its same value by setting to `t`
        l=L[o=='g'           //    If the line is 'jgz': †
            &P>0?            //     If `P` is larger than 0:
             c<1?            //      If it's process 1:
              j+=V-1         //       Increase index `j` by `V` minus 1
             :               //      Else (it's process 0):
              (i+=V-1):0];   //       Increase index `i` by `V` minus 1
        if(o=='n')           //    If the line is 'snd':
          (c<1?              //     If it's process 1:
            q                //      Use Message-queue `q`
           :                 //     Else (it's process 0):
            m                //      Use Message-queue `m` instead
          ).add(0,V);        //     And prepend `V` to this Message-queue
        if(o<100)            //    If the line is 'rcv':
          r[c][p]=           //     Set the `p`'th value to:
           (c<1?             //      If it's process 1:
             m               //       Use Message-queue `m`
            :                //      Else (it's process 0):
             q               //       Use Message-queue `q`
           ).pop();          //      And pop and get its top value
        l=L[c<1?             //    If it's process 1: †
             j+=g            //     Increase index `j` by `g`
            :                //    Else (it's process 0):
             (i+=g)];        //     Increase index `i` by `g`
      }catch(Exception e){   //   If an error occurs (which is either an
                             //   ArrayIndexOutOfBoundsException if an `i`/`j`/
                             //   `p`/`v` we've used for indexing is out of
                             //   bounds, or an EmptyStackException if we tried
                             //   `pop()` on an empty Message-queue)
        g=0;}}               //     Set flag `g` to 0

```

*†:* `l=L[o=='g'&P>0?c<1?j+=V-1:(i+=V-1):0];` and `l=L[c<1?j+=g:(i+=g)];` may seem like an odd way to increase `j`/`i` based on the if-condition, since why do we set it to `l` and get it from `L`? But this is 3 bytes shorter than the traditional way: `if(o=='g'&P>0)if(c<1)j+=V-1;else i+=V-1;` and `if(c<1)j+=g;else i+=g;`
> 1 votes

---
Tags: code-golf, interpreter, assembly, concurrency
---


title: AoCG2021 Day 17: Langton's Hexa-Virus

text:
# Question
Title: AoCG2021 Day 17: Langton's Hexa-Virus
The story continues from AoC2017 Day 22, Part 2.

---

The damn virus that was infecting a grid computing cluster now has jumped to a *hexagonal* computing cluster! In this cluster, the computers are connected in the honeycomb-like shape, and each computer has three neighbors.

```
 ..  ..  ..
.  ..  ..  .
 ..  ..  ..
.  ..  ..  .
 ..  .x  ..
.  ..  ..  .
 ..  ..  ..
.  ..  ..  .
 ..  ..  ..

```

Initially, the cluster is completely clean, and the virus is at `x`, facing east. At each tick, the virus moves in the following manner:

* If the current computer is clean, infect it, turn left (60 degrees), and move forward once (move to the neighboring computer in that direction).
* Otherwise (the current computer is infected), clean it, turn right, and move forward once.

Some initial iterations look like this (generated using this program; `.` is clean, `*` is infected, `x` is the virus at a clean computer, and `X` is the virus at an infected one):

```
 ..  ..  ..
.  ..  ..  .
 ..  ..  ..
.  ..  ..  .
 ..  .x  ..
.  ..  ..  .
 ..  ..  ..
.  ..  ..  .
 ..  ..  ..

 ..  ..  ..
.  ..  ..  .
 ..  ..  ..
.  ..  x.  .
 ..  .*  ..
.  ..  ..  .
 ..  ..  ..
.  ..  ..  .
 ..  ..  ..

 ..  ..  ..
.  ..  ..  .
 ..  .x  ..
.  ..  *.  .
 ..  .*  ..
.  ..  ..  .
 ..  ..  ..
.  ..  ..  .
 ..  ..  ..

 ..  ..  ..
.  ..  ..  .
 ..  x*  ..
.  ..  *.  .
 ..  .*  ..
.  ..  ..  .
 ..  ..  ..
.  ..  ..  .
 ..  ..  ..

 ..  ..  ..
.  ..  ..  .
 ..  **  ..
.  .x  *.  .
 ..  .*  ..
.  ..  ..  .
 ..  ..  ..
.  ..  ..  .
 ..  ..  ..

 ..  ..  ..
.  ..  ..  .
 ..  **  ..
.  .*  *.  .
 ..  x*  ..
.  ..  ..  .
 ..  ..  ..
.  ..  ..  .
 ..  ..  ..

 ..  ..  ..
.  ..  ..  .
 ..  **  ..
.  .*  *.  .
 ..  *X  ..
.  ..  ..  .
 ..  ..  ..
.  ..  ..  .
 ..  ..  ..

 ..  ..  ..
.  ..  ..  .
 ..  **  ..
.  .*  *.  .
 ..  *.  ..
.  ..  x.  .
 ..  ..  ..
.  ..  ..  .
 ..  ..  ..

 ..  ..  ..
.  ..  ..  .
 ..  **  ..
.  .*  *.  .
 ..  *.  ..
.  ..  *x  .
 ..  ..  ..
.  ..  ..  .
 ..  ..  ..

 ..  ..  ..
.  ..  ..  .
 ..  **  ..
.  .*  *.  .
 ..  *.  x.
.  ..  **  .
 ..  ..  ..
.  ..  ..  .
 ..  ..  ..

 ..  ..  ..
.  ..  ..  .
 ..  **  ..
.  .*  *x  .
 ..  *.  *.
.  ..  **  .
 ..  ..  ..
.  ..  ..  .
 ..  ..  ..

 ..  ..  ..
.  ..  ..  .
 ..  **  ..
.  .*  X*  .
 ..  *.  *.
.  ..  **  .
 ..  ..  ..
.  ..  ..  .
 ..  ..  ..

 ..  ..  ..
.  ..  ..  .
 ..  *X  ..
.  .*  .*  .
 ..  *.  *.
.  ..  **  .
 ..  ..  ..
.  ..  ..  .
 ..  ..  ..

 ..  ..  ..
.  ..  x.  .
 ..  *.  ..
.  .*  .*  .
 ..  *.  *.
.  ..  **  .
 ..  ..  ..
.  ..  ..  .
 ..  ..  ..

 ..  .x  ..
.  ..  *.  .
 ..  *.  ..
.  .*  .*  .
 ..  *.  *.
.  ..  **  .
 ..  ..  ..
.  ..  ..  .
 ..  ..  ..

```

A better visualization can be seen here (pdf).

The number of infected computers at each iteration is A269757:

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

```

Your task is to output the sequence. Standard rules and I/O methods apply. (0-based and 1-based indexing allowed.) The shortest code in bytes wins.

# Answer
> 7 votes
# JavaScript (Node.js), 67 bytes

```
n=>(g=d=>n--?g(d+(g[t=d*2/3&3,[x+=--t%2,y+=--t%2]]^=2)-1):d)(x=y=0)

```

Try it online!

Remove all spaces from OP's example, we got:

```
......
......
......
......
...x..
......
......
......
......

......
......
......
...x..
...*..
......
......
......
......

......
......
...x..
...*..
...*..
......
......
......
......

......
......
..x*..
...*..
...*..
......
......
......
......

......
......
..**..
..x*..
...*..
......
......
......
......

......
......
..**..
..**..
..x*..
......
......
......
......

......
......
..**..
..**..
..*X..
......
......
......
......

......
......
..**..
..**..
..*...
...x..
......
......
......

......
......
..**..
..**..
..*...
...*x.
......
......
......

......
......
..**..
..**..
..*.x.
...**.
......
......
......

......
......
..**..
..**x.
..*.*.
...**.
......
......
......

......
......
..**..
..*X*.
..*.*.
...**.
......
......
......

......
......
..*X..
..*.*.
..*.*.
...**.
......
......
......

......
...x..
..*...
..*.*.
..*.*.
...**.
......
......
......

...x..
...*..
..*...
..*.*.
..*.*.
...**.
......
......
......

```

And you will find out the pattern: "Up, Up, Left, Down, Down, Right". That's how \\$ \lfloor \frac{2}{3}\cdot d \rfloor \\$ comes.

# Answer
> 6 votes
# Python 3, 79, 74 (@xnor), 61 bytes (@tsh)

```
x={0}
p=c=0
while[print(c)]:c=len(x);p+=1j**(c*2//3&3);x^={p}

```

Try it online!

#### Older versions

```
x={2}
p=c=0
while[print(c)]:x^={p};c+=x>{p}or-1;p+=1j**(c*2//3)*(1j-c%3%2)

```

Try it online!

```
x={*()}
p=c=0
while[print(c)]:x^={p};c+=(x>={p})or-1;p+=1j**(c*2//3)*(1j-c%3%2)

```

Try it online!

set `x` holds points infected, `p` is current position and `c` is current infection count. Note that current heading needn't be tracked because it can be inferred from `c%6`.

Coordinates are complex numbers. It would be desirable to base them on actual geometry but that has numerical problems. Which is why we use integer coordinates, i.e. an orthogonal grid with only one diagonal direction connected. Instead, we deform the grid by "squeezing out" the unreachable hexagon centres resulting in a square grid (with some connections missing), see picture: hat tip to @tsh for that.

# Answer
> 5 votes
# Charcoal, ~~34~~ 28 bytes

```
ＦＮ«⊞υＬＫＡＰ⎇℅ＫＫψ*Ｍ✳÷×⁴ＬＫＡ³»⎚Ｉυ

```

Try it online! Link is to verbose version of code. Outputs the first `n` members of the sequence. Edit: Saved 6 bytes using @loopywait's observation that the direction can be inferred from the infection count. Explanation:

```
ＦＮ«

```

Input `n` and loop that many times.

```
⊞υＬＫＡ

```

Save the number of infected computers at this step.

```
Ｐ⎇℅ＫＫψ*

```

Flip the current computer between uninfected and infected.

```
Ｍ✳÷×⁴ＬＫＡ³

```

Move in a hexagonal pattern on an octagonal grid, based on the number of infected computers. Note that the exact orientation of the grid is not significant, so north west and south east are actually represented by north and south.

```
»⎚Ｉυ

```

Output the gathered list of infected computer counts.

Here's a version that you can run locally to animate the progress of infection (the virus itself is not shown):

```
ＲＦφφ«Ｐ⎇℅ＫＫψ*Ｍ✳÷⊕×⁴ＬＫＡ³

```

Outputs the first 1,000 steps (the first `φ` is the animation speed, the second the number of steps). Replace the  with  if you want the program to run indefinitely. The extra  skews north and south back to north west and south east.

# Answer
> 2 votes
# Pari/GP, 78 bytes

```
n->for(i=!p=#a=Map(),n,iferr(mapdelete(a,p),e,mapput(a,p,1));p+=I^(#a*2\3));#a

```

Try it online!

A port of @tsh's JavaScript answer.

# Answer
> 2 votes
# Python script in Golly, 179 bytes

```
from golly import*
new("")
setrule("TriTurmite_120010")
setcell(0,0,2)
run(int(getstring("")))
a=[0,1,0,0,0,1,1,1]
show(str(sum(a[c%8]+a[c//8]for c in getcells(getrect())[2::3])))

```

Triangular Langton's ant is a built-in rule in Golly. But it simulates the triangular grid in a nontrivial way: two triangular cells are represented by one square cell. So I cannot simply use the `getpop` built-in.

Screenshot for input `1000`. Output is `106`:

# Answer
> 2 votes
# Ruby, ~~82 ...~~ 56 bytes

```
a,*r=c=0;loop{p c+=(r!=r-=[a+=1i**(c*2/3)])?-1:(r<<a;1)}

```

Try it online!

Saved a lot of bytes by stealing tsh's formula.

# Answer
> 2 votes
# TypeScript Types, 317 bytes

```
//@ts-ignore
type I<T,P=0,N=[1,0][P]>=T extends[N,...infer T]?T:[...T,P];type M<N,a=[[],[]],b=0,c=0,d=[],e=0,f=[],g=[1,0][c],h=a[0],i=a[1],j=[[I<h,c>,I<i,g>],[h,I<i,c>],[I<h,g>,i]][b]>=N extends d["length"]?f["length"]:j extends e?M<N,j,[1,2,0][b],g,[...d,0],Exclude<e,j>,I<f,1>>:M<N,j,[2,0,1][b],g,[...d,0],e|j,I<f>>

```

Try It Online!

## Ungolfed / Explanation

```
// Increment/decrement an integer stored as e.g. [0, 0] for 2, [1, 1, 1] for -3, and [] for 0
// Invoked as Inc<T> to increment, or Inc<T, 1> to decrement
type Inc<T, Pos = 0, Neg = [1, 0][Pos]> = T extends [Neg, ...infer T] ? T : [...T, Pos]

type Main<
  // The goal number of steps
  N,
  // Last position; stored using axial coordinates as two integers
  LastPos = [[], []],
  // The current axis; 0 | 1 | 2
  DirAxis = 0,
  // The current direction on the axis; 0 | 1
  DirSign = 0,
  // The number of steps taken so far
  Steps = [],
  // A union of all infected positions
  Infected = 0,
  // A tuple counting how many positions are infected
  InfectedCount = [],
  // The sign opposite DirSign
  OtherSign = [1, 0][DirSign],
  // Calculate the new position based on LastPos, DirAxis, and DirSign
  LastPos0 = LastPos[0],
  LastPos1 = LastPos[1],
  NewPos = [
    [Inc<LastPos0, DirSign>, Inc<LastPos1, OtherSign>],
    [LastPos0, Inc<LastPos1, DirSign>],
    [Inc<LastPos0, OtherSign>, LastPos1]
  ][DirAxis]
> =
  N extends Steps["length"]
    // If N == Steps, return InfectedCount
    ? InfectedCount["length"]
    // Otherwise,
    : NewPos extends Infected
      // If NewPos is in Infected,
      ? Main<
        N,
        NewPos,
        // Cycle DirAxis to the right
        [1, 2, 0][DirAxis],
        // Set DirSign to OtherSign
        OtherSign,
        // Add one to Steps
        [...Steps, 0],
        // Remove NewPos from Infected
        Exclude<Infected, NewPos>,
        // Decrement InfectedCount
        Inc<InfectedCount, 1>
      >
      // Otherwise,
      : Main<
        N,
        NewPos,
        // Cycle DirAxis to the left
        [2, 0, 1][DirAxis],
        // Set DirSign to OtherSign
        OtherSign,
        [...Steps, 0],
        // Add NewPos to Infected
        Infected | NewPos,
        // Increment InfectedCount
        Inc<InfectedCount>
      >

```

# Answer
> 1 votes
# Rust, 144 bytes

```
let(mut x,mut p,mut c)=(vec![],[0,0],0);loop{print!("{}
",c);x.retain(|q|q!=&p);if c==x.len(){x.push(p)}c=x.len();p[c*2/3&1]+=1-2*(c/3&1)as i64}

```

Try it online!

Port of @loopy walt's algorithm.

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

```
(Clear@a;c=p=0;a@_=-1;Do[p+=I^⌊2/3(c+=a@p*=-1)⌋,#];c)&

```

Try it online!

A port of @tsh's JavaScript answer.

---
Tags: code-golf, sequence, hexagonal-grid
---


title: AoCG2021 Day 18: Stripping Strips

text:
# Question
Title: AoCG2021 Day 18: Stripping Strips
Part of **Advent of Code Golf 2021** event. See the linked meta post for details.

The story continues from AoC2018 Day 3.

*But you're not Bubbler, you're Lyxal! yeah, I know.*

---

After a long period of chaos, the Elves have finally agreed on how to cut the fabric. Unfortunately, the next day they have come up with how to utilize the leftovers - make a super long present wrapping strip. Well, if it can shrink Santa, it might be able to shrink presents as well...

The description of the strip is a string of `ODCF`, which happens to be the first letters of "up down left right" in Elvish (totally not this Elvish). Divide the fabric into a grid of 1cm × 1cm square cells, select a starting cell somewhere in the middle, and then move around according to the description to claim the strip.

So if the string is `OOCOFFFDD`, you would get this strip, starting at X:

```
OFFF
CO.D
.O.D
.X..

```

... Except that the strip the Elves gave to you is self-intersecting, so it simply doesn't work (a 1cm² fabric part doesn't magically become 2cm² - well, it's physics, at least until Santa comes).

Given the string `OOCOFFFDDCCCD`, the `?` is where the strip self-intersects:

```
OFFF
CO.D
C?CD
DX..

```

In order to avoid the `?` cell becoming a problem, you can take its substring (a contiguous part of the given string) in two ways: `OOCOFFFDDC` (cutting away the last 3 chars) and `COFFFDDCCCD` (cutting away the first 2 chars) gives, respectively,

```
OFFF
CO.D
.OCD
.X..

OFFF
CX.D
CCCD
D...

```

Among the two and all the other options, the latter of the two above is the longest possible.

Given a nonempty string of `ODCF`, determine the length of its longest substring out of which you can make a valid (non-self-intersecting) strip. Assume the fabric leftover is large enough to cover any valid substring of the input.

Standard rules apply. The shortest code in bytes wins.

## Test cases

```
C -> 1
ODD -> 2 (DD)
OOCOFFFDD -> 9 (whole input)
OOCOFFFDDCCCD -> 11 (whole input minus first 2)
OOOFFDCCCDFFFDCOOO -> 12 (minus first 3 and last 3)

```

# Answer
> 5 votes
# TypeScript Types, 537 bytes

```
//@ts-ignore
type a<T,P=0,N=[1,0][P]>=T extends[N,...infer T]?T:[...T,P];type b<T>=T extends{[K in keyof T]:{[L in keyof T]:K extends L?0:T[K]extends T[L]?T:0}[number]}[number]?never:T;type c<T>=T extends[{},...infer U]?T|c<U>:T;type d<T>=T extends[...infer U,{}]?T|d<U>:T;type e<T,K=T extends T?keyof T:0>=T extends T?[K]extends[keyof T]?T:never:0;type f<S,A=[],P=[[],[]],B=[...A,P],X=P[0],Y=P[1]>=S extends`${infer C}${infer R}`?f<R,B,{O:[X,a<Y>],D:[X,a<Y,1>],F:[a<X>,Y],C:[a<X,1>,Y]}[C]>:B;type M<T>=a<e<b<c<d<f<T>>>>>,1,{}>["length"]

```

Try It Online!

## Ungolfed / Explanation

```
// Increment/decrement an integer stored as e.g. [0, 0] for 2, [1, 1, 1] for -3, and [] for 0
// Invoked as Inc<T> to increment, or Inc<T, 1> to decrement
type Inc<T, Pos = 0, Neg = [1, 0][Pos]> = T extends [Neg, ...infer T] ? T : [...T, Pos]

// Filters a union of tuples for those with no duplicate elements
type FilterNoDuplicates<T> =
  // Map over the union T
  T extends
    {
      // Map over the tuple T
      [K in keyof T]: {
        // Map over the tuple T
        [L in keyof T]:
          // If K != L and T[K] == T[L], return T
          K extends L ? 0 : T[K] extends T[L] ? T : 0
      }[number]
    }[number]
      // If any returned T, omit T from the union
      ? never
      // Otherwise, keep T in the union
      : T

// Get all prefixes of T as a union (e.g. [1,2,3] -> [] | [1] | [1,2] | [1,2,3])
type Prefixes<T> = T extends [{}, ...infer U] ? T | Prefixes<U> : T

// Get all suffixes of T as a union (e.g. [1,2,3] -> [] | [3] | [2,3] | [1,2,3])
type Suffixes<T> = T extends [...infer U, {}] ? T | Suffixes<U> : T

// Filter a union of tuples, T, for those with the maximum length
type Longest<T, K = T extends T ? keyof T : 0> = T extends T ? [K] extends [keyof T] ? T : never : 0

// Convert a path like "ODCF" to its path (a list of pairs of integers, starting with (0,0))
type GetPath<
  Str,
  // The current path, not including the current position
  Path = [],
  // The current position
  Pos = [[],[]],
  // Aliases
  NewPath = [...Path, Pos],
  Pos0 = Pos[0],
  Pos1 = Pos[1]
> =
  // Get the first character of Str
  Str extends `${infer Char}${infer Rest}`
    // Recurse
    ? GetPath<
      // Set Str to Rest
      Rest,
      // Set Path to NewPath
      NewPath,
      // Update Pos based on Char
      {
        O: [Pos0, Inc<Pos1>],
        D: [Pos0, Inc<Pos1, 1>],
        F: [Inc<Pos0>, Pos1],
        C: [Inc<Pos0,1>, Pos1]
      }[Char]
    >
    // Str is empty
    : NewPath

// Convert Str to a path, find all subpaths, filter the subpaths
// for no duplicates, find the longest, return its length minus 1
type Main<Str> = Inc<Longest<FilterNoDuplicates<Prefixes<Suffixes<GetPath<Str>>>>>,1,{}>["length"]

```

# Answer
> 5 votes
# Python 3.8 (pre-release) 106, 103 (@pxeger), 96 (@ovs), 89, 84 bytes

```
lambda s,*i,x=0:max(len(i:=[x,*i[:[*i,x:=x+1j**"CDF".find(j)].index(x)]])for j in s)

```

Try it online!

#### Older versions

```
lambda s,i=[0],x=0:max(len(i:=[x:=x+1j**"CDF".find(j)]+i[:(i+[x]).index(x)])for j in s)-1

```

Try it online!

```
lambda s,i=[0],x=0:max(len(i:=i[(x:=x+1j**"CDF".find(j))in i and-~i.index(x):]+[x])for j in s)-1

```

Try it online!

```
x=m=0;i=[]
for j in input():
 i+=x,;x+=1j**"CDF".find(j)
 while x in i:_,*i=i
 m=max(m,len(i))
print(m)

```

Try it online!

```
x=m=0;i=[]
for j in input():
 i+=[x];x+=1j**"CDF".find(j)
 while x in i:i.pop(0)
 m=max(m,len(i))
print(m)

```

Try it online!

# Answer
> 3 votes
# Charcoal, 32 bytes

```
ＦＬθ«Ｆ✂θιＦ¬℅ＫＫ✳⊗⌕FOCκ¹ψ⊞υＬＫＡ⎚»Ｉ⌈υ

```

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

```
ＦＬθ«

```

Loop over each suffix.

```
Ｆ✂θι

```

Loop over the characters in the suffix.

```
Ｆ¬℅ＫＫ

```

Stop if the strip self-intersects.

```
✳⊗⌕FOCκ¹

```

Mark the current cell as part of the strip and move to where the next cell should be.

```
ψ

```

Ensure that the final cell is not part of the strip. This will remove the wrong cell if the strip self-intersected but only the count matters.

```
⊞υＬＫＡ

```

Record the number of cells marked as part of the strip.

Clear the canvas ready for the next suffix or to output the result.

```
»Ｉ⌈υ

```

Output the maximum possible strip length found.

# Answer
> 3 votes
# BQN, ~~40~~ 35 bytesSBCS

```
⌈´·{⊑/¬«∊+`<˘»⍉¬4|31‿37|⌜9×@-∾@}¨↓

```

Run online!

BQN doesn't support complex numbers yet, which means the directions have to be encoded as tuples by `<˘⍉¬4|31‿37|⌜9×@-`:

```
⟨ 'O' ⟨ ¯1 0 ⟩ ⟩ ⟨ 'D' ⟨ 1 0 ⟩ ⟩ ⟨ 'C' ⟨ 0 ¯1 ⟩ ⟩ ⟨ 'F' ⟨ 0 1 ⟩ ⟩

```

We iterate over the suffixes , and get the length of the longest unique prefix of each. The maximum of that is the result.

# Answer
> 2 votes
# Pari/GP, 98 bytes

```
s->vecmax([vecmin([#[1|k<-[j..p=#s+a=0],p*=a+=I^(Vecsmall(s)[k]%69)]+j-i|j<-[i..#s]])|i<-[1..#s]])

```

Try it online!

# Answer
> 2 votes
# Python, 99 bytes

```
f=lambda a,B=1,c=0,*v:a>""and max(B*f(a[1:]),~f(a[1:],0,r:=c+1j**'OCD'.find(a[0]),*v,c)*~-(r in v))
```

Attempt This Online!

Tricks:

* `a>""` is the same as `bool(a)`, since strings are compared lexicographically, and can be used as a recursive base-case because it returns `0` when `a` is empty, unlike simply `a and`
* `a>""` is a sufficient base-case to prevent infinite recursion, which allows shorter conditionals later on because they're allowed to be strictly evaluated (mostly using `*`, and the fact that the output is always positive so we can happily pass `0` to `max`)
* `~X*~-Y` = `-~X*-~-Y` = `(1+X)*(1-Y)` = `(1+X)*(not Y)`
* With the help of the flag variable `B`, I combine the loops searching for the shortest substring into one recursive function

# Answer
> 2 votes
# Rust, 150 bytes

```
|i:&str|i.bytes().scan((vec![],[0,0]),|(v,p),c|{v.push(*p);p[c as usize%23&1]+=1-c as i64%2*2;while v.contains(&p){v.remove(0);};Some(v.len())}).max()

```

Try it online!

Ungolfed:

```
|i: &str| {
    i.bytes()
        .scan((vec![], [0, 0]), |(v, p), c| {
            v.push(*p);
            p[c as usize % 23 & 1] += 1 - c as i64 % 2 * 2;
            while v.contains(&p) {
                v.remove(0);
            }
            Some(v.len())
        })
        .max()
}

```

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

```
Max[s=Subsequences;Length/@Select[s[I^ToCharacterCode@#~Mod~69],FreeQ[Tr/@Rest@s@#,0]&]]&

```

Try it online!

# Answer
> 1 votes
# Python3, 195 bytes:

```
f=lambda d,x,y:{'O':(x+1,y),'C':(x,y-1),'D':(x-1,y),'F':(x,y+1)}[d]
g=lambda s,p=(0,0),q=[]:0 if not s or(n:=f(s[0],*p))in q else g(s[1:],n,q+[p])+1
r=lambda x:max(g(x[i:])for i in range(len(x)))

```

Try it online!

# Answer
> 1 votes
# JavaScript (Node.js), 108 bytes

```
f=a=>Math.max(a&&f(a.slice(1)),Buffer(a).some(g=c=>g[g[[x,y]]=[x+=(c=c%13%5-2)%2,y+=~c%2]]||!++t,t=x=y=0),t)

```

Try it online!

# Answer
> 1 votes
# Ruby, ~~88~~ 86 bytes

```
->s{*l=z=0;s.chars.map{|c|l<<z+=1i**"OCDF".index(c);_,*l=l while l!=l|l;l.size}.max-1}

```

Try it online!

---
Tags: code-golf, string, grid
---


title: Multiplicity of Shared Totients

text:
# Question
Title: Multiplicity of Shared Totients
Euler's totient function, \\$\varphi(n)\\$, counts the number of integers \\$1 \le k \le n\\$ such that \\$\gcd(k, n) = 1\\$. For example, \\$\varphi(9) = 6\\$ as \\$1,2,4,5,7,8\\$ are all coprime to \\$9\\$. However, \\$\varphi(n)\\$ is not injective, meaning that there are distinct integers \\$m, n\\$ such that \\$\varphi(m) = \varphi(n)\\$. For example, \\$\varphi(7) = \varphi(9) = 6\\$.

The number of integers \\$n\\$ such that \\$\varphi(n) = k\\$, for each positive integer \\$k\\$, is given by A014197. To clarify this, consider the table

| \\$k\\$ | Integers \\$n\\$ such that \\$\varphi(n) = k\\$ | How many? (aka A014197) |
| --- | --- | --- |
| \\$1\\$ | \\$1, 2\\$ | \\$2\\$ |
| \\$2\\$ | \\$3, 4, 6\\$ | \\$3\\$ |
| \\$3\\$ | \\$\\$ | \\$0\\$ |
| \\$4\\$ | \\$5, 8, 10, 12\\$ | \\$4\\$ |
| \\$5\\$ | \\$\\$ | \\$0\\$ |
| \\$6\\$ | \\$7, 9, 14, 18\\$ | \\$4\\$ |
| \\$7\\$ | \\$\\$ | \\$0\\$ |
| \\$8\\$ | \\$15, 16, 20, 24, 30\\$ | \\$5\\$ |
| \\$9\\$ | \\$\\$ | \\$0\\$ |
| \\$10\\$ | \\$11, 22\\$ | \\$2\\$ |

You are to implement A014197.

---

This is a standard challenge. You may choose to do one of these three options:

* Take a positive integer \\$k\\$, and output the \\$k\\$th integer in the sequence (i.e. the number of integers \\$n\\$ such that \\$\varphi(n) = k\\$). Note that, due to this definition, you may **not** use 0 indexing.
* Take a positive integer \\$k\\$ and output the first \\$k\\$ integers in the sequence
* Output the entire sequence, in order, indefinitely

This is , so the shortest code in bytes wins.

---

The first 92 elements in the sequence are

```
2,3,0,4,0,4,0,5,0,2,0,6,0,0,0,6,0,4,0,5,0,2,0,10,0,0,0,2,0,2,0,7,0,0,0,8,0,0,0,9,0,4,0,3,0,2,0,11,0,0,0,2,0,2,0,3,0,2,0,9,0,0,0,8,0,2,0,0,0,2,0,17,0,0,0,0,0,2,0,10,0,2,0,6,0,0,0,6,0,0,0,3

```

# Answer
# Jelly, 6 bytes

```
‘²RÆṪċ

```

Try It Online!

```
‘²RÆṪċ  Main Link
‘       x + 1
 ²      (x + 1) ^ 2
  R     range
   ÆṪ   totient
     ċ  count how many times x shows up

```
> 6 votes

# Answer
# Python 3, 86 bytes

```
lambda i:sum(i==sum(2>math.gcd(n,k)for n in range(k))for k in range(3**i))
import math

```

Try it online!

The `3**i` is sufficient. It follows from this inequality.
> 4 votes

# Answer
# Charcoal, ~~44~~ 25 bytes

crossed out 44 is still regular 44

```
Ｉ№ＥＸ⊕θ²ＬΦ⊕ι⬤…·²λ∨﹪λν﹪ιν⊕θ

```

Try it online! Link is to verbose version of code. Outputs the `n`th term of the sequence. Edit: Saved 16 bytes by stealing @HyperNeutrino's upper bound, which then allowed a further 3 bytes of golfing. Explanation:

```
     θ                      Input `n`
    ⊕                       Incremented
   Ｘ                        Raised to power
      ²                     Literal integer `2`
  Ｅ                         Map over implicit range
          ι                 Current value
         ⊕                  Incremented
        Φ                   Filter over implicit range
            …·              Inclusive range
              ²             From literal integer `2`
               λ            To current value
           ⬤                All values satisfy
                   ν        Current value
                 ﹪          Does not divide into
                  λ         Inner value
                ∨           Logical Or
                      ν     Current value
                    ﹪       Does not divide into
                     ι      Outer value
       Ｌ                    Take the length
 №                          Count occurences of
                        θ   Input `n`
                       ⊕    Incremented
Ｉ                           Cast to string
                            Implicitly print

```

The innermost loop erroneously counts `0` as coprime, so this is adjusted for by searching for occurrences of `n+1`.
> 3 votes

# Answer
# Haskell, ~~61~~ 55 bytes

```
f x=sum[1|z<-[1..2*x^2],sum[1|y<-[1..z],gcd z y==1]==x]

```

Try it Online!

-6 bytes thanks to Unrelated String
> 3 votes

# Answer
# JavaScript (ES6), 88 bytes

```
n=>eval("for(t=0,j=n*n*3;j--;)t+=(P=k=>k--&&(C=(a,b)=>b?C(b,a%b):a<2)(j,k)+P(k))(j)==n")

```

Try it online!
> 2 votes

# Answer
# Pari/GP, 32 bytes

```
n->sum(i=1,2*n^2,eulerphi(i)==n)

```

Try it online!
> 1 votes

# Answer
# 05AB1E, 6 bytes

```
>nLÕI¢

```

Port of *@hyper-neutrino♦*'s Jelly answer.

Try it online or verify the first 25 terms.

**Explanation:**

```
>       # Increase the (implicit) input by 1
 n      # Square it
  L     # Pop and push a list in the range [1,(input+1)²]
   Õ    # Convert each value in this list to its Euler's Totient
    I¢  # Count how many times the input is in this list
        # (after which the result is output implicitly)

```
> 1 votes

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


title: AoCG2021 Day 19: To Hire or To Fire

text:
# Question
Title: AoCG2021 Day 19: To Hire or To Fire
Part of **Advent of Code Golf 2021** event. See the linked meta post for details.

The story continues from AoC2018 Day 7, Part 2.

Why I'm pxeger, not Bubbler

---

As soon as you and a few Elves successfully assemble the Sleigh kit, you spot another set of the same kit not so far away. But you noticed that the last Elf is slacking quite a lot but you had to work from start to end without having any free time at all.

In an attempt to fix this, you decide to take a specific number of Elves to maximize *your* free time.

This time, you and the Elves learned how to assemble it, so each job numbered `n` exactly takes `n` seconds to complete (instead of `n + 60` seconds). And, to simplify things, the manual is given simply as a list of pairs of job numbers, each pair `(x, y)` meaning "job `x` should be completed before job `y` can begin". The smallest-numbered worker available (you being number 1 and the Elves being number 2, 3, ...) takes the next available job, smallest number first.

Given the example manual

```
[(3, 1), (3, 6), (1, 2), (1, 4), (2, 5), (4, 5), (6, 5)]

```

the visual order of the jobs is as follows:

```
  -->1--->2--
 /    \      \
3      -->4----->5
 \           /
  ---->6-----

```

If you take 0, 1, or 2 Elves with you (being 1, 2, 3 workers in total), the following will happen respectively:

```
1 worker:
you   | 333122444466666655555

2 workers:
you   | 333122444455555
elf 1 |    666666

3 workers:
you   | 333122   55555
elf 1 |    666666
elf 2 |     4444

```

So you get 3 seconds of rest when there are 3 workers, and no time to rest with fewer. Since there is no opportunity to do 4 jobs in parallel, the 3-worker case is the best for you. If multiple choices give the same amount of time to rest, choose the fewest number of workers.

Note that the amount of rest counts until the last job is finished. So if the input is `[(4, 1), (4, 2), (4, 3)]`, the following happens with 3 workers and you get two seconds of rest at the end:

```
You: 44441__
Elf:     22
Elf:     333

```

**Input:** A description of the manual. Assume every job to be done appears in the manual, and the job numbers are consecutive from 1.

**Output:** The optimal total number of workers.

Standard rules apply. The shortest code in bytes wins.

## Test cases

```
[(2, 1), (3, 2)] -> 1
[(3, 1), (3, 6), (1, 2), (1, 4), (2, 5), (4, 5), (6, 5)] -> 3
[(2, 3), (2, 5), (8, 6), (8, 4), (3, 7), (6, 7), (5, 1), (4, 1)] -> 3
+-2-+-3--+--7-+
|   +-5--|+   |
|        ||   |
+-8-+-6--+|   |
    +-4---+-1-+
1 worker:
2-3-5-8-4-1-6-7
2 worker:
22333555556666667777777
8888888844441
3 worker: (same as 4 worker; no way to parallelize [3, 4, 5, 6])
22333...44441.7777777
88888888666666
  55555

[(4, 1), (4, 2), (4, 3)] -> 3
[(1, 2), (1, 3), (3, 4), (3, 5), (3, 6), (3, 7)] -> 4

```

# Answer
# Ruby, ~~29, then 157 ...~~ 106 bytes

```
->a,*r{(0..a.sum(&:sum)).map{x,y=a.transpose;r+=x&=x-y;a=a.map{|i,j|i>r.count(i)?[i,j]:[j,0]};x.size}.max}

```

Try it online!

### Took me some time so I want to explain:

Just the core loop:

```
x,y=a.transpose;r+=x&=x-y

```

`x` and `y` are the jobs on the left and right side of all instructions in the manual. At any given iteration, we can only execute steps that don't depend on other jobs, so only the ones that aren't in `y`. At the beginning all the jobs are either in `x` or in `y` so we can get them easily.

```
a=a.map{|i,j|i>r.count(i)?[i,j]:[j,0]}

```

After each iteration we check if any job has been completed. If so, then we can remove it from all instructions where it's on the left side, and move the job on the right side to the left (and define a dummy task 0 which won't be executed anyway, to compensate for the missing right side). Next time, all jobs that are no longer blocked by others will be available in `x`.

```
x.size}.max

```

Final result is the max number of jobs that ran in parallel on a single iteration.
> 4 votes

# Answer
# Python3, 279 bytes:

```
f=lambda d,s,q:[len(q)]+([]if not q else f(d,(s:=s+[(i,q.pop(i))[0]for i in [*q] if q[i]==0]),{**{i:q[i]-1for i in q},**{b:b for a,b in d if all(i[0]in s for i in d if i[1]==b)and b not in q and b not in s}}))
g=lambda d:max(f(d,[],{a:a for a,b in d if all(j[1]!=a for j in d)}))

```

Try it online!
> 3 votes

# Answer
# Charcoal, ~~138~~ 135 bytes

```
≔⌈Ｅθ⌈ιηＦη⊞θ⟦⊕ι⁰⟧Ｆη«⊞υ⁰≔Ｅ⊕η⁰ζ≔Ｅ⊕ι⁰εＷΦ⊕η‹§ζλ⬤θ∨§ζ§ν⁰⁻λ§ν¹«≔Ｅκ∨⌈ＥΦθ⁼λ§ν¹§ζ§ν⁰¦⁰δ≔§κ⌕δ⌊δκ⊞υ⁺⊟υ⌈⟦⁰⁻⌊δ§ε⁰⟧ＵＭε⌈⟦λ⌊δ⟧§≔ζκ⁺κ⌊ε§≔ε⌕ε⌊ε§ζκ»»Ｉ⊕⌕υ⌈υ

```

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

```
≔⌈Ｅθ⌈ιη

```

Find the number of jobs.

```
Ｆη⊞θ⟦⊕ι⁰⟧

```

Add a dummy job `0` whose sole purpose is to come after all the other jobs, automatically accounting for the rest time at the end.

```
Ｆη«

```

Try up to as many workers as jobs.

```
⊞υ⁰

```

Start with `0` seconds of rest.

```
≔Ｅ⊕η⁰ζ

```

Start with no jobs started yet.

```
≔Ｅ⊕ι⁰ε

```

Start with no workers having done any jobs yet.

```
ＷΦ⊕η‹§ζλ⬤θ∨§ζ§ν⁰⁻λ§ν¹«

```

Repeat while there are jobs that can be started.

```
≔Ｅκ∨⌈ＥΦθ⁼λ§ν¹§ζ§ν⁰¦⁰δ

```

Find the times at which those jobs can start, assuming a worker is free.

```
≔§κ⌕δ⌊δκ

```

Get the job that's next available.

```
⊞υ⁺⊟υ⌈⟦⁰⁻⌊δ§ε⁰⟧

```

If worker `0` is idle, add on the time to wait before the job can start to the seconds of rest.

```
ＵＭε⌈⟦λ⌊δ⟧

```

Make all idle workers wait until this job can start. (This can mean that the worker doing the job which this job was dependent on ends up doing this job too.)

```
§≔ζκ⁺κ⌊ε

```

Mark this job as started by recording the job's finish time (which is also used to determine when a dependent job can start).

```
§≔ε⌕ε⌊ε§ζκ

```

Give this job to the first available worker and record the worker's finish time.

```
»»Ｉ⊕⌕υ⌈υ

```

Output the smallest number of workers needed to obtain the largest rest time.
> 3 votes

# Answer
# TypeScript Types, 764 bytes

```
//@ts-ignore
type a<T,N=[]>=T extends N["length"]?N:a<T,[...N,0]>;type b<M,J=M[0|1]>=J extends J?[a<Extract<M,[{},J]>[0]>,a<J>]:0;type c<T,K=keyof T>=T extends T?keyof T extends K?T:never:0;type d<T,K=T extends T?keyof T[0]:0>=T extends T?[K]extends[keyof T[0]]?T:never:0;type e<f,g,h=0,i=[],j=[],k=g[number],l=k extends[infer A,infer B]?A extends B?A|h:h:0,>=g extends[infer Elf,...infer ElvesTail]?Elf[1]extends Elf[0]?c<Extract<f,[l,{}]>[1]>extends infer Job?e<Exclude<f,[{},Job]>,ElvesTail,l,[Job,j]extends[0,[]]?[...i,0]:i,[...j,[Job]extends[0]?[0,0]:[Job,[0]]]>:0:e<f,ElvesTail,h,i,[...j,[Elf[0],[...Elf[1],0]]]>:j extends 0[][]?i:e<f,j,h,i>;type M<m,n=[],o=never,p=[...n,[0,0]]>=m[0|1]extends Partial<n>["length"]?c<d<o>[1]>["length"]:M<m,p,o|[e<b<m>,p>,p]>

```

Try It Online!

## Ungolfed / Explanation

<pre><code>// Convert a number literal to a tuple of equal length
type NumToTuple<T,N=[]> = T extends N["length"] ? N : NumToTuple<T,[...N,0]>

// Convert a manual (a union of number literal pairs)
// to a todo list (a union of [Prerequisites, Job])
type ManualToTodo<Manual, Jobs = Manual[0|1]> = Jobs extends Jobs ? [NumToTuple<Extract<Manual,[{},Jobs]>[0]>, NumToTuple<Jobs>] : 0

// Filter a union of tuples for those with the shortest length
type Shortest<T, K=keyof T> = T extends T ? keyof T extends K ? T : never : 0

// Filter a union of tuples for those with the longest first element
type LongestFirstEl<T, K=T extends T ? keyof T[0] : 0> = T extends T ? [K] extends [keyof T[0]] ? T : never : 0

// Repeatedly iterates over a list of elves, either incrementing its progress or assigning it a new job
type CalculateRestTime<
  // A union of [Prerequisites, Job]
  Todo,
  // The tuple of elves being iterated over.
  // Each elf is represented by [Job, TimeElapsed] if working, or [0, 0] if idle
  ElvesIter,
  // A union of finished jobs
  Done=0,
  // The number of steps elf #0 has rested
  RestCount=[],
  // The tuple of elves already iterated over
  ElvesAcc=[],
  /* Aliases */
  ElvesIterValues = ElvesIter[number],
  // The jobs that have been finished by later elves in the iteration
  NewDone = ElvesIterValues extends [infer A, infer B] ? A extends B ? A | Done : Done : 0,
> =
  // Get the first elf in ElvesIter
  ElvesIter extends [infer Elf, ...infer ElvesTail]
    // If this elf is finished or idle
    ? Elf[1] extends Elf[0]
      // Set Job to the first Job in Todo whose prerequisites have been met
      ? Shortest<Extract<Todo,[NewDone, {}]>[1]> extends infer Job
        ? CalculateRestTime<
          // Remove Job from todo
          Exclude<Todo, [{}, Job]>,
          ElvesTail,
          // Update Done
          NewDone,
          // If Job is empty and ElvesAcc is empty, increment RestCount
          [Job, ElvesAcc] extends [0, []] ? [...RestCount, 0] : RestCount,
          // Add this elf to ElvesAcc; if Job is empty, set this elf to [0, 0]; otherwise, set it to [Job, [0]]
          [...ElvesAcc, [Job] extends [0] ? [0,0] : [Job,[0]]]
        >
        // Unreachable
        : 0
      // Otherwise, increment this elf's progress
      : CalculateRestTime<
        Todo,
        ElvesTail,
        Done,
        RestCount,
        [...ElvesAcc, [Elf[0], [...Elf[1], 0]]]
      >
    // ElvesIter is empty. If all elves are idle,
    : ElvesAcc extends 0[][]
      // Return RestCount
      ? RestCount
      // Otherwise, iterate over the elves again
      : CalculateRestTime<Todo, ElvesAcc, Done, RestCount>

type Main<Manual, ElfCount=[], Results=never, NextElfCount=[...ElfCount, [0,0]]> =
  // If all jobs are less than ElfCount.
  Manual[0|1] extends Partial<ElfCount>["length"]
    // Return the best result
    ? Shortest<LongestFirstEl<Results>[1]>["length"]
    // Otherwise, add [RestTime, ElfCount] to the Results union
    : Main<Manual, NextElfCount,Results | [CalculateRestTime<ManualToTodo<Manual>, NextElfCount>, NextElfCount]>
```
</code></pre>
> 3 votes

# Answer
# Pari/GP, 181 bytes

```
a->m=vecmax;l=n=m([m(b)|b<-a]);forvec(v=[[i,k=n^2]|i<-r=[1..n]],u=v-r;if(![v[b[1]]>u[b[2]]|b<-a],d=Vec(sum(i=1,n,(x^v[i]-x^u[i])/(x-1)));if(#d<k,l=m(d);k=#d,#d-k||l=min(l,m(d)))));l

```

Try it online!

Brute force. Extremely slow.

Let \\$n\\$ be the number of jobs. Loops over all tuples \\$\[v\_1,\dots,v\_n\]\\$, where \\$i\le v\_i\le n^2\\$ (a better but longer upper bound would be \\$n(n+1)/2\\$). \\$v\_i\\$ represents the ending time of job \\$i\\$, so the corresponding starting time is \\$v\_i-i\\$. For each tuple, checks if it satisfies the graph.

Now we can write job \\$i\\$ as a polynomial \\$x^{v\_i-i}+\cdots+x^{v\_i}\\$. Let \\$d\\$ be the sum of these polynomials, with \\$i\\$ running from \\$1\\$ to \\$n\\$. Then the ending time of all the jobs is the degree of polynomial \\$d\\$, while the number of workers is the largest coefficient of \\$d\\$.
> 2 votes

# Answer
# Rust, 151 110 85 426 bytes

```
|x:&[[_;2]]|{let(k,mut r)=(*x.iter().flatten().max()?,(0,!0));for c in 1..=k{let(mut u,mut x,[mut e,mut j])=(0,x.to_vec(),[vec![0;c],(0..=k).collect()]);while j.iter().any(|x|x>&0){for t in 0..e.len(){if j[e[t]]>1{j[e[t]]-=1}else{j[e[t]]=0;x.retain(|j|j[0]!=e[t])}}for p in 1..=k{if!e.contains(&p)&&j[p]>0&&x.iter().all(|b|b[1]!=p){for t in 0..e.len(){if j[e[t]]<1{e[t]=p;break}}}}if j[e[0]]<1{u+=1}}r=r.min((!u,c))}Some(r.1)}

```

Try it online!

* -41 bytes by using iterators instead of recursion
* -25 bytes by counting groups
* +341 bytes by fully implementing workers to fix a new test case :(
> 2 votes

# Answer
# Wolfram Language (Mathematica), 156 bytes

```
Min[Max@Total@IntegerDigits[2^#-2^(#-r),2,l+1]&/@Pick[{a,b}=#;s=Select[Range@Tr[r=Range[n=Max@#]]~Tuples~n,#r&&#[[b]]-b#[[a]]&],m=Max/@s,l=Min@m]]&

```

Try it online!

Brute force. Extremely slow.
> 1 votes

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


title: Find The Local Maxima And Minima

text:
# Question
Title: Find The Local Maxima And Minima
# Definition

The maxima and minima of a given function are the largest and smallest values of the function either within a given range or otherwise within the entire domain of the function.

# Challenge

The challenge is to **find the local maxima and minima** of a given polynomial function **using any method you may like**. Don't worry, I will try my best to explain the challenge and keep it as simple as possible.

The input will contain **all the coefficients of the single variable polynomial** in either decreasing or increasing order of power (up to you). For example,

* `[3,-7,1]` will represent \\$3x^2 - 7x + 1\\$
* `[4,0,0,-3]` will represent \\$4x^3 - 3\\$

# How To Solve Using Derivatives

Now, let's say our input is `[1,-12,45,8]`, which is nothing but the function \\$x^3 - 12x^2 + 45x + 8\\$.

1. The first task is to find the derivative of that function. Since it is a polynomial function, so it is indeed a simple task to do.

The derivative of \\$x^n\\$ is \\$n\times x^{n-1}\\$. Any constant terms present with \\$x^n\\$ are simply multiplied. Also, if there are terms added/subtracted, then their derivatives are also added or subtracted respectively. Remember, the derivative of any constant numerical value is zero. Here are a few examples:

* \\$x^3 \to 3x^2\\$
* \\$9x^4 \to 9\times4\times x^3 = 36x^3\\$
* \\$-5x^2 \to -5\times2\times x = - 10x\\$
* \\$2x^3 - 3x^2 + 7x \to 6x^2 - 6x + 7\\$
* \\$4x^2 - 3 \to 8x - 0 = 8x\\$

2. Now solve the equation by equating the new polynomial to zero and get only the integral values of \\$x\\$.
3. Put those values of \\$x\\$ in the original function and return the results. **That should be the output**.

# Example

Let us take the example we mentioned earlier, i.e, `[1,-12,45,8]`.

* Input: `[1,-12,45,8]`
* Function: \\$x^3 - 12x^2 + 45x + 8\\$
* Derivative: \\$3x^2 - 24x + 45 + 0 \to \[3,-24,45\]\\$
* Solving equation: \\$3x^2 - 24x + 45 = 0\\$, we get \\$x = 3\\$ and \\$x = 5\\$.
* Now putting \\$x = 3\\$ and \\$x = 5\\$ in the function, we get the values \\$(62,58)\\$.
* Output: `[62,58]`

# Assumptions

1. Assume that **all the input coefficients are integers**. They can be in increasing or decreasing order of power.
2. Assume the **input to be at least a 2-degree polynomial**. If the polynomial has no integer solutions, you can return anything.
3. Assume that the final result will be integers only.
4. You can print the results in any order. The degree of the input polynomial would not be more than 5, so that your code can handle it.
5. The input will be valid so that the solutions of x are not saddle points.

Also, **you are not forced to do it by the derivative method. You can use any method you feel like.**

# Sample Input And Output

```
[2,-8,0] -> (-8)
[2,3,-36,10] -> (91,-34)
[1,-8,22,-24,8] -> (-1,0,-1)
[1,0,0] -> (0)

```

# Scoring

This is so the shortest code wins.

# Answer
> 4 votes
# Jelly, 20 bytes

```
ASŒRḅ@Ðḟ
J’U×µṖÇḅ@€³

```

Try it online!

# Explanation

```
ASŒRḅ@Ðḟ     Helper Function; find all integer solutions to a polynomial
             All integer roots are within the symmetric range of the sum of the absolute values of the coefficients
A            Absolute Value (Of Each)
 S           Sum
  ŒR         Symmetric Range; `n -> [-n, n]`
      Ðḟ     Filter; keep elements where the result is falsy for:
    ḅ@       Base conversion, which acts like the application of the polynomial
J’U×µṖÇḅ@€³  Main Link
J                             Range of length
 ’                    Lowered
  U          Reversed
   ×         Multiplied with the original list (last value is 0)
    µ        Begin new monadic chain
     Ṗ       Pop; all but the last element
      Ç      Apply last link (get all integer solutions of the derivative)
       ḅ@€³  Base conversion of the polynomial into each of the solutions; apply polynomial to each solution of the derivative.

```

The helper function in this program was taken from Mr. Xcoder's answer here which was based off of Luis's answer here

# Answer
> 3 votes
# JavaScript (ES7), ~~129~~ 120 bytes

Takes the coefficients in increasing order of power.

```
a=>(g=x=>x+k?(A=g(x-1),h=e=>a.reduce((s,n,i)=>s+n*(e||i&&i--)*x**i,0))()?A:[h(1),...A]:[])(k=Math.max(...a.map(n=>n*n)))

```

### Test cases

```
let f =

a=>(g=x=>x+k?(A=g(x-1),h=e=>a.reduce((s,n,i)=>s+n*(e||i&&i--)*x**i,0))()?A:[h(1),...A]:[])(k=Math.max(...a.map(n=>n*n)))

console.log(JSON.stringify(f([0,-8,2])))        // (-8)
console.log(JSON.stringify(f([10,-36,3,2])))    // (91,-34)
console.log(JSON.stringify(f([8,-24,22,-8,1]))) // (-1,0,-1)
```

### Commented

```
a => (                        // given the input array a[]
  g = x =>                    // g = recursive function checking whether x is a solution
    x + k ? (                 //   if x != -k:
      A = g(x - 1),           //     A[] = result of a recursive call with x - 1
      h = e =>                //     h = function evaluating the polynomial:
        a.reduce((s, n, i) => //       for each coefficient n at position i:
          s +                 //         add to s
          n                   //         the coefficient multiplied by
          * (e || i && i--)   //         either 1 (if e = 1) or i (if e is undefined)
          * x**i,             //         multiplied by x**i or x**(i-1)
          0                   //         initial value of s
        )                     //       end of reduce()
      )() ?                   //     if h() is non-zero:
        A                     //       just return A[]
      :                       //     else:
        [h(1), ...A]          //       prepend h(1) to A[]
    :                         //   else:
      []                      //     stop recursion
  )(k = Math.max(             // initial call to g() with x = k = maximum of
    ...a.map(n => n * n)      // the squared coefficients of the polynomial
  ))                          // (Math.abs would be more efficient, but longer)

```

# Answer
> 3 votes
# Java 8, ~~364~~ ~~239~~ ~~227~~ ~~226~~ 218 bytes

```
a->{int l=a.length,A[]=a.clone(),s=0,i,r,f=l,p;for(;f>0;A[--f]*=f);for(int n:A)s+=n<0?-n:n;for(r=~s;r++<s;){for(p=0,i=f=1;i<l;f*=r)p+=A[i++]*f;if(p==0){for(f=i=0;i<l;f+=a[i++]*Math.pow(r,p++));System.out.println(f);}}}

```

Uses the same functionality from this answer of mine.

-8 bytes thanks to *@OlivierGrégoire* by taking the array in reversed order.

**Explanation:**

Try it online.

```
a->{                  // Method with integer-varargs parameter and integer return-type
  int l=a.length,     //  The length of the input-array
      A[]=a.clone(),  //  Copy of the input-array
      s=0,            //  Sum-integer, starting at 0
      i,              //  Index-integer
      r,              //  Range-integer
      f=l,            //  Factor-integer, starting at `l`
      p;              //  Polynomial-integer
  for(;f>0;           //  Loop over the copy-array
    A[--f]*=f);       //   And multiply each value with it's index
                      //   (i.e. [8,45,-12,1] becomes [0,45,-24,3])
  for(int n:A)        //  Loop over this copy-array:
    s+=n<0?-n:n;      //   And sum their absolute values
  for(r=~s;r++<s;){   //  Loop `r` from `-s` up to `s` (inclusive) (where `s` is the sum)
    for(p=0,          //   Reset `p` to 0
        i=f=1;        //   and `f` to 1
                      //   (`i` is 1 to skip the first item in the copy-array)
        i<l;          //   Inner loop over the input again, this time with index (`i`)
        f*=r)         //     After every iteration: multiply `f` with the current `r`
      p+=             //    Sum the Polynomial-integer `p` with:
         A[i++]       //     The value of the input at index `i`,
               *f;}   //     multiplied with the current factor `f`
    if(p==0){         //   If `p` is now 0:
      for(f=i=0;      //    Use `f` as sum, and reset it to 0
          i<l;        //    Loop over the input-array
        f+=a[i++]*Math.pow(r,p++));
                      //     Fill in `r` in the parts of the input-function
      System.out.println(f);}}}
                      //    And print the sum

```

# Answer
> 3 votes
# Julia 0.6 (with `Polynomials` package), 57 bytes

```
using Polynomials
x->map(Poly(x),roots(polyder(Poly(x))))

```

Try it online!

Takes coefficients in increasing order, i.e. the first input is the constant term.

Example run:

```
julia> using Polynomials

julia> g = x -> map(Poly(x), roots(polyder(Poly(x))))
(::#1) (generic function with 1 method)

julia> g([8,45,-12,1])
2-element Array{Float64,1}:
 58.0
 62.0

```

# Answer
> 3 votes
# Wolfram Language (Mathematica), 30 bytes

```
a@x/.#&/@Solve[a=#;#'@x==0,x]&

```

Takes a pure-function polynomial (i.e. a polynomial with `#` as a variable and with a `&` at the end).

Try it online!

# Answer
> 2 votes
# Haskell, 89 bytes

*-3 bytes thanks to Laikoni.*

```
r#l=foldr1((.(r*)).(+))l
r l|_:d<-zipWith(*)[0..]l,t<-sum$abs<$>d=[i#l|i<-[-t..t],i#d==0]

```

Try it online!

Takes coefficients reversed.

# Answer
> 2 votes
# Jelly, 9 bytes

```
J’×UḊÆrḅ@

```

Try it online!

Takes input as a list of coefficients in decreasing order of powers

## How it works

```
J’×UḊÆrḅ@ - Main link. Takes a list of coefficients C on the left
J         - Yield indices; [1, 2, ..., len(C)]
 ’        - Decrement; [0, 1, ..., len(C)-1]
   U      - Yield C reversed
  ×       - Multiply each element of C reversed by each element of [0, 1, ..., len(C) - 1]
    Ḋ     - Remove the leading 0
     Ær   - Solve the polynomial represented by the new list of coefficients
       ḅ@ - Evaluate the roots as inputs to C (base conversion)

```

# Answer
> 2 votes
# Vyxal, 8 bytes

```
∆Ċ:∆Kv∆Q

```

Try it Online!

The power of **actual symbolic algebra**.

## Explained

```
∆Ċ:∆Kv∆Q
∆Ċ        # Convert the list of coefficients into an expression that looks like a*x**n + b*x**(n-1) ... + z
  :       # Push a second copy of that
   ∆K     # Get the stationary points of that (returns x values)
     v∆Q  # and sub those x-values into the original equation

```

# Answer
> 1 votes
# Python 3, 156 bytes

```
def f(p,E=enumerate):a=lambda p,v:sum(e*v**i for i,e in E(p));d=[e*i for i,e in E(p)][1:];r=sum(map(abs,d));return[a(p,x)for x in range(-r,r+1)if a(d,x)==0]

```

Try it online!

-2 bytes thanks to Mr. Xcoder
-22 bytes thanks to ovs

# Answer
> 1 votes
# Python + numpy, 91

* 1 byte saved thanks to @KevinCruijssen

```
from numpy import*
p=poly1d(input())
print map(lambda x:int(polyval(p,x)),roots(p.deriv()))

```

Try it online.

# Answer
> 1 votes
# Pari/GP, 28 bytes

```
p->[eval(p)|x<-polroots(p')]

```

Evaluate the polynomial at the roots of its derivative.

Try it online!

---
Tags: code-golf, polynomials, calculus, equation
---