title: It's Halloween again!

text:
# Question
Title: It's Halloween again!
## Problem Description

We all love a Twix (because it is the best candy), but this is the kids' first Halloween --- we gotta grab at least one of each type of candy for them. Each Halloween all the residents of Numberline avenue send out an email saying what types of candy they'll be giving away this year.

Oh! And we live in a 1D world.

Being exceptionally lazy in some ways and not in others, we've made a map of the houses giving their positions along the street. We also noted the types of candy they have. Here's the map we made for this year:

```
 [(-2, {"Kisses", "KitKats"}),
 (1, {"KitKats", "Peanut Butter Cups"}),
 (6, {"Kisses", "Twix"}),
 (9, {"Skittles"}),
 (10, {"Twix"})]

```

For the sake of the kids' little legs, we need to find the **shortest** walk starting at any house in the neighborhood to gather at **least one** of each type of candy.

## Examples

At the request of a couple users (including Shaggy), I'll toss in some worked examples. Hopefully this clears things up. :) **Input:**

```
 [(-2, {"Kisses", "KitKats"}),
 (1, {"KitKats", "Peanut Butter Cups"}),
 (6, {"Kisses", "Twix"}),
 (9, {"Skittles"}),
 (10, {"Twix"})]

```

**Output:**

```
[1, 2, 3]

```

Another map and solution...

**Input:**

```
[(-3, {"KitKats", "Twix"}),
(-1, {"Hundred Grands"}),
(3, {"Kisses"}),
(12, {"Hundred Grands", "Twix", "KitKats"})]

```

**Output**:

```
[0, 1, 2]

```

We could begin at the coordinate 9 house collecting candies to at houses 6 and 1. That fills the candy quota by walking 8 units, but is it the shortest solution?

## Rules

Entries must take in a *similarly* structured single argument to the example and output the indices of the houses to visit in the shortest solution.

Typical code golf rules apply: shortest correct solution in bytes wins!

*P.S. This was an interview question given to me by one of the world's largest tech companies. If you don't like golf, try finding an O(k\*n) time solution where k is the number of candy types and n is the number of houses.*

## Edit

As Jonathon Allan pointed out, some confusion exists around what "indices" means in this case. We want to output the houses positions **in the argument list** and not their coordinates on the lane.

# Answer
# Python 2, ~~133~~ ~~130~~ 127 bytes

```
def f(l):r=range(len(l));v,c=zip(*l);print min((v[j]-v[i],r[i:j+1])for i in r for j in r if s(*c)==s(*c[i:j+1]))[1]
s={0}.union

```

Try it online!
> 3 votes

# Answer
# Jelly, 16 bytes

```
ŒPṪ€ẎQLƲÐṀẎISƊÞḢ

```

A monadic Link accepting the input as described in a list sorted from lowest to highest Numberline Avenue houses (if we need to accept any ordering we can prepend an ) which yields the shortest path starting at the lowest numbered house and travelling up the Avenue.

**Try it online!**

If we want to find all such shortest paths replace the trailing bytes, `ÞḢ`, with `ÐṂ`; this is also 16 bytes.

### How?

```
ŒPṪ€ẎQLƲÐṀẎISƊÞḢ - Link: list of [index, candies]
ŒP               - power-set
        ÐṀ       - keep those for which this is maximal:
       Ʋ         -   last four links as a monad:
  Ṫ€             -     tail €ach -- this removes the candies lists from the current list
                 -                  and yields them for use now
    Ẏ            -     tighten (to a flat list of candies offered by these hoses)
     Q           -     de-duplicate (get the distinct candies offered)
      L          -     length (how many distinct candies are on offer)
              Þ  - sort (now just the indexes of remaining sets due to Ṫ) by:
             Ɗ   -   last three links as a monad:
          Ẏ      -     tighten (to a flat list of indexes since Ṫ leaves a list behind)
           I     -     incremental differences (distances between houses)
            S    -     sum
               Ḣ - head (get the first)

```
> 3 votes

# Answer
# 05AB1E, 22 bytes

```
æʒ€θ˜I€θ˜åP}€€нD€¥OWQÏ

```

Assumes the numbers in the input-list are sorted lowest to highest.
If more than one solution is found, it will output all of them.

Try it online.

**Explanation:**

```
æ            # Get the powerset (all possible combinations) of the (implicit) input-list
 ʒ           # Filter this list of combinations by:
  €θ         #  Get the last items of each (the list of strings)
    ˜        #  Flatten the list
  I          #  Get the input-list again
   €θ˜       #  Get the last items of each (the list of strings) flattened as well
      å      #  Check for each if it is in the list of strings of this combination
       P     #  Check if all are present
 }           # Close the filter (we now have all combinations, containing all unique strings)
  €€н        # Only leave the first items of each item in the combination (the integers)
     D       # Duplicate this list
      €¥     # Get the deltas (forward differences) of each
        O    # Sum these deltas
         W   # Get the lowest sum (without popping the list)
          Q  # Check for each if it's equal to this minimum
           Ï # And only leave the list of integers at the truthy indices
             # (which are output implicitly as result)

```
> 2 votes

# Answer
# Perl 6, 70 bytes

```
{grep({.[@^i;1]⊇.[*;1]},combinations ^$_).min:{[-] .[@^i[*-1,0];0]}}

```

Try it online!
> 1 votes

# Answer
# Haskell, ~~343~~ 372 bytes

Thanks to @ASCII-only for improvements, there's also a 271 bytes variant he proposed in the comments :)

```
import Data.List
import Data.Function
f s=subsequences(map(\a@(x,y)->(x,y,[(a`elemIndices`s)!!0]))s)
g f s=if f*s<=0 then f+abs f+abs s else f+abs(f-s)
h=foldl(\(a,b,c)(d,e,f)->(g a d,nub(b++e),c++f))(0,[],[])
i s=map h(filter(not.null)s)
l m=filter(\(_,x,_)->length x==(maximum$map(\(_,x,_)->length x)m))m
m=minimumBy(compare`on`(\(p,_,_)->p))
n s=(\(_,_,l)->l)$m$l$i$f s

```

Try it online!

---

**Ungolfed**

```
import Data.List
import Data.Function

allPaths :: [(Integer, [String])] -> [[(Integer, [String], [Int])]]
allPaths xs = subsequences(map (\a@(x,y) -> (x,y,[(a`elemIndices`s) !! 0])) s)

pathLength :: Integer -> Integer -> Integer
pathLength f s = if f*s <= 0 then f + abs f + abs s else f + abs(f - s)

traversePath :: [(Integer, [String], [Int])] -> (Integer, [String], [Int])
traversePath = foldl (\(n1, a1, c1) (n2, a2, c2) -> (pathLength n1 n2, nub (a1 ++ a2), c1 ++ c2)) (0, [], [])

allTraversedPaths :: [[(Integer, [String], [Int])]] -> [(Integer, [String], [Int])]
allTraversedPaths xs = map traversePath (filter (not . null) xs)

getCompletePaths :: [(Integer, [String], [Int])] -> [(Integer, [String], [Int])]
getCompletePaths m = filter (\(_,x,_) -> length x == ( maximum $ map (\(_,x,_) -> length x) m)) m

getFastestPath :: [(Integer, [String], [Int])] -> (Integer, [String], [Int])
getFastestPath = minimumBy (compare `on` (\(p, _, _) -> p))

getPath :: [(Integer, [String])] -> (Integer, [String], [Int])
getPath xs = (\(_,_,l) -> l) getFastestPath $ getCompletePaths $ allTraversedPaths $ allPaths xs

```

---

First attempt
> 0 votes

# Answer
# O(k\*n) time solution, with O(k\*n) space

Let \\$x\_i\\$ be the position of the \\$i\\$th house (where \\$0 \le i \< n\\$, and \\$x\_i\\$ are sorted) and \\$c\_i\\$ be the list of candies offered by the \\$i\\$th house.

Observe that if we have a path from house \\$i\_1\\$ to \\$j\_1\\$ that gets all candy types, then for all \\$i\_0 \< i\_1\\$, there is such a path from \\$i\_0\\$ to \\$j\_0\\$ where \\$i\_0 \le j\_0\\$.

Thus, our algorithm is:

```
// A[k] is the number of each candy we get from the first k houses
A := array of n bags
A[0] := {}
for k := 0 to n - 1
  A[k] := A[k - 1] + c[k - 1]
end
best_distance := ∞
best_i := -1
best_j := -1
// Find the range [i, j] such that we get all candy types
j := n
for i := n - 1 to 0
  while j > i and (A[j - 1] - A[i]) has all candy types
    j := j - 1
  end
  if (A[j] - A[i]) does not have all candy types then continue end
  distance = x[j - 1] - x[i]
  if distance < best_distance then
    best_distance = distance
    best_i = i
    best_j = j
  end
end
return best_i ..^ best_j

```

The construction of \\$A\\$ takes \\$O(k)\\$ time for each element, or \\$O(nk)\\$ time (and space) total. The outer loop for computing the best distance executes \\$n\\$ times. The inner loop can execute up to \\$n\\$ times in one iteration, but the body is executed at most \\$n\\$ times, so the condition is checked \\$O(n)\\$ times; thus, the inner loop accounts for a total of \\$O(nk)\\$ time. The rest of the outer loop body takes \\$O(k)\\$ time as well. Hence, our algorithm takes \\$O(nk)\\$ time and space.
> 0 votes

---
Tags: code-golf
---


title: Dobble/SpotIt card generator

text:
# Question
Title: Dobble/SpotIt card generator
## Introduction

Dobble/SpotIt is a card game, where people have to spot same symbol on pair of cards in shortest time, indicate it and move to next pair. Each card has multiple symbols (8 in normal version), but exactly one is common between each pair of cards.

Example from physical copy of game:

## Challenge

Write a program, which given set of symbols (single ascii characters) and number of symbols on single card will produce output listing cards with symbols for each card. There are obviously many equivalent combinations, your program just has to write any of combinations which produces largest amount of cards for given input.

It is a code-golf, so shorter the code, better.

It would be also great if computation will finish before heat death of universe for most complicated case.

## Input

Two arguments to function/stdin (your choice)

* First of them being collection of symbols, something like 'ABCDE" or \['A','B','C','D','E'\] - your choice of format, be it string, set, list, stream, or whatever is idiomatic for language of choice. Characters will be given from set of \[A-Za-z0-9\], no duplicates (so maximum size of input symbol set is 62). They won't be neccesarily ordered in (so you can get "yX4i9A" as well for 6-symbol case).
* Second argument is integer, indicating amount of symbols on single card. It will be \<= than size of symbol set.

## Output

Print multiple lines separated by newlines, each one of them containing symbols for single card.

## Examples

```
ABC
2
>>>>
AB
BC
AC

```

Or

```
ABCDEFG
3
>>>>
ABC
BDE
CEF
BFG
AEG
CDG
ADF

```

Or

```
ABCDE
4
>>>>
ABCD

```

## Hints

* Number of cards produced cannot be larger than amount of distinct symbols and in many combinations it will be considerably smaller
* You might want to read up Some math background if you need help with math side of the problem

This is my first code golf challenge, so please forgive possible issues with formatting/style - I'll try to correct errors if you point them in comments.

Edit: There is a very nice youtube video explaining the math behind the Dobble setup here:

# Answer
> 6 votes
# Python 2, ~~192~~ 162 bytes

I have an argument that this produces the maximum set of cards for every scenario and it does handle the 3 test cases.

```
from itertools import*
def m(a,s):
    C=["".join(x)for x in combinations(a,s)]
    while len(C):
        print C[0]
        C=list(set(A for A in C if len(set(A)&set(C[0]))==1<s))

```

Try it online!

### Algorithm

Given an alphabet `a` and a card size `s`, take all combinations of `s` elements in `a` and call it `C`, then:

* Take the first element of `C`, call it `C0`
* Save `C0`
* Remove all elements from`C` that have a union with `C0` not equal to `1`
* Repeat with second element of `C`
* Continue until `C` is empty

Then print the saved elements.

### Argument

Some non-empty subset of `C` is our maximal solution, `K`. Since it contains at least one element and any two elements are indistinguishable, choose an arbitrary element, `C0`, of `C` to be in `K`. For any element `e` in the `K`, the cardinality of `e` union `x` is 1 for `x != e` in `K`; so eliminate all elements in `C` whose union with `C0` does not have cardinallity 1. By the same reasoning, choose a new arbitrary element in `C`, add it to `K`, and reduce `C`. Eventually `C` is the empty set and `K` will be the maximal solution because at no point did we choose an element that was distinguishable from any other element.

---

## Test Cases

These test cases were written before I realized that the printing was a requirement.

```
a=["a","b","c"]
b=2
c=3
d=m(a,b)
print d,len(d)==c
>> ['bc', 'ab', 'ac'] True

a=["a","b","c","d","e","f","g"]
b=3
c=7
d=m(a,b)
print d,len(d)==c
>> ['aef', 'abc', 'bde', 'ceg', 'adg', 'cdf', 'bfg'] True

a=["a","b","c","d","e"]
b=4
c=1
d=m(a,b)
print d,len(d)==c
>> ['abcd'] True

```

**Update**

* **+9** \[16-12-07\] Fit the print requirement
* **-11** \[16-12-07\] Golfed out my `R` variable
* **-30** \[16-12-09\] Golfed out my `K` variable, Thanks to *@Leo*!

# Answer
> 3 votes
# Haskell, ~~175~~ 156 bytes

My first take at golfing, let me know if I've messed something up.

```
import Data.List
f 0_=[[]]
f n a=g$c n a
c n a=[a!!i:x|i<-[0..(length a)-1],x<-f(n-1)(drop(i+1)a)]
g[]=[]
g(x:t)=x:g(filter(\z->length(z`intersect`x)<= 1)t)

```

Try it online!

Thank to @Paul Mutser for improvement and -19 bytes

---

Original version

# Answer
> 1 votes
# Perl 6, ~~88~~ 77 bytes

```
{+(combinations($^a,$^n),{my \d=.[0];say d.join;grep *∩d==1,.[1..*]}...!*)}

```

Try it online!

---
Tags: code-golf, game, combinatorics, set-partitions
---


title: ASCII ruler generation

text:
# Question
Title: ASCII ruler generation
The challenge is to generate an ASCII character count ruler in the following format:

```
+-------------------------------------------------------------------------+
||    |    |    |    |    |    |    |    |    |    |    |    |    |    |  |
|0         10        20        30        40        50        60        70 |
|                                                                         |
+-------------------------------------------------------------------------+

```

The length of the ruler should be scalable to any multiple of 10.

Rules:

* Ruler must be horizontal.
* Let's say, to keep things simpler, that the ruler must work until the 1000 mark, all numbers left-aligned, **one space after the final number**.
* Asking for a ruler with zero length should print NaR
* Negative numbers should print a reversed ruler (-90, -80, -70, ...) with right-aligned numbers, in the exact same format as the one above otherwise

And, just printing to console is fine

Ready, set, golf!

# Answer
# Python - 227 232

**Supports entire specification**

**edit:** improved generator expression.

Supporting right aligned negative numbers adds a surprising amount of code.

```
b,p,d,w,='|+- '
g=input
s=''.join(('%'+d[:i>0]+'10s')%i+['',9*w][i==0] for i in range(g(),g()+1,10)).strip()+w
m,n=s[0]==d and s.find(w)-1,len(s)
t=p+n*d+p
print['\n'.join([t,b+(w*m+'|    '*n)[:n]+b,b+s+b,b+n*w+b,t]),'NaR'][n<9]

```

Sample outputs:

-30 30

```
+-----------------------------------------------------------------+
|  |    |    |    |    |    |    |    |    |    |    |    |    |  |
|-30       -20       -10         0         10        20        30 |
|                                                                 |
+-----------------------------------------------------------------+

```

-30 -30

```
NaR

```

100 150

```
+------------------------------------------------------+
||    |    |    |    |    |    |    |    |    |    |   |
|100       110       120       130       140       150 |
|                                                      |
+------------------------------------------------------+

```

-1000 -950

```
+--------------------------------------------------------+
|    |    |    |    |    |    |    |    |    |    |    | |
|-1000      -990      -980      -970      -960      -950 |
|                                                        |
+--------------------------------------------------------+

```
> 8 votes

# Answer
Not going to beat the dynamic languages today, but anyway...

## Haskell, 341

```
import Data.List
main=interact$unlines.m.map read.words
m[l,r]|r>l=ᴛ.("┌│││└":).(++["┬   ─","┐│││┘"]).ʀ.t.ʀ.t.takeWhile((>4).length).ᴛ$[c"┬",c"│    ",[l,l+10..r]>>=h.show,c" ",c"─"]|True=["NaR"]
h s=p s$length s;p s@('-':_)l=r(6-l)ꜱ++s++r 4ꜱ;p s l=r 5ꜱ++s++r(5-l)ꜱ
ᴛ=transpose;ʀ=reverse;r=replicate;c=cycle
ꜱ=' ';t l@(c:o)|c!!2==ꜱ=t o|True=l

```

I took the liberty of exchanging the actual ASCII characters with better-looking unicode box drawing chars.

```
$ echo "-50 30" | runhaskell  def0.hs
┌┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┐
│  │    │    │    │    │    │    │    │    │    │    │    │    │    │    │    │    │  │
│-50       -40       -30       -20       -10         0         10        20        30 │
│                                                                                │
└─────────────────────────────────────────────────────────────────────────────────────┘

```
> 10 votes

# Answer
Python 2.7, ~~342 266~~ 260 chars

```
a,b,c,d,m='+|- \n'
def f(y):x=map(str,(range(0,y+1,10)if y>0 else range(y,1,10)));h,g=len(x[-1])+1,len(x)-1;u=a+(c*10)*g+c*h+a;return'NaR'if y==0 else u+m+b+(b+d*4)*2*g+b+d*(h-1)+b+m+b+''.join(i.ljust(10)for i in x[:-1])+x[-1].ljust(h)+b+m+b+(d*10)*g+d*h+b+m+u

```

returns a ~~tuple of each line~~ string, which you can then print or save to a file (I prefer the latter for lengths longer than 70 becuase the console will jsut make it look messed up with wrapping)

Assumes `y` to be ~~a string (raw\_input() n python, or sys.argv\[1\] if you wish to invoke via cmd)~~ an integer (eg with input() in 2.x or int(input()) in 3.x)

I made this a function to be more flexible

edit: reduced to 266 characters. no longer returns a tuple, but a string instead. Now takes an integer instead of a string as the argument

edit2: reduced to 260 chars, single line function

note: does handle negative numbers, but doesn't right justify (I don't really htink the justification is too important anyways
> 3 votes

# Answer
# PowerShell, ~~256~~ ~~253~~ ~~233~~ ~~225~~ 222 bytes

```
param($a,$b)('NaR',$($d=@{}
$a..$b|%{$d.$_=' ';0..($l=($s="$($_-$_%10)").Length-1)|%{$d[$_+$s-$l*(0-gt$s)]=$s[$_]}}
$d.Keys|sort|%{$e+='-';$p+='|    '[$_%5];$r+=$d.$_;$w+=' '}
@"
+$e-+
|$p |
|$r |
|$w |
+$e-+
"@))[$a-lt$b]

```

Try it online!

Less golfed:

```
param($a,$b)
(
    'NaR',
    $(
        # {key, value} := {position, digit|minus|space}
        $d=@{}
        $a..$b|%{
            $d.$_=' '

            # draw a nearest left number
            $n=$_-$_%10
            $s="$n"
            $l=$s.Length-1
            0..$l|%{
                $d[$_+$s-$l*(0-gt$s)]=$s[$_]
            }
        }

        # edge, points, ruler, whitespaces
        $d.Keys|sort|%{
            $e+='-'
            $p+='|    '[$_%5]
            $r+=$d.$_
            $w+=' '
        }

        # output the multiline string
@"
+$e-+
|$p |
|$r |
|$w |
+$e-+
"@
    )
)[$a-lt$b]

```
> 1 votes

# Answer
Perl 5.14, ~~198~~ 224 chars

Probably can be shortened a lot further, but here's a ~~first~~ second attempt (with line breaks inserted for readability):

```
$l=shift||die"NaR\n";
@n=grep!($_%10),$l>0?0..$l:$l..0;
$l=9-length$n[$#n];
@f=('-'x10,'|    'x2,'@'.'<'x9,' 'x10);
@f=map$_ x@n,@f;
map$_=~s/.{$l}$//,@f;
eval"format=\n+$f[0]+\n|$f[1]|\n|$f[2]|\n\@n\n|$f[3]|\n+$f[0]+\n.\n";
write

```

**EDIT:** Edited to die with "NaR" when input is `0` and to support negative range.

**EDIT2:** I haven't had a chance to work more on this, and I only just now noticed the right aligned for negative numbers rule, which my code doesn't support, so I think another solution should be marked as the answer if the deadline has been reached.
> 0 votes

# Answer
## Python, 291 241 characters

A pretty simple approach. I'm sure it can be improved quite a lot.
I tried to follow the guidelines in the comments, but I don't support negative numbers (it was a joke, I hope).
This is a program, prints the ruler to standard output. If your screen is wide enough, it should support pretty long rulers.

```
import sys
def p(b,a="|"):print a+b+a
j="".join
l=int(sys.argv[1])//10*10
if l:
    d=j(["%-10d"%n for n in range(0,l,10)])+"%d "%l
    L=len(d)
    h="-"*L
    p(h,"+")
    p(j(["|    "[n%5] for n in range(L)]))
    p(d)
    p(" "*L)
    p(h,"+")
else: print "NaR"

```
> 0 votes

# Answer
## C++, 392

This is programmed using the windows console, therefore I just chose a maximum ruler size is 70, it'll just crash for anything bigger. Negative numbers( up to -70) and 0 are handled correctly.

```
#include<ios>
#define q s[2][i
#define v ,memset(&s
char g,o,i,n,s[5][80];int main(int a,char**b){a=atoi(b[1])v,32,400);n=0<a;for(a=abs(a)v[0][1],45,a+3)v[4][1],45,a+3);i<a+4;++i)o=i-n,!(o%5)?s[1][n?i:i+3]='|',(o%2-1?(n?q]=i/10+48,i>9?q+1]=48:0:((a-i)>9?q+2]=(a-i)/10+48,q+1]=45:0,q+3]=48)):0):0;for(;g-5;g++)for(s[g][a+4]=s[g][i=0]=g&g-4?'|':43;i-80;i++)printf(a?"%c":g+i?"":"NaR",s[g][i]);}

```
> 0 votes

# Answer
# Python - 208

(does not support right aligned negative numbers)

```
 l,u=map(int,raw_input().split())
 n=u-l
 q="+%s+\n"
 q=q+"|%s|\n"*3+q
 print q%('-'*n,(''.join("|    "for i in range(n)))[:n],(''.join("{:<10d}".format(i)for i in range(l,u,10)))[:n],' '*n,'-'*n)if n>0 else"NaR"

```

I think my favourite trick was to generate strings that are way longer than necessary and then truncate them, for example:

```
 ''.join("|    "for i in range(n)))[:n]

```

I just wish there was a more concise string formatting option for left-alignment (unless there is one that I just don't know about)
> 0 votes

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


title: Make a Frogger Solver

text:
# Question
Title: Make a Frogger Solver
#

You must make the shortest program to always find the optimal solution to a simplified Frogger game on a 9x9 grid.

**Course Elements:**

* `L` \- Log (Length: 3-4). When you hop on a log, it carries you with it.
* `V` \- Vehicle (Length: 1-2)
* Speed (1-2): On the left hand side of the row will be the speed that elements in the row move.
* Spaces: There will **always** be at least two spaces between elements.
* Direction: In both the Vehicle and the Log sections, the direction of movement in each lane alternates between left and right.

**Course Structure:**

* If it's capital, it goes right; if it's lowercase, it goes left. All elements in a row go the same direction. As soon as part of an element goes off the screen, it will appear on the opposite side of the screen.
* The first row is a safe zone. The frog starts at `F`, which is always the same spot.
* The next 3 rows are roads with Vehicles.
* The next row is a safe zone.
* The next 3 rows are water (touching water == death) with Logs.
* Once you reach the `W` lane you win.
* If the frog dies it goes back to `F`

**Player Controls:**

* `L` \- Left
* `R` \- Right
* `U` \- Up
* `D` \- Down
* `W` \- Wait

After you move, another frame passes. (Note that the frame passes after your move, not at the same time as your move.) Your program must give the optimal solution as a sequence of characters such as `URWUUL`. If a course has no solution, your program should output `N`.

**Examples:** (Since I did these by hand I don't know if they are optimal solutions.)

```
0WWWWWWWWW
1  lll
2  LLLL
2  llll
0
1  vv  vv
1  V  V
1   vv
0    F
```

Solution: `WUWUUURWUULWUU`

```
0WWWWWWWWW
2   lll
1   LLLL
1   lll
0
2   vv
1  VV
2   vv
0    F
```

Solution: `WUWUWUUWUUWWUU`

```
0WWWWWWWWW
2   llll
2   LLL
1   llll
0
2  v   vv
1  VV  VV
1  v  v
0    F
```

Solution: `WWUUUURURRWWUUU`

```
0WWWWWWWWW
2  llll
2   LLL
1   lll
0
1   vv  v
2 V  V  V
2 v  v  v
0    F
```

Solution: `N` (No way to get past first row.)

Test these in the snippet by pasting the course into the textbox and pushing "Load Course". Then paste the solution into "Input" and push submit.

**Snippet:** It's hard to make test cases, so I made this snippet which lets you see if your program can solve randomly-generated courses. For testing purposes, all you need to do is input your program's solution (e.g. `LRUWL...`) into the "Input" section and push submit. To reset the course back to it's original state push "Reset". Let me know if you find any bugs.

```
var timer;
var f_x, f_y;
var replaced;
var copy;
document.body.onkeyup = function(e) {
  var a = document.activeElement;
  if (a !== controls && a !== data) hop(e.keyCode);
};

function setup() {
  stop();
  var rows = game.children;
  rows[0].innerHTML = "0WWWWWWWWW";
  load(logs, "L");
  rows[2].innerHTML = "0         ";
  load(cars, "V");
  rows[4].innerHTML = "0    F    ";
  copy = game.innerHTML;
  save();

  f_x = 5;
  f_y = 9;
  replaced = " ";
}

function save() {
  data.value = "";
  for (var i = 1; i <= 9; i++) {
    data.value += getRow(i).textContent;
    if (i < 9) data.value += "\n";
  }
}

function extLoad() {
  stop();
  var rows = data.value.split("\n");
  replaced = " ";
  for (var i = 0; i < rows.length; i++) {
    var r = getRow(i + 1);
    r.innerHTML = rows[i].replace(/ /g, " ");
    if (rows[i].indexOf("V") !== -1 || rows[i].indexOf("L") !== -1) r.className = "right";
    else if (rows[i].indexOf("v") !== -1 || rows[i].indexOf("l") !== -1) r.className = "left";
    var f = rows[i].indexOf("F");
    if (f !== -1) {
      f_y = i + 1;
      f_x = f;
    }
  }
  copy = game.innerHTML;
}

function reset() {
  stop();
  game.innerHTML = copy;
  f_x = 5;
  f_y = 9;
  replaced = " ";
}

function play() {
  if (!timer) {
    timer = setInterval(next, 1500);
  }
}

function stop() {
  if (timer) {
    clearInterval(timer);
    timer = null;
  }
}

function input(i) {
  var s = controls.value;
  if (i === 0) {
    stop();
    sub.disabled = true;
  }
  if (s[i] === "L") hop(65);
  else if (s[i] === "U") hop(87);
  else if (s[i] === "R") hop(68);
  else if (s[i] === "D") hop(83);
  next();
  if (i < s.length - 1) setTimeout(function() {
    input(i + 1);
  }, 750);
  else sub.disabled = false;
}

function load(part, code) {
  for (var r = 0; r < 3; r++) {
    var row = part.children[r];
    var s = "";
    var dir = r % 2;
    row.className = dir === 1 ? "right" : "left";
    s += Math.floor(Math.random() * 2) + 1;
    var end = 0;
    for (var c = 0; c < 9-end;) {
      var spaces = Math.min(9 - end - c , Math.floor(Math.random() * 2) + 2);
      if(c === 0 && end===0) {
        spaces = Math.floor(Math.random()*4);
        end = Math.max(0,2-spaces);
      }
      s += " ".repeat(spaces);
      c += spaces;
      var type = "";
      var len = 0;
      var rand = Math.floor(Math.random() * 2);
      if (code === "L") {
        type = dir === 1 ? "L" : "l";
        len = rand + 3;
      } else {
        type = dir === 1 ? "V" : "v";
        len = rand + 1;
      }
      if (c + len > 9-end) continue;
      s += type.repeat(len);
      c += len;

    }
    row.innerHTML = s + " ".repeat(end);
  }
}

function next() {
  move(logs);
  move(cars);
}

function move(part) {
  var rows = part.children;
  for (var i = 0; i < rows.length; i++) {
    var s = rows[i].textContent;
    var f = s.indexOf("F") !== -1;
    if (f) {
      replace(f_y, f_x, false);
      s = rows[i].textContent;
    }
    var speed = s[0];
    var stuff = s.substring(1);
    var v = vel(speed, rows[i].className);
    rows[i].textContent = s[0] + shift(stuff, speed, rows[i].className);
    if (f) {
      if (part === logs) {
        f_x += v;
        if (f_x < 1 || f_x > 9) {
          go(5 - f_x, f_y - 9);
          return;
        }
      }
      replace(f_y, f_x, true);
      s = rows[i].textContent.substring(1);
      var c = f_x + v;
      var t = "";
      if (c > 9) t = s.substring(f_x) + s.substring(0, c - 9);
      else if (c < 0) t = s.substring(0, f_x) + s.substring(9 + c);
      else t = v > 0 ? s.substring(f_x, c) : s.substring(c, f_x);
      if (t.indexOf("V") !== -1 || t.indexOf("v") !== -1) {
        go(5 - f_x, f_y - 9);
      }

    }

  }
}

function vel(mag, dir) {
  var d = dir === "right" ? 1 : -1;
  var m = parseInt(mag);
  return d * m;
}

function shift(s, n, d) {
  n = parseInt(n);
  for (var i = 0; i < n; i++) {
    if (d === "left") {
      s = s.substring(1) + s.substring(0, 1);
    } else {
      s = s.substring(s.length - 1) + s.substring(0, s.length - 1);
    }
  }
  return s;
}

function hop(k) {
  if (k === 65) go(-1, 0);
  else if (k === 87) go(0, 1);
  else if (k === 68) go(1, 0);
  else if (k === 83) go(0, -1);
}

function go(x, y) {

  replace(f_y, f_x, false);
  f_y -= y;
  f_x += x;
  replace(f_y, f_x, true);
  if (f_x < 1 || f_x > 9 || f_y > 9) {
    go(5 - f_x, f_y - 9);
    return;
  }

  if (f_y == 1) {
    alert("win!");
    go(5 - f_x, f_y - 9);
  }

}

function replace(y, x, f) {

  var row = getRow(y);
  if (!row) return false;

  var s = row.textContent;
  if (x < 1 || x >= s.length) return false;
  if (f) {
    replaced = s[x];
    if (replaced === "V" || replaced === "v" || (replaced.charCodeAt(0) === 160 && y < 5)) {
      go(5 - f_x, f_y - 9);

    } else {
      row.textContent = s.substring(0, x) + "F" + s.substring(x + 1);
    }
  } else {
    row.textContent = s.substring(0, x) + replaced + s.substring(x + 1);
  }

}

function getRow(y) {
  if (y < 1 || y > 9) return false;
  if (y === 1) return game.firstChild;
  if (y === 9) return game.lastChild;
  if (y > 5) return cars.children[y - 6];
  if (y < 5) return logs.children[y - 2];
  return game.children[2];
}
```

```
<body onload="setup()"><code id="game"><div></div><div id="logs"><div></div><div></div><div></div></div><div></div><div id="cars"><div></div><div></div><div></div></div><div></div></code>
  <input type="button" value="Step" onclick="next()" />
  <input type="button" value="Pause" onclick="stop()" />
  <input type="button" value="Play" onclick="play()" />
  <input type="button" value="Reset" onclick="reset()" />
  <input type="button" value="New Course" onclick="setup()" />
  <div>Controls: WASD</div>
  <div>Input:
    <input type="text" id="controls" />
    <input type="submit" onclick="input(0)" id="sub" />
  </div>
  <div>
    <textarea id="data" rows=9 cols=12></textarea>
    <input type="button" onclick="extLoad()" value="Load Course" />
    <input type="button" onclick="save()" value="Save Course" />
  </div>
</body>
```

**Where to Start:**

**Related:**

**See also:**

# Answer
## Javascript, 854 bytes

```
function f(w){h=[];z=[];for(y=0;y<9;y++){l=w.split('\n')[y];r={s:parseInt(l[0]),d:1,e:[]};for(x=0;x<9;x++){c=l[1+x];if(c=='v'||c=='l')r.d=-1;r.e.push(c);}z.push(r);}h.push(z);h.push(z);for(g=2;g<40;g++){z=JSON.parse(JSON.stringify(z));for(y=0;y<9;y++){r=z[y];if(r.s>0&&(g%2==0||r.s==2)){i=0;t=0;if(r.d==-1){t=r.e[0];for(i=0;i<8;i++)r.e[i]=r.e[i+1];r.e[i]=t;}else{t=r.e[8];for(i=8;i>0;i--)r.e[i]=r.e[i-1];r.e[i]=t;}}}h.push(z);}j=15;k="";m(0,4,8,"","");return k==""?"N":k;function m(s,a,b,u,v){if(s<j){q={'U':[0,-1],'D':[0,1],'L':[-1,0],'R':[1,0]}[u];if(q)a+=q[0],b+=q[1];v+=u;if(!b){j=s;k=v;return;}if(s>0){for(i=0;i<3;i++){z=h[s*2+i-2];r=z[b];if(i&&(i==1||r.s==2)&&r.e[a].toUpperCase()=='L')a+=r.d;if(a<0||a>8||b>8)return;z=h[s*2+i-1];e=z[b].e;if(e[a].toUpperCase()=='V'||(b<4&&e[a].toUpperCase()!='L'))return;}}t="UWRLD";for(x in t)m(s+1,a,b,t[x],v);}}}

```

Ungolfed

```
function solve(input) {
    var grids = [];
    var maxgrid = 40;
    // load input
    var grid = [];
    var lines = input.split('\n');
    for (var y = 0; y < 9; y++) {
        var line = lines[y];
        var row = {
            speed: parseInt(line[0]),
            direction: 1,
            cells: []
        }
        for (var x = 0; x < 9; x++) {
            var c = line[1 + x];
            if (c == 'v' || c == 'l')
                row.direction = -1;
            row.cells.push(c);
        }
        grid.push(row);
    }
    grids.push(grid);
    grids.push(grid);
    // animate grids
    for (var g = 2; g < maxgrid; g++) {
        grid = JSON.parse(JSON.stringify(grid));
        for (var y = 0; y < 9; y++) {
            var row = grid[y];
            if (row.speed > 0 && (g % 2 == 0 || row.speed == 2)) {
                if (row.direction == -1) {
                    var i, temp = row.cells[0];
                    for (i = 0; i < 8; i++)
                        row.cells[i] = row.cells[i + 1];
                    row.cells[i] = temp;
                }
                else {
                    var i, temp = row.cells[8];
                    for (i = 8; i > 0; i--)
                        row.cells[i] = row.cells[i - 1];
                    row.cells[i] = temp;
                }
            }
        }
        grids.push(grid);
    }
    var best = 15;
    var best_moves = "";
    var forceExit = false;

    move(0, 4, 8, "", "");
    return best_moves == "" ? "N" : best_moves;

    function move(step, fx, fy, dir, moves) {
        if (step >= best)
            return "die";
        switch (dir) {
            case 'U':
                fy--;
                break;
            case 'D':
                fy++;
                break;
            case 'L':
                fx--;
                break;
            case 'R':
                fx++;
                break;
        }
        if (dir != '')
            moves += dir;
        if (fy == 0) {
            best = step;
            best_moves = moves;
            return "win";
        }
        if (step > 0) {
            for (var i = 0; i < 3; i++) {
                var grid = grids[step * 2 + i - 2];
                if (i > 0 && (i == 1 || row.speed == 2)) {
                    var row = grid[fy];
                    if (row.cells[fx].toUpperCase() == 'L')
                        fx += row.direction;
                }
                if (fx < 0 || fx > 8 || fy > 8)
                    return "die";
                var grid = grids[step * 2 + i - 1];
                var cells = grid[fy].cells;
                if (cells[fx].toUpperCase() == 'V')
                    return "die";
                if (fy < 4 && cells[fx].toUpperCase() != 'L')
                    return "die";
            }
        }
        move(step+1, fx, fy, 'U', moves);
        move(step+1, fx, fy, 'W', moves);
        move(step+1, fx, fy, 'R', moves)
        move(step+1, fx, fy, 'L', moves);
        move(step+1, fx, fy, 'D', moves)
    }
}

```

I'm only testing for Up, Wait and Right in the example to speed things up:

JSFiddle
> 1 votes

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


title: Convert to Roman Numeral!

text:
# Question
Title: Convert to Roman Numeral!
Your task is to convert a given **positive integer** from Arabic numeral to Roman numeral.

Things get difficult when you count to 4000.

The romans did this by adding a line above a symbol to multiply that symbol by `1 000`. However, overlines aren't exactly displayable in ASCII. Also, there are double overlines to multiply a symbol by `1 000 000`, and then triple overline to multiply a symbol by `1 000 000 000`, etc...

Therefore, I decided to use **parentheses** to replace overlines.

The symbols can be **individually** placed in parentheses. For example, both `(VI)` and `(V)(I)` are valid representations of `6 000`. `(V)M` is also a valid representation of 6000.

`(I)` is a valid way to represent `1 000`.

### Testcases

```
Input: 1
Output: I
Input: 2
Output: II
Input: 3
Output: III
Input: 4
Output: IV
Input: 15
Output: XV
Input: 40
Output: XL
Input: 60
Output: LX
Input: 67
Output: LXVII
Input: 400
Output: CD
Input: 666
Output: DCLXVI
Input: 3000
Output: MMM
Input: 3999
Output: MMMCMXCIX
Input: 4000
Output: M(V)
Input: 4999
Output: M(V)CMXCIX
Input: 6000
Output: (VI)
Input: 6000000
Output: ((VI))
Input: 6006000
Output: ((VI)VI)
Input: 6666666666
Output: (((VI)DCLXVI)DCLXVI)DCLXVI

```

### Scoring

This is . Shortest code in bytes win.

# Answer
## Mathematica, 67 bytes

```
Fold["("<>#<>")"<>#2&,RomanNumeral[#~IntegerDigits~1000]/."N"->""]&

```

Avoids all trouble with `M` by converting the input to base 1000 and converting each digit separately with `RomanNumeral`. Then we fold them up by inserting `(...)` from the left.

Unfortunately, Mathematica represents zeros as `N` so we need to get rid of those.
> 10 votes

# Answer
## JavaScript (ES6), 136 bytes

```
f=n=>n<4e3?"M1000CM900D500CD400C100XC90L50XL40X10IX9V5IV4I1".replace(/(\D+)(\d+)/g,(_,r,d)=>r.repeat(n/d,n%=d)):`(${f(n/1e3)})`+f(n%1e3)

```

For numbers under 4000, repeats each Roman "letter" as many times as possible, using the list of Roman "letters" and their decimal values. Otherwise recursively builds up the answer from the division and modulo with 1000. Fortunately `repeat` truncates so I don't have to do it myself.
> 9 votes

# Answer
## Common Lisp, 108

```
(defun p(n)(if(> n 0)(if(< n 4000)(format()"~@R"n)(format()"(~A)~@[~A~]"(p(floor n 1000))(p(mod n 1000))))))

```

## Ungolfed

```
(defun p(n)
  (if (> n 0)
      (if (< n 4000)

          ;; Built-in Roman formatter (between 1 and 3999)
          (format () "~@R" n)

          ;; Divide N by 1000, as 1000*Q + R.
          ;; First print (p Q) in parentheses (recursively)
          ;; Then, if it is not NIL, the remainder R.
          (format () "(~A)~@[~A~]"
                  (p (floor n 1000))
                  (p (mod n 1000))))))

```

## Tests

Two tests give different outputs than the ones from the question:

```
(loop for (in out) in '((1 "I")
                        (2 "II")
                        (3 "III")
                        (4 "IV")
                        (15 "XV")
                        (40 "XL")
                        (60 "LX")
                        (67 "LXVII")
                        (400 "CD")
                        (666 "DCLXVI")
                        (3000 "MMM")
                        (3999 "MMMCMXCIX")
                        (4000 "M(V)")
                        (4999 "M(V)CMXCIX")
                        (6000 "(VI)")
                        (6000000 "((VI))")
                        (6006000 "((VI)VI)")
                        (6666666666 "(((VI)DCLXVI)DCLXVI)DCLXVI"))
   for computed = (p in)
   unless (string= out computed)
   collect (list in out computed))

=> ((4000 "M(V)" "(IV)")
    (4999 "M(V)CMXCIX" "(IV)CMXCIX"))

```
> 5 votes

# Answer
# Ruby, ~~137~~ ~~134~~ ~~130~~ 129 bytes

Recursive function that returns the string. I'm trying to golf down the numeral encodings a bit more if possible, but I'm not sure how.

Whoops, it's practically a direct port of @Neil's ES6 answer now.

```
f=->x{(x<t=1e3)?"CM900D500CD400C100XC90L50XL40X10IX9V5IV4I1".gsub(/(\D+)(\d+)/){s=x/v=eval($2);x%=v;$1*s}:"(#{f[x/t]})#{f[x%t]}"}

```

Attempt This Online!
> 3 votes

# Answer
# Ruby, ~~185 161~~ 144 bytes

```
r=->i{i>(t=1e3)? "(#{r[i/t]})"+r[i%t]:(s=?I*i;"IVXXLCCDM".scan(/(.)(.)(.)/){|x,y,z|{x*5=>y,x*4=>x+y,y*2=>z,y+x+y=>x+z}.map{|x,y|s.gsub!x,y}};s)}

```

Over a year after the original post, I think I learned something about golfing.

Thank you Value Ink for your valuable comments.
> 2 votes

# Answer
# R, 134

```
m=1000;x=scan();while(x[1]>=m)x=c(floor(x[1]/m),x[1]%%m,x[-1]);cat(rep("(",length(x)),sep="");cat(as.character(as.roman(x)),sep=")")

```

It's pretty much not the best option, but I think the idea should go pretty similar to this.
> 2 votes

# Answer
## TCL 134 bytes

```
proc f r {
set map {M 1000+ CM 900+ D 500+ CD 400+ C 100+ XC 90+ L 50+ XL 40+ X 10+ IX 9+ V 5+ IV 4+ I 1+}
expr [string map $map $r]0}

```

Try it here: https://rextester.com/BJC92885
> 2 votes

# Answer
## Python, 188 ~~194~~

*-6 bytes from getting rid of some whitespace*

This challenge brought me back to when I was first learning to program...

```
def f(x,s=zip("M CM D CD C XC L XL X IX V IV I".split(),[1e3,900,500,400,100,90,50,40,10,9,5,4,1])):
 r=""if x<4e3else"("+f(x/1e3)+")";x%=1e3
 for a,b in s:
    while x>=b:r+=a;x-=b
 return r

```

It might not be the shortest solution, but I had fun golfing this problem.

Try it out!
> 1 votes

---
Tags: code-golf, arithmetic, roman-numerals
---


title: Area of a 2D convex hull

text:
# Question
Title: Area of a 2D convex hull
You are given an array/list/vector of pairs of integers representing cartesian coordinates \\$(x, y)\\$ of points on a 2D Euclidean plane; all coordinates are between \\$−10^4\\$ and \\$10^4\\$, duplicates are allowed. Find the area of the convex hull of those points, rounded to the nearest integer; an exact midpoint should be rounded to the closest even integer. You may use floating-point numbers in intermediate computations, but only if you can guarantee that the final result will be always correct. This is , so the shortest correct program wins.

The *convex hull* of a set of points \\$P\\$ is the smallest convex set that contains \\$P\\$. On the Euclidean plane, for any single point \\$(x,y)\\$, it is the point itself; for two distinct points, it is the line containing them, for three non-collinear points, it is the triangle that they form, and so forth.

A good visual explanation of what a convex hulls, is best described as imagining all points as nails in a wooden board, and then stretching a rubber band around them to enclose all the points:

Some test cases:

```
Input: [[50, -13]]
Result: 0

Input: [[-25, -26], [34, -27]]
Result: 0

Input: [[-6, -14], [-48, -45], [21, 25]]
Result: 400

Input: [[4, 30], [5, 37], [-18, 49], [-9, -2]]
Result: 562

Input: [[0, 16], [24, 18], [-43, 36], [39, -29], [3, -38]]
Result: 2978

Input: [[19, -19], [15, 5], [-16, -41], [6, -25], [-42, 1], [12, 19]]
Result: 2118

Input: [[-23, 13], [-13, 13], [-6, -7], [22, 41], [-26, 50], [12, -12], [-23, -7]]
Result: 2307

Input: [[31, -19], [-41, -41], [25, 34], [29, -1], [42, -42], [-34, 32], [19, 33], [40, 39]]
Result: 6037

Input: [[47, 1], [-22, 24], [36, 38], [-17, 4], [41, -3], [-13, 15], [-36, -40], [-13, 35], [-25, 22]]
Result: 3908

Input: [[29, -19], [18, 9], [30, -46], [15, 20], [24, -4], [5, 19], [-44, 4], [-20, -8], [-16, 34], [17, -36]]
Result: 2905

```

# Answer
> 9 votes
# SQL Server 2012+, 84 bytes

```
SELECT Round(Geometry::ConvexHullAggregate(Geometry::Point(x,y,0)).STArea(),0)FROM A

```

Makes use of the geometry functions and aggregates in SQL Server. Coordindates are from table `A` with columns `x` and `y`.

# Answer
> 9 votes
# Java 10, ~~405~~ ~~...didn't fit anymore; see edit history..~~ ~~317~~ 316 bytes

```
P->{int n=P.length,l=0,i=0,p,q,t[],h[][]=P.clone(),s=0;for(;++i<n;)l=P[i][0]<P[l][0]?i:l;p=l;do for(h[s++]=P[p],q=-~p%n,i=-1;++i<n;q=(t[1]-P[p][1])*(P[q][0]-t[0])<(t[0]-P[p][0])*(P[q][1]-t[1])?i:q)t=P[i];while((p=q)!=l);for(p=i=0;i<s;p-=(t[0]+h[++i%s][0])*(t[1]-h[i%s][1]))t=h[i];return Math.round(.5*p/~(p%=2))*~p;}

```

-52 bytes thanks to *@OlivierGrégoire*
-3 bytes thanks to *@PeterTaylor*
-7 bytes thanks to *@ceilingcat*

Try it online.

Or **299 bytes without rounding..**.

**Explanation:**

There are three steps to do:

1. Calculate the points for the Convex Hull based on the input-coordinates (using Jarvis' Algorithm/Wrapping)
2. Calculate the area of this Convex Hull
3. Banker's rounding..

To calculate the coordinates that are part of the Convex Hull, we use the following approach:

Set point \\$l\\$ and \\$p\\$ to the left-most coordinate. Then calculate the next point \\$p\\$ in a counterclockwise rotation; and continue doing so until we've reached back at the initial point \\$l\\$. Here a visual for this:

As for the code:

```
P->{                      // Method with 2D integer array as parameter & long return-type
  int n=P.length,         //  Integer `n`, the amount of points in the input
      l=0,                //  Integer `l`, to calculate the left-most point
      i=0,                //  Index-integer `i`
      p,                  //  Integer `p`, which will be every next counterclockwise point
      q,                  //  Temp integer `q`
      t[],                //  Temp integer-array/point
      h[][]=P.clone(),    //  Initialize an array of points `h` for the Convex Hull
      s=0;                //  And a size-integer for this Convex Hull array, starting at 0
  for(;++i<n;)            //  Loop `i` in the range [1, `n`):
    l=                    //   Change `l` to:
      P[i][0]<P[l][0]?    //   If i.x is smaller than l.x:
       i                  //    Replace `l` with the current `i`
      :l;                 //   Else: leave `l` unchanged
  p=l;                    //  Now set `p` to this left-most coordinate `l`
  do                      //  Do:
    for(h[s++]=P[p],      //   Add the `p`'th point to the 2D-array `h`
        q=-~p%n,          //   Set `q` to `(p+1)` modulo-`n`
        i=-1;++i<n;       //    Loop `i` in the range [0, `n`):
        ;q=               //      After every iteration: change `q` to:
                          //       We calculate: (i.y-p.y)*(q.x-i.x)-(i.x-p.x)*(q.y-i.y),
                          //       which results in 0 if the three points are collinear;
                          //       a positive value if they are clockwise;
                          //       or a negative value if they are counterclockwise
           (t[1]-P[p][1])*(P[q][0]-t[0])<(t[0]-P[p][0])*(P[q][1]-t[1])?
                          //       So if the three points are counterclockwise:
            i             //        Replace `q` with `i`
           :q)            //       Else: leave `q` unchanged
      t=P[i];             //     Set `t` to the `i`'th Point (to save bytes)
  while((p=q)             //  And after every while-iteration: replace `p` with `q`
             !=l);        //  Continue the do-while as long as `p` is not back at the
                          //  left-most point `l` yet
  // Now step 1 is complete, and we have our Convex Hull points in the List `h`

  for(p=i=0;              //  Set `p` (the area) to 0
      i<s                 //  Loop `i` in the range [0, `s`):
      ;p-=                //    After every iteration: Decrease the area `p` by:
        (t[0]+h[++i%s][0])//     i.x+(i+1).x
        *(t[1]-h[i%s][1]))//     Multiplied by i.y-(i+1).y
    t=h[i];               //   Set `t` to the `i`'th point (to save bytes)
 return Math.round(.5*p/~(p%=2))*~p;}
                          //  And return `p/2` rounded to integer with half-even

```

# Answer
> 7 votes
# Wolfram Language (Mathematica), 27 bytes

```
Round@*Area@*ConvexHullMesh

```

Try it online!

# Answer
> 6 votes
# JavaScript (ES6),  ~~191~~  189 bytes

Implements the Jarvis march (aka gift wrapping algorithm).

```
P=>(r=(g=p=>([X,Y]=P[p],Y*h-X*v)+(P.map(([x,y],i)=>q=(y-Y)*(P[q][0]-x)<(x-X)*(P[q][1]-y)?i:q,q=P[++p]?p:0,h=X,v=Y)|q?g(q):V*h-H*v))(v=h=0,([[H,V]]=P.sort(([x],[X])=>x-X)))/2)+(r%1&&r&1)/2|0

```

Try it online!

Or **170 bytes** without the cumbersome rounding scheme.

# Answer
> 4 votes
# , ~~85~~ ~~81~~ 78 bytes

```
function(i,h=chull(i),j=c(h,h[1]))round((i[h,1]+i[j[-1],1])%*%diff(-i[j,2])/2)

```

Try it online!

Takes input as a 2-column matrix - first for `x`, second for `y`. R's `round` actually uses banker's rounding method, so we are quite lucky here.

The code uses a built-in function to determine, which points form the convex hull, and then applies the standard formula \\$\sum\_{i}{(x\_{i-1}+x)\cdot(y\_{i-1}-y\_i)}/2\\$ to get the polygon surface area.

Thanks to Giuseppe for -3 bytes.

# Answer
> 3 votes
# \[R + sp package\], 55 bytes

```
function(x)round(sp::Polygon(x[chull(x),,drop=F])@area)

```

Try it at RDRR

A function which takes a n x 2 matrix and returns the rounded area. This uses the `sp` package. The `drop=F` is needed to handle the one co-ordinate case. RDRR used for demo since TIO lacks the `sp` package.

---
Tags: code-golf, number, geometry, integer
---


title: Slither Like a Snake

text:
# Question
Title: Slither Like a Snake
## The Idea

We've done matrix spirals before, and full rotations, and even diagonal rotations, but not, as far as I can find, *snake rotations*!

What is a snake rotation?

Imagine the rows of a matrix snaking back and forth, with dividers between them like the dividers of long queue:

```
    +--------------+
      1  2  3  4  5|
    +------------  |
    |10  9  8  7  6|
    |  +-----------+
    |11 12 13 14 15|
    +------------  |
     20 19 18 17 16|
    +--------------+

```

Now imagine rotating these items by 2. Each item advances, like people moving in a line, and the items at the end spill out and return to the beginning:

```
    +--------------+
-->  19 20  1  2  3|
    +------------  |
    | 8  7  6  5  4|
    |  +-----------+
    | 9 10 11 12 13|
    +------------  |
<--  18 17 16 15 14|
    +--------------+

```

If there are an odd number of rows it will exit from the right, but still wrap to the beginning. For example, here's a 3 rotation:

```
    +--------------+
      1  2  3  4  5|
    +------------  |
    |10  9  8  7  6|
    |  +-----------+
    |11 12 13 14 15
    +--------------+

    +--------------+
-->  13 14 15  1  2|
    +------------  |
    | 7  6  5  4  3|
    |  +-----------+
    | 8  9 10 11 12  -->
    +--------------+

```

A negative rotation will take you backwards. Here's a -2 rotation:

```
    +--------------+
<--   3  4  5  6  7|
    +------------  |
    |12 11 10  9  8|
    |  +-----------+
    |13 14 15  1  2  <--
    +--------------+

```

## The Challenge

Your function or program will take 2 inputs, in any convenient format:

* A matrix
* A integer (positive or negative) indicating how many places to rotate it.

It will return:

* The rotated matrix

Notes:

* Code golf. Fewest bytes wins.
* Matrixes need not be square, but will contain at least 2 rows and 2 columns
* Positive integers will rotate row 1 toward the right
* Negative integers will rotate row 1 toward the left
* You may reverse the meaning of positive / negative rotation numbers, if convenient
* The rotation number can be larger than the number of items. In that case, it will wrap. That is, it will be equivalent to the number modulo the number of items.
* The matrix will contain only integers, but it may contain any integers, including repeats

## Test Cases

Format:

* Matrix
* Rotation number
* Expected return value

---

```
4 5
6 7

1

6 4
7 5

```

---

```
2  3  4  5
6  7  8  9
10 11 12 13

-3

5  9  8  7
12 11 10 6
13 2  3  4

```

---

```
8 8 7 7
5 5 6 6

10

5 5 8 8
6 6 7 7

```

# Answer
> 7 votes
# Jelly, 10 bytes

```
UÐeẎṙṁ⁸UÐe

```

A dyadic Link accepting the marix on the left and the rotation integer on the right (uses the reverse meaning of positive / negative)

**Try it online!**

### How?

```
UÐeẎṙṁ⁸UÐe - Link: matrix of integers, M; integer, R
 Ðe        - apply to even indices of M:
U          -   reverse each
   Ẏ       - tighten
    ṙ      - rotate left by R
     ṁ     - mould like:
      ⁸    -   chain's left argument, M
        Ðe - apply to even indices:
       U   -   reverse each

```

# Answer
> 6 votes
# , ~~121~~ ~~110~~ 101 bytes

```
function(m,n,o=t(m)){o[,j]=o[i<-nrow(o):1,j<-c(F,T)];o[(seq(o)+n-1)%%sum(1|o)+1]=o;o[,j]=o[i,j];t(o)}

```

Try it online!

### Walkthrough

```
function(m,n) {           # Input: m - matrix, n - shift
  o <- t(m)               # Transpose the matrix, since R works in column-major order
                          # while our snake goes in row-major order
  i <- nrow(o):1          # Take row indices in reverse
  j <- c(F,T)             # Take even column indices (FALSE, TRUE, FALSE, TRUE, ...)
  o[,j] <- o[i,j]         # "Normalize" the matrix by reversing every second column
  o[(seq(o)+n-1) %%       # Perform the shift: add n-1 to indices,
    length(o)+1] <- o     # Modulo sequence length, and +1 again
  o[,j] <- o[i,j]         # Reverse even columns again to return to snake form
  t(o)                    # Transpose the matrix back to orginal shape and return
}

```

# Answer
> 4 votes
# Python 3.8 (pre-releasSSSse), 119 bytes

```
lambda m,r,n=-1:[[m[(k:=(j+(s:=r+i)//w)%h)][::n**k][s%w]for i in range(w:=len(m[0]))][::n**j]for j in range(h:=len(m))]

```

An unnamed function accepting `matrix, rotation` which yields the new matrix.
Uses the opposite rotation sign.

**Try it online!**

### How?

We set `n=-1` upfront to save on parentheses later and take the matrix as `m` and the rotation as `r`.

A new matrix is constructed with the same dimensions as `m` \- with a width of `w` (`w:=len(m[0])`) and a height of `h` (`h:=len(m)`).

Every other row of this matrix is reversed (`[::n**j]`).

The values are looked up by calculating their row and column in the original, `m` using the current elements row, `i`, and column, `j`...

We set `s` to `r+i` and `k` to `(j+s//w)%h`. `k` is the row of the original to access for our current element.

In order to easily access odd indexed rows from the right we reverse such rows before accessing their elements (with `[:n**k]`), this means the element of interest is at `s%w`.

# Answer
> 3 votes
# , ~~41~~ ~~30~~ 21 bytes

-11 bytes thanks to Jonah!

-9 bytes thanks to FrownyFrog & ngn !

```
$@]t@$(|.,@t=.|.@]/\)

```

Try it online!

Reversed `+/-`

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

Takes input as `(matrix)(integer)`. The meaning of the sign of the integer is inverted.

```
m=>n=>(g=m=>m.map(r=>r.sort(_=>~m,m=~m)))(m.map(r=>r.map(_=>a[(l+n++%l)%l]),l=(a=g(m).flat()).length))

```

Try it online!

### Helper function

The helper function \\$g\\$ is used to 'snakify' or 'unsnakify' a matrix by reversing rows at odd indices.

```
g = m =>        // m[] = input matrix
  m.map(r =>    // for each row r[] in m[]:
    r.sort(_ => //   sort r[]:
      ~m,       //     using either 0 (don't reverse) or -1 (reverse)
      m = ~m    //     and toggling m before each iteration
                //     (on the 1st iteration: m[] is coerced to 0, so it yields -1)
    )           //   end of sort()
  )             // end of map()

```

### Main function

```
m => n =>                    // m[] = matrix, n = integer
  g(                         // invoke g on the final result
    m.map(r =>               //   for each row r[] in m[]:
      r.map(_ =>             //     for each entry in r[]:
        a[(l + n++ % l) % l] //       get the rotated value from a[]; increment n
      ),                     //     end of inner map()
      l = (                  //     l is the length of a[]:
        a = g(m).flat()      //       a[] is the flatten result of g(m)
      ).length               //       (e.g. [[1,2],[3,4]] -> [[1,2],[4,3]] -> [1,2,4,3])
    )                        //   end of outer map()
  )                          // end of call to g

```

# Answer
> 2 votes
# Pyth, 20 bytes

```
L.e_W%k2bbyclQ.>syQE

```

Try it online here.

# Answer
> 2 votes
# Python 3, 94 bytes

```
lambda m,n:g(roll(g(m),n))
g=lambda b:[b[i][::(-1)**i]for i in r_[:len(b)]]
from numpy import*

```

Try it online!

Used the odd-row-reversal from Jonathan Allan's answer.

```
lambda m,n:g(roll(g(m),n))  #reverse odd rows, shift elements, then reverse odd rows again.
g=lambda b:[b[i][::(-1)**i] #reverse odd rows
    for i in r_[:len(b)]]   #r_[:x] = range(x)
from numpy import*          #roll() and r_[]

```

# Answer
> 2 votes
# 05AB1E, 16 bytes

```
εNFR]˜²._¹gäεNFR

```

Try it online!

Thanks to Emigna for -5. Unfortunately, I can't see how to golf the redundant part out. :(

# Answer
> 1 votes
# Charcoal, 36 bytes

```
ＦＥθ⎇﹪κ²⮌ιιＦι⊞υκＩＥ⪪Ｅυ§υ⁻κηＬ§θ⁰⎇﹪κ²⮌ιι

```

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

```
Ｅθ⎇﹪κ²⮌ιι

```

Reverse alternate rows of the input.

```
Ｆ...Ｆι⊞υκ

```

Flatten the array.

```
Ｅυ§υ⁻κη

```

Rotate the flattened array.

```
⪪...Ｌ§θ⁰

```

Split the array back into rows.

```
Ｅ...⎇﹪κ²⮌ιι

```

Reverse alternate rows.

```
Ｉ...

```

Convert each entry to string and output in the default output format which is one number per line with rows double-spaced. (Formatting with a separator would cost the length of the separator.)

# Answer
> 1 votes
# C# (Visual C# Interactive Compiler), 141 bytes

```
a=>n=>{for(dynamic l=a.Length,w=a.GetLength(1),i=l,j,b=a.Clone();i-->0;)a[(j=(i+n%l+l)%l)/w,j/w%2<1?j%w:w-j%w-1]=b[i/w,i/w%2<1?i%w:w-i%w-1];}

```

Try it online!

-5 bytes total thanks to @someone!

Anonymous function that performs an in-place modification to the input matrix.

An single loop iterates over the cells. You can scan from top to bottom and left to right using the following formulas:

* `row=i/w`
* `col=i%w`

Where `i` is a loop counter and `w` is the number of columns. This is varies slightly when scanning in a snake pattern.

* `row=i/w`
* `col=i%w` (0th, 2nd, 4th, etc. row)
* `col=w-i%w-1` (1st, 3nd, 5th, etc. row)

Another thing to note is that the `%` in C# does not convert to a positive value like it does in some other languages. A couple extra bytes are needed to account for this.

```
// a: input matrix
// n: number of cells to rotate
a=>n=>{
  for(
    // l: total number of cells
    // w: number of columns
    // i: loop index
    // j: offset index
    // b: copy of input matrix
    dynamic
      l=a.Length,
      w=a.GetLength(1),
      i=l,j,
      b=a.Clone();
    // iterate from i down to 0
    i-->0;
  )
    // calculate the offset `j` and use
    // the above formulas to index
    // into `a` for setting a value
    a[
      (j=(i+n%l+l)%l)/w,
      j/w%2<1?j%w:w-j%w-1
    ]=
    // use the un-offset index `i` and
    // the above formulas to read a
    // value from the input matrix
    b[
      i/w,
      i/w%2<1?i%w:w-i%w-1
    ];
}

```

# Answer
> 1 votes
# Japt, 28 bytes

```
mÏ%2©XÔªX
c éV òUÎl
W©UªßV1V

```

Try it

Port of Arnauld's answer. The biggest challenge was creating a reusable function. In particular, there is a helper function to reverse every other row. The approach that I am taking is to make a recursive call and depending on whether a variable is set.

Transpiled JS:

```
// U: first input argument (matrix)
// m: map it through a function
U = U.m(function(X, Y, Z) {
  // if the row index is even, don't alter it
  // if the row index is odd, reverse it (w)
  return Y % 2 && X.w() || X
});
V = U
  // flatten the matrix
  .c()
  // shift by the amount specified in second argument
  .é(V)
  // partition back to matrix
  .ò(
    // the number of columns should be the same as input
    U.g().l()
  );
// if W is specified, return the result from the first line
W && U ||
  // otherwise, make a recursive call with the shifted matrix
  rp(V, 1, V)

```

# Answer
> 1 votes
# APL (Dyalog Classic), 20 bytes

```
↑∘t⊢∘⍴⍴⌽∘∊∘(t←⊢∘⌽\↓)

```

Try it online!

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


title: Letter Boxed validator

text:
# Question
Title: Letter Boxed validator
The New York Times has a daily online game called Letter Boxed (the link is behind a paywall; the game is also described here), presented on a square as follows:

You are given 4 groups of 3 letters (each group corresponds to one side on the picture); no letter appears twice. The aim of the game is to find words made of those 12 letters (and those letters only) such that:

* Each word is at least 3 letters long;
* Consecutive letters cannot be from the same side;
* The last letter of a word becomes the first letter of the next word;
* All letters are used at least once (letters can be reused).

In this challenge, you are given the letters and a list of words. The goal is to check whether the list of words is a valid Letter Boxed solution.

## Input

Input consists of (1) 4 groups of 3 letters and (2) a list of words. It can be in any suitable format.

## Output

A truthy value if the list of words is a valid solution to the Letter Boxed challenge for those 4×3 letters, and a falsey value otherwise.

## Test cases

Groups of letters=`{{I,C,O}, {M,R,E}, {G,N,S}, {A,P,L}}`.

### Truthy values

* PILGRIMAGE, ENCLOSE
* CROPS, SAIL, LEAN, NOPE, ENIGMA

### Falsey values

* PILGRIMAGE, ECONOMIES (can't have CO since they are on the same side)
* CROPS, SAIL, LEAN, NOPE (G and M have not been used)
* PILGRIMAGE, ENCLOSURE (U is not one of the 12 letters)
* ENCLOSE, PILGRIMAGE (last letter of 1st word is not first letter of 2nd word)
* SCAMS, SO, ORGANISE, ELOPE (all words must be at least 3 letters long).

Note that in this challenge, we do not care whether the words are valid (part of a dictionary).

## Scoring:

This , lowest score in bytes wins!

# Answer
# 05AB1E, ~~37~~ ~~35~~ ~~33~~ ~~32~~ ~~31~~ ~~29~~ 28 bytes

```
εk3÷üÊ}DO2@¹ü«εüQO}²{¹˜êQ)˜P

```

-2 bytes by taking inspiration of the `ê` approach *@Emigna* used in his 05AB1E answer.
-3 bytes thanks to *@Grimy*.

Takes a list of list of characters for the words as first input, and the flattened list of twelve letters as second input.

Try it online or verify all test cases.

**Explanation:**

```
ε         # Map over the character-lists `y` of the (implicit) input-list of words:
 k        #  Get the index of each character in the (implicit) input-list of letters
  3÷      #  Integer-divide each index by 3
    üÊ    #  Check for each overlapping pair of integers that they are NOT equal
}D        # After the map: duplicate the resulting list
  O       #  Get the sum of each inner list of truthy/falsey values
   2@     #  And check that each is larger than 2 (so all words had at least 3 letters)
¹ü        # Get all overlapping pairs of character-lists from the input-list of words:
  «       #  And merge them together to a flattened list of characters
   ε   }  # Map over those merged character lists:
    üQ    #  Check for each overlapping pair of characters in the list that they are equal
      O   #  And take the sum of this (where we'd expect 1/truthy if the last character of
          #  the first word and the first character of the second word are equal)
          #  (NOTE: This could fail for inputs with identical adjacent characters,
          #   but the earlier check of `εk3÷üÊ}` already covers for this)
²{        # Push the input-list of letters, and sort them
  ¹˜      # Push the input-list of list of word-letters, flattened,
    ê     # and then uniquified and sorted as well
     Q    # And check if both lists of characters are the same
)˜        # Then wrap everything on the stack into a list, and deep flatten it
  P       # And check if everything is truthy by taking the product
          # (which is output implicitly as result)

```
> 6 votes

# Answer
# JavaScript (ES6),  ~~130~~  126 bytes

Takes input as `(letters)(words)`. Returns \\$0\\$ or \\$1\\$.

```
L=>W=>L.every(a=>a.every(x=>(W+'').match(x,a.map(y=>s+='|'+x+y))),p=s=1)&W.every(w=>w[2]&&p|w[0]==p&!w.match(s,p=w.slice(-1)))

```

Try it online!

### Step 1

We first iterate over \\$L\\$ to build a pipe-separated string \\$s\\$ consisting of all invalid pairs of letters. While doing so, we also make sure that each letter appears at least once in some word.

```
L.every(a =>              // for each group of letter a[] in L[]:
  a.every(x =>            //   for each letter x in a[]:
    (W + '')              //     coerce W[] to a string
    .match(               //     and test whether ...
      x,                  //       ... x can be found in it
      a.map(y =>          //       for each letter y in a[]:
        s += '|' + x + y  //         append '|' + x + y to s
      )                   //       end of map()
    )                     //     end of match()
  ),                      //   end of inner every()
  p = s = 1               //   start with p = s = 1
)                         // end of outer every()

```

### Step 2

We now iterate over \\$W\\$ to test each word.

```
W.every(w =>              // for each word w in W[]:
  w[2] &&                 //   is this word at least 3 characters long?
  p |                     //   is it the first word? (p = 1)
  w[0] == p &             //   or does it start with the last letter of the previous word?
  !w.match(               //   and finally make sure that ...
    s,                    //     ... it doesn't contain any invalid pair of letters
    p = w.slice(-1)       //     and update p to the last letter of w
  )                       //   end of match()
)                         // end of every()

```
> 6 votes

# Answer
# Jelly, ~~30~~ 29 bytes

```
FQṢ=Ṣ},i@€€’:3Iʋ,Ẉ>2ɗ,U=ḢɗƝ{Ȧ

```

Try it online!

A dyadic link that takes the list of words as left argument and the flattened list of letters in the box as the right argument. It returns `1` for true and `0` for false.

### Explanation

```
F                               | Flatten the word list
 Q                              | Unique
  Ṣ                             | Sort
   =                            | Is equal to
    Ṣ}                          |   The sorted letterbox letters
      ,        ʋ                | Pair this with the following:
       i@€€                     |   The index of each letter of each word in the letterbox
           ’                    |   Decrease by 1
            :3                  |   Integer divide by 3
              I                 |   Differences between consecutive ones (will be zero if any two consecutive letters in a word from same side of box)
                ,   ɗ           | Pair everything so far with the following:
                 Ẉ>2            |   Whether length of each input word is greater than 2
                     ,   ɗƝ{    | Pair everything so far with the following, applied to each neighbouring pair of the input word list
                      U         |   Upend (reverse) first word
                       =        | Compare characters to second
                        Ḣ       |   Take first (i.e. last character of first word equals first character of second)
                            Ȧ   | Flatten all of the above and check there are no false values

```
> 6 votes

# Answer
# 05AB1E, 42 bytes

```
εg2›}P¹εεUIεXå}ƶO}üÊP}P¹ü‚ε`нsθQ}P¹Jê²JêQP

```

Try it online!
> 5 votes

# Answer
# Python 2, 171 bytes

```
lambda l,w:(set(sum(l,[]))==set(''.join(w)))*all(a[-1]==b[0]for a,b in zip(w,w[1:]))*all((a in g)+(b in g)<2for x in w for a,b in zip(x,x[1:])for g in l)*min(map(len,w))>2

```

Try it online!
> 4 votes

# Answer
# Jelly, 34 bytes

```
Ṫ=¥/ƝḢ€Ạȧ⁸Fe€ⱮZḄ;IẠƊȧF}fƑF{
ẈṂ>2ȧç

```

A dyadic Link accepting the words on the left and the letter groups on the right which yields `1` if valid and `0` if not.

**Try it online!** Or see the test-suite.
> 4 votes

# Answer
# Haskell, 231 bytes

```
import Data.List
l&w=all((>2).length)w&&c w&&all(l!)w&&(h l)%(h w)
h=concat
l%w=null[x|x<-l,x`notElem`w]
l!(a:b:c)=a#l?(b#l)&&l!(b:c)
l!_=1>0
Just a?Just b=a/=b
_?_=1<0
c#l=findIndex(elem c)l
c(a:b:t)=last a==head b&&c(b:t)
c _=1>0

```

Try it online!

Not the best score. Some Haskell guru will probably be able to get this under 100 bytes.

### Usage

```
["ICO","MRE","GNS","APL"]&["CROPS", "SAIL", "LEAN", "NOPE", "ENIGMA"]

```

### Explanation

```
import Data.List
l&w = all((>2).length)w &&      -- Every word has length > 2
      c w &&                    -- Every word ends with the same letter as the next one starts with
      all(l!)w &&               -- For every word: Consecutive letters are on different sides (and must exist on a side)
      (h l)%(h w)               -- All letters are used

h=concat                        -- Just a shorthand

l%w=null[x|x<-l,x`notElem`w]    -- The letters of l, with all letters of w removed, is empty

l!(a:b:c)=a#l?(b#l)&&l!(b:c)    -- Sides of the first two letters are different, recurse from second letter
l!_=1>0                         -- Until fewer than 2 letters remain

Just a?Just b=a/=b              -- Both sides must be different
_?_=1<0                         -- And must exist

c#l=findIndex(elem c)l          -- Find the side of letter c

c(a:b:t)=last a==head b&&c(b:t) -- Last letter of the first word must be same as first letter of second word, recurse starting from second word
c _=1>0                         -- Until there are fewer than 2 words

```
> 4 votes

# Answer
# Haskell, 231 bytes

A different Haskell variation, exactly the same size as @Paul Mutser's :)

```
import Data.List
f x=filter(\a->length a>1)$concatMap subsequences x
g=nub.concat.f
p l(x:y)=foldl(\(m,n)c->(c,n&&length c>2&&(not$any(`isInfixOf`c)(f l))&&last m==head c))(x,True)y
z l w=null(g l\\g w)&&null(g w\\g l)&&(snd$p l w)

```

Try it online!

### Ungolfed

```
-- generate all invalid substrings
f :: [String] -> [String]
f xs = filter (\x -> length x > 1) $ concatMap subsequences xs

-- utility function to flatten and remove duplicates
g :: [String] -> String
g  = nub $ concat $ f

-- verify that all conditions are satisfied along the list
p :: [String] -> [String] -> (String, Bool)
p l (x:xs) = foldl (\(m,n) c -> (c , n && length c > 2 && (not $ any (`isInfixOf` c)(f l)) && last m == head c)) (x, True) xs

-- put all the pieces together and consume input
z :: [String] -> [String] -> Bool
z l w = null (g l \\ g w) && null (g w \\ g l) && (snd $ p l w)

```
> 4 votes

# Answer
# Java (JDK), 188 bytes

```
g->w->{var v=0<1;int x=0,l,i=0,j,p,z,y=w[0][0];for(;i<w.length;i++)for(l=w[i].length,v&=y==w[i][0]&l>2,j=0,p=-9;j<l;v&=z>=0&z/3!=p/3,x|=2<<(p=z))z=g.indexOf(y=w[i][j++]);return v&x==8190;}

```

Try it online!

## Explanations

```
g->w->{     // Lambda accepting letter groups as a string and a list of words, in the form of an array of char arrays.
 var v=0<1;     // Validity variable
 int x=0,       // The letter coverage (rule 4)
     l,         // The length of w[i]
     i=0,       // The w iterator
     j,         // The w[i] iterator
     p,         // The previous group
     z,         // The current group
     y=w[0][0]; // The previous character
 for(;i<w.length;i++) // For each word...
  for(
     l=w[i].length,     // make a shortcut for the length
     v&=y==w[i][0]&l>2, // check if the last character of the previous word is the same as the first of the current.
                        // Also, check if the length is at least 3
     j=0,               // Reset the iteration
     p=-9               // Set p to an impossible value.
    ;
     j<l                //
    ;
     v&=z>=0&z/3!=p/3,  // Check that each letter of the word is in the letter pool,
                        //  and that the current letter group isn't the same as the previous one.
     x|=2<<(p=z)      // After the checks, assign z to p,
                        //  and mark the letter of the pool as used.
   )
   z=g.indexOf(y=w[i][j++]); // Assign the current letter to y so that it contains the last at the end of the loop.
                             //  and fetch the position of the letter in the pool.
 return v&x==8190; // Return true if all matched
                   //  and if the rule 4 is enforced.
}

```

## Credits

* -2 bytes thanks to ceilingcat
> 3 votes

# Answer
# Ruby, 126 bytes

```
->l,w{(/(_|^)..(_|$)/!~s=w*?_)&&!!s.chars.uniq[12]&&/__|^_|_$|(_.*)\1/!~s.gsub(/(.)_\1/,'\1').chars.map{|x|l.grep(/#{x}/)}*?_}

```

Try it online!
> 3 votes

# Answer
# Charcoal, 63 bytes

```
⌊⁺⁺⁺⭆η›Ｌι²⭆⪫ηω№⪫θωι⭆⪫θω№⪫ηωι⭆η⭆ι⎇μ¬⁼Φθ№νλΦθ№ν§ι⊖μ∨¬κ⁼§ι⁰§§η⊖κ±¹

```

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

```
⌊⁺⁺⁺

```

Concatenate the below expressions and output `0` if any of them includes a `0` otherwise `1`.

```
⭆η›Ｌι²

```

For each word in the solution output whether its length is at least 3.

```
⭆⪫ηω№⪫θωι

```

For each letter in the solution output whether it appears in the puzzle.

```
⭆⪫θω№⪫ηωι

```

For each letter in the puzzle output whether it appears in the solution.

```
⭆η⭆ι⎇μ¬⁼Φθ№νλΦθ№ν§ι⊖μ∨¬κ⁼§ι⁰§§η⊖κ±¹

```

For each letter in the solution check that the previous letter is not in the same group, unless it is the first letter of a word, in which case check that it is equal to the last letter of the previous word, unless it is the first letter of the solution, in which case just ignore it.
> 2 votes

# Answer
# Python 2, ~~168~~ 156 bytes

```
lambda l,w,J=''.join:(set(J(w))==set(J(l)))*all((v<1or u[-1]==v[0])*u[2:]*(2>(x in p)+(y in p))for u,v in zip(w,w[1:]+[0])for x,y in zip(u,u[1:])for p in l)

```

Try it online!

Returns `1` for truthy, `0` for falsey.
> 0 votes

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


title: Can a neural network recognize primes?

text:
# Question
Title: Can a neural network recognize primes?
# Background

Recognizing primality seems like a poor fit for (artificial) neural networks. However, the universal approximation theorem states that neural networks can approximate any continuous function, so in particular it should be possible to represent any finitely-supported function one desires. So let's try to recognize all the primes among the first million numbers.

More precisely, because this is a programming website, let's go up to 2^20 = 1,048,576. The number of primes below this threshold is 82,025 or roughly 8%.

# Challenge

**How small of a neural network can you find that correctly classifies all 20-bit integers as prime or not prime?**

For the purposes of this challenge, the size of a neural network is the total number of weights and biases required to represent it.

# Details

The goal is to *minimize* the size of a single, explicit neural network.

The input to your network will be a vector of length 20 containing the individual bits of an integer, represented either with 0s and 1s or alternatively with -1s and +1s. The ordering of these can be most-significant-bit first or least-significant-bit first.

The output of your network should be a single number, such that above some cutoff the input is recognized as prime and below the same cutoff the input is recognized as not prime. For example, positive might mean prime (and negative not prime), or alternatively greater than 0.5 might mean prime (and less than 0.5 not prime).

The network must be 100% accurate on all 2^20 = 1,048,576 possible inputs. As mentioned above, note that there are 82,025 primes in this range. (It follows that always outputting "not prime" would be 92% accurate.)

In terms of standard neural network terminology, this would likely be called *overfitting*. In other words, your goal is to perfectly overfit the primes. Other words one might use are that the "training set" and the "test set" are the same.

This challenge does not consider the number of "trainable" or "learnable" parameters. Indeed, your network is likely to contain hard-coded weights, and the example below is entirely hard-coded. Instead, *all* weights and biases are considered parameters and are counted.

The length of the code necessary to train or generate your neural network is not relevant to your score, but posting the relevant code is certainly appreciated.

# Baseline

As a baseline, it is possible to "memorize" all 82,025 primes with **1,804,551** total weights and biases.

Note that this code that follows includes many things: a working example, working test code, a working definition of neural network using a known neural network library, a "hard-coded" (or at least, not "trained") neural network, and a working measurement of score.

```
import numpy as np

bits = 20

from keras.models import Sequential
from keras.layers import Dense

from sympy import isprime

# Hardcode some weights
weights = []
biases  = []
for n in xrange(1<<bits):
    if not isprime(n):
        continue
    bit_list = [(n / (1 << i))%2 for i in xrange(bits)]
    weight = [2*bit - 1 for bit in bit_list]
    bias   = - (sum(bit_list) - 1)
    weights.append(weight)
    biases .append(bias)
nprimes = len(biases)
weights1 = np.transpose(np.array(weights))
biases1  = np.array(biases )
weights2 = np.full( (nprimes,1), 1 )
biases2  = np.array( [0] )

model = Sequential()
model.add(Dense(units=nprimes, activation='relu', input_dim=bits, weights=[weights1, biases1]))
model.add(Dense(units=1, activation='relu', weights=[weights2, biases2]))
print "Total weights and biases: {}".format( np.size(weights1) + np.size(weights2) + np.size(biases1) + np.size(biases2) )

# Evaluate performance
x = []
y = []
for n in xrange(1<<bits):
    row = [(n / (1 << i))%2 for i in xrange(bits)]
    x.append( row )
    col = 0
    if isprime(n):
        col = 1
    y.append( col )
x = np.array(x)
y = np.array(y)

model.compile(loss='binary_crossentropy', optimizer='sgd', metrics=['accuracy'])

loss, accuracy = model.evaluate(x, y, batch_size=256)
if accuracy == 1.0:
    print "Perfect fit."
else:
    print "Made at least one mistake."

```

# What is a neural network?

For the purposes of this challenge, we can write down a narrow but precise definition of an (artificial) neural network. For some external reading, I suggest Wikipedia on artificial neural network, feedforward neural network, multilayer perceptron, and activation function.

A *feedforward neural network* is a collection of *layers* of neurons. The number of neurons per layer varies, with 20 neurons in the input layer, some number of neurons in one or more hidden layers, and 1 neuron in the output layer. (There must be at least one hidden layer because primes and not-primes are not linearly separable according to their bit patterns.) In the baseline example above, the sizes of the layers are \[20, 82025, 1\].

The values of the input neurons are determined by the input. As described above, this will either be 0s and 1s corresponding to the bits of a number between 0 and 2^20, or -1s and +1s similarly.

The values of the neurons of each following layer, including the output layer, are determined from the layer beforehand. First a linear function is applied, in a *fully-connected* or *dense* fashion. One method of representing such a function is using a *weights* matrix. For example, the transitions between the first two layers of the baseline can be represented with a 82025 x 20 matrix. The number of weights is the number of entries in this matrix, eg 1640500. Then each entry has a (separate) bias term added. This can be represented by a vector, eg a 82025 x 1 matrix in our case. The number of biases is the number of entries, eg 82025. (Note that the weights and biases together describe an *affine linear function*.)

A weight or bias is counted even if it is zero. For the purposes of this narrow definition, biases count as weights even if they are all zero. Note that in the baseline example, only two distinct weights (+1 and -1) are used (and only slightly more distinct biases); nonetheless, the size is more than a million, because the repetition does not help with the score in any way.

Finally, a nonlinear function called the *activation function* is applied entry-wise to the result of this affine linear function. For the purposes of this narrow definition, the allowed activation functions are ReLU, tanh, and sigmoid. The entire layer must use the same activation function.

In the baseline example, the number of weights is 20 * 82025 + 82025 * 1 = 1722525 and the number of biases is 82025 + 1 = 82026, for a total score of 1722525 + 82026 = 1804551. As a symbolic example, if there were one more layer and the layer sizes were instead \[20, a, b, 1\], then the number of weights would be 20 * a + a * b + b * 1 and the number of biases would be a + b + 1.

This definition of neural network is well-supported by many frameworks, including Keras, scikit-learn, and Tensorflow. Keras is used in the baseline example above, with code essentially as follows:

```
from keras.models import Sequential
model = Sequential()
from keras.layers import Dense
model.add(Dense(units=82025, activation='relu', input_dim=20, weights=[weights1, biases1]))
model.add(Dense(units=1, activation='relu', weights=[weights2, biases2]))
score = numpy.size(weights1) + numpy.size(biases1) + numpy.size(weights2) + numpy.size(biases2)

```

If the weights and bias matrices are numpy arrays, then numpy.size will directly tell you the number of entries.

# Are there other kinds of neural networks?

If you want a single, precise definition of neural network and score for the purposes of this challenge, then please use the definition in the previous section. If you think that "any function" looked at the right way is a neural network *with no parameters*, then please use the definition in the previous section.

If you are a more free spirit, then I encourage you to explore further. Perhaps your answer will not count toward the *narrow* challenge, but maybe you'll have more fun. Some other ideas you may try include more exotic activation functions, recurrent neural networks (reading one bit at a time), convolutional neural networks, more exotic architectures, softmax, and LSTMs (!). You may use any standard activation function and any standard architecture. A liberal definition of "standard" neural network features could include anything posted on the arxiv prior to the posting of this question.

# Answer
## Trial division: score 59407, 6243 layers, 16478 neurons in total

Given as a Python program which generates and validates the net. See the comments in `trial_division` for an explanation of how it works. The validation is quite slow (as in, running time measured in hours): I recommend using PyPy or Cython.

All layers use ReLU (\\$\alpha \to \max(0, \alpha)\\$) as the activation function.

The threshold is 1: anything above that is prime, anything below is composite or zero, and the only input which gives an output of 1 is 1 itself.

```
#!/usr/bin/python3

import math

def primes_to(n):
    ps = []
    for i in range(2, n):
        is_composite = False
        for p in ps:
            if i % p == 0:
                is_composite = True
                break
            if p * p > i:
                break
        if not is_composite:
            ps.append(i)
    return ps

def eval_net(net, inputs):
    for layer in net:
        inputs.append(1)
        n = len(inputs)
        inputs = [max(0, sum(inputs[i] * neuron[i] for i in range(n))) for neuron in layer]
    return inputs

def cost(net):
    return sum(len(layer) * len(layer[0]) for layer in net)

def trial_division(num_bits):
    # Overview: we convert the bits to a single number x and perform trial division.
    # x is also our "is prime" flag: whenever we prove that x is composite, we clear it to 0
    # At the end x will be non-zero only if it's a unit or a prime, and greater than 1 only if it's a prime.
    # We calculate x % p as
    #     rem = x - (x >= (p << a) ? 1 : 0) * (p << a)
    #     rem -= (rem >= (p << (a-1)) ? 1) : 0) * (p << (a-1))
    #     ...
    #     rem -= (rem >= p ? 1 : 0) * p
    #
    # If x % p == 0 and x > p then x is a composite multiple of p and we want to set it to 0

    N = 1 << num_bits
    primes = primes_to(1 + int(2.0 ** (num_bits / 2)))

    # As a micro-optimisation we exploit 2 == -1 (mod 3) to skip a number of shifts for p=3.
    # We need to bias by a multiple of 3 which is at least num_bits // 2 so that we don't get a negative intermediate value.
    bias3 = num_bits // 2
    bias3 += (3 - (bias3 % 3)) % 3

    # inputs: [bit0, ..., bit19]
    yield [[1 << i for i in range(num_bits)] + [0],
           [-1] + [0] * (num_bits - 1) + [1],
           [0] * 2 + [-1] * (num_bits - 2) + [1],
           [(-1) ** i for i in range(num_bits)] + [bias3]]

    for p in primes[1:]:
        # As a keyhole optimisation we overlap the cases slightly.
        if p == 3:
            # [x, x_is_even, x_lt_4, x_reduced_mod_3]
            max_shift = int(math.log((bias3 + (num_bits + 1) // 2) // p, 2))
            yield [[1, 0, 0, 0, 0], [0, 1, -1, 0, 0], [0, 0, 0, 1, 0], [0, 0, 0, -1, p << max_shift]]
            yield [[1, -N, 0, 0, 0], [0, 0, 1, 0, 0], [0, 0, 0, -1, 1]]
            yield [[1, 0, 0, 0], [0, 1, -p << max_shift, 0]]
        else:
            # [x, x % old_p]
            max_shift = int(num_bits - math.log(p, 2))
            yield [[1, 0, 0], [1, -N, -p_old], [-1, 0, p << max_shift]]
            yield [[1, -N, 0, 0], [0, 0, -1, 1]]
            yield [[1, 0, 0], [1, -p << max_shift, 0]]

        for shift in range(max_shift - 1, -1, -1):
            # [x, rem]
            yield [[1, 0, 0], [0, 1, 0], [0, -1, p << shift]]
            yield [[1, 0, 0, 0], [0, 1, 0, 0], [0, 0, -1, 1]]
            yield [[1, 0, 0, 0], [0, 1, -p << shift, 0]]
        # [x, x % p]
        p_old = p

    yield [[1, 0, 0], [1, -N, -p]]
    yield [[1, -N, 0]]

def validate_primality_tester(primality_tester, threshold):
    num_bits = len(primality_tester[0][0]) - 1
    primes = set(primes_to(1 << num_bits))
    errors = 0
    for i in range(1 << num_bits):
        expected = i in primes
        observed = eval_net(primality_tester, [(i >> shift) & 1 for shift in range(num_bits)])[-1] > threshold
        if expected != observed:
            errors += 1
            print("Failed test case", i)
        if (i & 0xff) == 0:
            print("Progress", i)

    if errors > 0:
        raise Exception("Failed " + str(errors) + " test case(s)")

if __name__ == "__main__":
    n = 20

    trial_div = list(trial_division(n))
    print("Cost", cost(trial_div))
    validate_primality_tester(trial_div, 1)

```

---

As an aside, re

> the universal approximation theorem states that neural networks can approximate any continuous function

it's easy to show that a neural network using ReLU is Turing complete. The easiest logic gate to implement robustly is NOR: an n-input NOR gate is \\$\max\left(0, 1 - \sum a\_i\right)\\$. I say *robustly* because this gate accepts inputs greater than 1 but (provided the inputs are not between 0 and 1) only ever outputs 0 or 1. A single-layer AND gate is \\$\max\left(0, 1 + \sum(a\_i - 1)\right)\\$ but only works correctly if its inputs are guaranteed to be 0 or 1, and may output larger integers. Various other gates are possible in one layer, but NOR by itself is Turing-complete so there's no need to go into detail.
> 14 votes

# Answer
## Score 984314, 82027 layers, 246076 neurons in total

We can keep things entirely in the integers if we use activation function ReLU, which simplifies the analysis.

Given an input \\$x\\$ which is known to be an integer, we can test whether \\$x = a\\$ with two layers and three neurons:

1. First layer: outputs \\$\textrm{ge}\_a = (x - a)^+\\$ and \\$\textrm{le}\_a = (-x + a)^+\\$
2. Second layer: outputs \\$\textrm{eq}\_a = (-\textrm{ge}\_a - \textrm{le}\_a + 1)^+\\$. \\$\textrm{eq}\_{a}\\$ will be \\$1\\$ if \\$x = a\\$ and \\$0\\$ otherwise.

---

Layer 1: reduce the 20 inputs to one value \\$x\\$ with weights 1, 2, 4, ... and bias 0. Cost: (20 + 1) * 1 = 21.

Layer 2: outputs \\$\textrm{ge}\_2 = (x - 2)^+\\$, \\$\textrm{le}\_2 = (-x + 2)^+\\$. Cost (1 + 1) * 2 = 4.

Layer 3: outputs \\$\textrm{accum}\_2 = (-\textrm{ge}\_2 - \textrm{le}\_2 + 1)^+\\$, \\$\textrm{ge}\_3 = (\textrm{ge}\_2 - (3-2))^+\\$, \\$\textrm{le}\_3 = (-\textrm{ge}\_2 + (3-2))^+\\$. Cost (2 + 1) * 3 = 9.

Layer 4: outputs \\$\textrm{accum}\_3 = (2^{21} \textrm{accum}\_2 -\textrm{ge}\_3 - \textrm{le}\_3 + 1)^+\\$, \\$\textrm{ge}\_5 = (\textrm{ge}\_3 - (5-3))^+\\$, \\$\textrm{le}\_5 = (-\textrm{ge}\_3 + (5-3))^+\\$. Cost (3 + 1) * 3 = 12.

Layer 5: outputs \\$\textrm{accum}\_5 = (2^{21} \textrm{accum}\_3 -\textrm{ge}\_5 - \textrm{le}\_5 + 1)^+\\$, \\$\textrm{ge}\_7 = (\textrm{ge}\_5 - (7-5))^+\\$, \\$\textrm{le}\_7 = (-\textrm{ge}\_5 + (7-5))^+\\$. Cost (3 + 1) * 3 = 12.

...

Layer 82026: outputs \\$\textrm{accum}\_{1048571} = (2^{21} \textrm{accum}\_{1048559} -\textrm{ge}\_{1048571} - \textrm{le}\_{1048571} + 1)^+\\$, \\$\textrm{ge}\_{1048573} = (\textrm{ge}\_{1048571} - ({1048573}-{1048571}))^+\\$, \\$\textrm{le}\_{1048573} = (-\textrm{ge}\_{1048571} + ({1048573}-{1048571}))^+\\$. Cost (3 + 1) * 3 = 12.

Layer 82027: outputs \\$\textrm{accum}\_{1048573} = (2^{21} \textrm{accum}\_{1048571} -\textrm{ge}\_{1048573} - \textrm{le}\_{1048573} + 1)^+\\$. Cost (3 + 1) * 1 = 4.

The threshold is 0. If working with doubles, overflow to \\$+\infty\\$ is quite possible, but that seems to be perfectly in accordance with the rules.

Score is (82026 - 3) * 12 + 21 + 4 + 9 + 4.
> 7 votes

---
Tags: code-challenge, primes, optimization, bitwise, neural-networks
---