# Question
Title: Does this JavaScript function support keyword arguments?
JavaScript has no direct support for keyword arguments, but it supports argument object destructuring. It is standard to use a destructed final argument for keyword arguments. Here is an example:

```
function f(x, { a = 7, b = 2}){
    return [x, a, b];
}

```

You would then call this function like:

```
f(9, {}); // ==> [9, 7, 2]
f(9, {a : 3}); // ==> [9, 3, 2]
f(9, {b : 3, a : 1}); // ==> [9, 1, 3]

```

The object may also supply a separate default if you omit the object entirely:

```
function g({ a = 7, b = 2} = {b : 3} ){
    return [a, b];
}
g() // => [7,3]
g({}) // => [7,2]

```

### Goal

Given an argument specification for a JavaScript function, determine whether it "supports key word arguments". The input must be a valid argument specification for a JavaScript function. It "supports key word arguments" if the last argument does object destructuring. See many examples below.

You may assume that no strings appear in the input (so no single quote `'` double quote `"` or uptick ```). You may also assume that the spread operator `...` does not appear.

(It would be nice to have the grammar for JavaScript argument specifications here but on a quick google I didn't find a readable reference. This section of the ECMAScript specification looks relevant, but I can't make sense of the grammar they provide. If anyone can suggest a readable link, I will add it.)

## Scoring

This is code golf, and the shortest code wins.

## Examples

```
"" // empty params ==> false
"x" // single normal argument ==> false
"x     " // test is space insensitive ==> false
"{x}" // ==> true
"x, y, z" // multiple normal arguments ==> false
"x, y, {z}" // ==>  true
"x, {y}, z" // ==> false
"x, {y}, {z}" // ==> true

"{}" // ==> true
"{} = {}" ==> true
"[] = {}" ==> false
"{} = []" ==> true
"[] = []" ==> false
"{} = null" ==> true

"[{x}]" // ==> false
"[x, y, z]" // ==> false
"x," // ==> false
"{x}," // ==> true

"x, { y = 2 }" // ==> true
"{ y = 2 }, x" // ==> false, not last argument
"{ x = 2 }, { y = 2 }" // ==> true

"{ a = 7, b = 2}" // ==> true, this is f above
"{ a = 7, b = 2} = {b : 3}" // ==> true this is g above
"{ a = [7, 1], b = { c : 2} } = {}" // ==> true
"{ a = 7, b = 2} = {}" // ==> true
"{ a = 7, b = 2} = null" // ==> true.

"{ x = { y : 2 }}" // ==> true

"x, [y, { z }]" // ==> false
"[x] = {[Symbol.iterator]: [][Symbol.iterator].bind([42])}" // ==> false
"x, y = function ({z}) {}" // ==> false
`x, y = ({z}) => {z}` // ==> false

```

Unspecified inputs:

```
","
"x y"
"x = '2, {y}' " // no syntax error but default is a string
...[x, y, { keyword },] // no syntax error but contains illegal ...
"{x"
"{{x}}"
"{[x]}"
"{1}"
"x,,"
"x, { x = 2 }"
"{ x = { y = 2 }}"
"{ x : 2 }"

```

Here are the tests as a JSON string:

```
"[[\"\",false],[\"x\",false],[\"x     \",false],[\"{x}\",true],[\"x, y, z\",false],[\"x, y, {z}\",true],[\"x, {y}, z\",false],[\"x, {y}, {z}\",true],[\"{}\",true],[\"{} = {}\",true],[\"[] = {}\",false],[\"{} = []\",true],[\"[] = []\",false],[\"{} = null\",true],[\"[{x}]\",false],[\"[x, y, z]\",false],[\"x,\",false],[\"{x},\",true],[\"x, { y = 2 }\",true],[\"{ y = 2 }, x\",false],[\"{ x = 2 }, { y = 2 }\",true],[\"{ a = 7, b = 2}\",true],[\"{ a = 7, b = 2} = {b : 3}\",true],[\"{ a = [7, 1], b = { c : 2} } = {}\",true],[\"{ a = 7, b = 2} = {}\",true],[\"{ a = 7, b = 2} = null\",true],[\"{ x = { y : 2 }}\",true], [\"x, [y, { z }]\", false], [\"[x] = {[Symbol.iterator]: [][Symbol.iterator].bind([42])}\", false], [\"x, y = function ({z}) {}\", false], [\"x, y = ({z}) => {z}\", false] ]"

```

## A reference implementation

Here is an ungolfed reference implementation in JavaScript (it uses nothing specific to JavaScript and could be easily ported to other languages).

```
function supportsKwargs (funcstr) {
    let START_ARG = 1;
    let ARG = 2;
    let paren_depth = 0;
    let arg_is_obj_dest = false;
    let state = START_ARG;
    for (let i = 0; i < funcstr.length; i++) {
      let x = funcstr[i];
      // Skip whitespace.
      if(x === " " || x === "\n" || x === "\t"){
        continue;
      }
      if(paren_depth === 0){
        if(x === ","){
          state = START_ARG;
          continue;
        }
      }
      if(state === START_ARG){
        // Nonwhitespace character in START_ARG so now we're in state arg.
        state = ARG;
        arg_is_obj_dest = x === "{";
      }
      switch(x){
        case "[": case "{": case "(":
          paren_depth ++;
          continue;
        case "]": case "}": case ")":
          paren_depth--;
          continue;
      }
    }
    return arg_is_obj_dest;
}

```

# Answer
# JavaScript (SpiderMonkey), 69 bytes

```
x=>Reflect.parse(`function f(${x}){}`).body[0].params.pop()?.type>'I'

```

Try it online!

Certainly you need right tools for this question...

SpiderMonkey on TIO is a bit old and won't work correctly for above code. You may download newest version of jsshell from https://archive.mozilla.org/pub/firefox/nightly/latest-mozilla-central/ .

It is strange that, using `function f(){}` instead of `()=>{}` in JavaScript may save bytes.
> 3 votes

# Answer
# 05AB1E, 44 bytes

```
…
    м©¼¬ˆε',Q¾*i®N>èˆ}…[{(yå½…]})yåi.¼]¯θ'{Q

```

Simply a port of the reference implementation.

Try it online or verify all test cases.

**Explanation:**

```
… \n\tм      # Remove all spaces, tabs, and newlines from the (implicit) input
©            # Store this new string in variable `®` (without popping)
¼            # Start the counter variable at 1 (it's 0 by default)
¬            # Get the first character of the string (without popping)
 ˆ           # And pop and add it to the global array
ε            # For-each `y` over the characters in the string:
 ',Q        '#  If the current character is a ","
    ¾*i      #  and the counter variable is still 1:
       ®     #   Push the string from variable `®`
        N>   #   Get the for-each index, and increment it by 1
          è  #   Index that into the string, to get the next character
           ˆ #   Pop and add that to the global array
      }      #  Close the if-statement
 …[{(yå      #  If the current character is in the string "[{(":
       ½     #   Increment the counter variable by 1
 …]})yåi     #  If the current character is in the string "]})":
        .¼   #   Decrement the counter variable by 1
]            # Close both the if-statement and for-each
 ¯           # Push the global array
  θ          # Only leave its last item
   '{Q      '# And check if this is equal to "{"
             # (after which the result is output implicitly)

```
> 3 votes

# Answer
# 05AB1E, ~~36~~ 35 bytes

Some parts are taken from Kevin Cruijsen's answer
-1 byte thanks to Kevin Cruijssen!

```
…
	мS©…[{(®å…]})®å-.¥_®',Q1š*Ïθ'{Q

```

Try it online!

**Commented**:

```
…\s\n\tм    # remove all whitespace from the input
        S   # split into a list of characters
         ©  # store this list in the register (without popping)
…[{(        # push string literal "[{("
    ®       # push the list from the register
     å      # for each character check if it is in the string "[{("
            # this is now a list with 1's at the indices of opening brackets
…]})        # push string literal "]})"
    ®       # push the list from the register
     å      # for each character check if it is in the string "]})"
            # this is now a list with 1's at the indices of closing brackets
-           # subtract element-wise
 .¥         # take the cumulative sum and prepend a 0
            # this a list of the parentheses depths
   _        # for each element: does it equal 0?
®           # push the list from the register
 ‛,Q        # for each element: does it equal ","?
    1š      # prepend a 1, this list is 1 at index N if N==0 or ®[N-1]==","
      *     # multiply element-wise with the previous list
Ï           # take the elements in the input where a 1 is in this list
 θ          # take the last element of this
  ‛{Q       # is this equal to "{"?

```
> 3 votes

# Answer
# JavaScript (ES6), 96 bytes

A minimal parser that expects a list of characters and returns `0` or `1`.

```
a=>a.map(c=>n=(i=",{}[]() ".indexOf(c))<7?~i?i?(o|=n/(d+=i&1||-1)/i)&0:!d:n?o=0:0:n,n=1,d=o=0)|o

```

Try it online!

### Commented

Variables:

* `d` is the current depth (0 = root)
* `n` is a flag telling whether we're at the beginning of a new block at the root level
* `o` is a flag telling whether the last block is an object

Source:

```
a =>                     // a[] = array of characters
a.map(c =>               // for each character c in a[]:
  n =                    //   update n:
    ( i = ",{}[]() "     //     i = index of c in this string
          .indexOf(c)    //
    ) < 7 ?              //     if c is not a space:
      ~i ?               //       if c is one of the characters defined above:
        i ?              //         if c is not a comma:
          ( o |=         //           set the flag o if:
            n /          //             n = 1
            ( d += i & 1 //             and the updated depth is 1
                   || -1 //             (incremented if i is odd, decremented if even)
            ) / i        //             and i = 1 (i.e. c is "{")
          ) & 0          //           clear n
        :                //         else (comma):
          !d             //           set n if we are at the root level
      :                  //       else (other character):
        n ?              //         if n is set:
          o = 0          //           clear o and clear n
        :                //         else:
          0              //           clear n
    :                    //     else (space):
      n,                 //       leave n unchanged
  n = 1,                 //     start with n = 1
  d = o = 0              //     start with d = o = 0
) | o                    // end of map(); return o

```
> 2 votes

# Answer
# Retina 0.8.2, 38 bytes

```
+`{([^{}]|{})+}
{}
\s

,$

=[^,]*$

}$

```

Try it online! Link includes test suite that assumes all tests are on separate lines and enclosed in quotes. Explanation:

```
+`{([^{}]|{})+}
{}

```

Collapse all objects recursively to empty objects.

```
\s

```

Delete all whitespace.

```
,$

```

Delete any trailing comma.

```
=[^,]*$

```

Delete the last parameter's default value, if any.

```
}$

```

Check whether the last parameter is a destructured object.
> 2 votes

---
Tags: code-golf, parsing, javascript
---


title: Yahtzee Small Straight Detection

text:
# Question
Title: Yahtzee Small Straight Detection
In the game Yahtzee, players roll five six-sided dice, and attempt to create certain hands to score points. One such hand is a *small straight*: four consecutive numbers, not necessarily in order. The three possible small straights are `1, 2, 3, 4`, `2, 3, 4, 5`, and `3, 4, 5, 6`.

For example, `[3, 5, 6, 1, 4]` contains the small straight `[3, 4, 5, 6]`.

### Input

An unsorted list of five integers, each between 1 and 6 inclusive, representing a Yahtzee hand.

### Output

A truthy value if the hand contains a small straight and a falsy value otherwise.

### Test cases

Truthy:

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

```

Falsy:

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

```

Inspired by this

## Catalogue

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

```
body{text-align:left!important}#answer-list{padding:10px;width:290px;float:left}#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="language-list"> <h2>Shortest Solution 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> <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> <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
> 29 votes
# MATL, ~~7~~ ~~12~~ ~~11~~ ~~9~~ ~~8~~ 6 bytes

*Thanks a lot to @lirtosiast for removing 2 bytes*

```
ud7BXf

```

Truthy is an array of nonzero values. Falsy is empty array (no output displayed).

*As of release 16.2.0, `u` is stable by default. So the code needs an extra `S` to sort the output: `uSd7BXf` (**7 bytes**). The link includes this modification.*

**Try it online!**

```
u     % input array implicitly. Transform into array of unique elements sorted
d     % array of differences between consecutive elements
7B    % push arrray [1 1 1] (number 7 converted to binary)
Xf    % indices of occurrences of the second array within the first

```

# Answer
> 13 votes
## Python, 44 bytes

```
lambda l:any({i+1,i+2,i+3}<set(l)for i in l)

```

Back after 9 months with an improvement. We don't need to check if `i` is in the set with Zgarb's idea of checking only start values in the set. We can now also use `<` for strict subsets because `i` must also be included.

---

**47 bytes:**

```
lambda l:any({i,i+1,i+2,i+3}<=set(l)for i in l)

```

Checks if any die rolls is the start of a small straight set. Thanks to Zgarb for the idea of only checking start values in the list, saving 5 bytes.

Python 3.5 has shorter set conversion, for 45 bytes

```
lambda l:any({i,i+1,i+2,i+3}<={*l}for i in l)

```

It's the same length to do `{*range(i,i+4)}` as `{i,i+1,i+2,i+3}`.

# Answer
> 10 votes
## Labyrinth, 41 bytes

```
=|?30
0 _ }:/2
3 1  { "!
({(  &{/
} )
+:"

```

A collab answer with @MartinBüttner. I think we've squeezed this one far beyond my initial expectations.

Output is `1` for truthy, empty for falsy. Try it online!

### Quick explanation

Convert each number `n` to a binary integer 1 followed by `n+1` zeroes, i.e. `2^(n+1)`. Bitwise OR the results and check for `1111` (in binary). Exponentiation needs to be implemented manually in Labyrinth.

### Detailed explanation

The usual primer:

* Labyrinth is a stack-based 2D programming language. For memory there is a main stack and an auxiliary stack, and popping from an empty stack produces 0 rather than an error.
* At each junction, where the instruction pointer could move down two or more possible paths, the top of the stack is checked to decide where to go next. Negative is left, zero is forward, positive is right.
* Digits in Labyrinth do not push the corresponding digit to the stack – rather, they pop `n` and push `n*10 + <digit>`. To start a new number, `_` pushes zero.

**Setup**

Execution begins at the top-left, with the instruction pointer facing rightwards. We execute:

```
=        Swap tops of main and auxiliary stacks
|        Bitwise OR

```

Aside from effectively pushing zeroes, these instructions don't change the stack.

**Left loop: exponentiate and bitwise OR**

Labyrinth doesn't have exponentiation, so we need to implement it manually. First we read an integer with `?`, and since this is guaranteed to be positive we turn right. `_1` pushes 1 and we enter the inner loop.

The inner loop does the following:

```
(       Decrement. For the first iteration this turns 1 into 0 so we move straight ahead
        downwards; for other iterations when we're coming from the left this turns 2^k into
        2^k-1 > 0, making us turn right (also downwards)
)       Increment again
"       No-op
:+      Duplicate and add, i.e. double
}       Move result to aux
(       Decrement input n. Since this is at a junction, we turn right and continue the
        loop if n is still positive, else we exit the loop by going forwards if n is 0
{       Move result from aux to main

```

Since this is a do-while loop, for input `n` this calculates `2^(n+1)`. We end with the zeroed input on the stack, and `30` turns this zero into 30. We then perform the same instructions from the setup, but this time they're actually useful.

```
=       Swap tops of main and aux, moving 30 to aux and 2^(n+1) to main
|       Bitwise OR (for the first input, this is bitwise OR with an implicit zero at
        the bottom of the stack)

```

This loop continues for each number in the input until EOF, when `?` returns 0. This makes us move forwards instead of turning, leading into...

**Bridge: some extra setup**

The `30` after the `?` turns the 0 from EOF into 30, which is pushed to the auxiliary stack via `}`. Of importance is the fact that we pushed a 30 to the auxiliary stack for every input number, so now **the auxiliary stack contains `5 + 1 = 6` copies of the number 30**.

Meanwhile, the main stack contains the bitwise OR of `2^(n+1)` for each input `n`. Let's call this bitwise OR `b`, since it gets modified in the right loop.

**Right loop: check result and output**

Here's what happens in the right-hand side loop:

```
:     Duplicate top of stack. This makes us turn right for the first iteration, since
      b is positive. For later iterations, when we're coming in from the
      right, we usually take the same turn (but see below)
{&    Bitwise AND with a 30 pulled from aux
{/    Integer division by a 30 pulled from aux. This returns 1 or 0 depending on whether
      we have found a small straight.
"     No-op at a junction. Turn right if small straight, else go forward.

[If small straight found]
!     Output the previous 1. This is at a dead end, so we turn around.
"     No-op at junction. Turn right since top of stack is positive.
      (stuff happens - see below)

[If small straight not found]
2     Turn 0 into 2
/     Divide b by said 2
      (continue loop)

```

Now, termination is a little tricky with this program. Here are the possible ways the program can terminate:

* **After 3 iterations of the right loop, and `b` is still positive:** Remember how we put six 30s into the auxiliary stack? Since we use two of them each iteration, on the fourth iteration we start pulling zeroes from the bottom of the auxiliary stack. This causes a division by zero when we do `{/`, and the program terminates.
* **After outputting a 1 for a small straight**: So we've executed `!` then turned right at the no-op `"` junction. Then we're in for a rollercoaster as we start crawling all over the left half again:

```
2     Pops b, pushes 10*b + 2
/}    Divide bottom zero by b, giving zero, pushing to aux
03    Zero at bottom of stack becomes 3
?     Push 0 due to EOF, main stack [3 0]. Go straight.
|=    Bitwise OR then swap tops of main and aux
03    Zero at bottom of stack becomes 3, stacks [3 | 3]
({(   Dec, shift dec. Stacks [2 2 | ], and we're in the exponentiator again.

```

After a few trips in the exponentiator, the stack looks something like `[12 | 30 30]`, which errors out by division by zero after another two iterations in the right loop.

* **After b becomes zero at some point**: The key here is that the `:` in the right loop is at a junction. If the input was, say, `1 1 1 1 1`, then `b` would be `4`, then `2`, then `1`, then `0` after the third iteration. Instead of turning at the `:`, the IP now moves straight ahead, and something like the previous case happens to cause an eventual termination.

All in all it's a mess how the program terminates, but hey anything to save those few bytes!

# Answer
> 7 votes
# Mathematica, ~~39~~ ~~43~~ ~~44~~ ~~31~~ ~~39~~ 44 bytes

```
Differences@Union@#~MatchQ~{___,1,1,1,___} &

```

# Answer
> 7 votes
## Haskell, ~~39~~ 34 bytes

```
f x=any(\y->all(`elem`x)[y..y+3])x

```

Usage example: `f [1,2,3,3,4]` -\> `True`.

Similar to @xnor's answer, i.e. check if any of the small straights are in the input list. Actually I'm testing all "small straights" (i.e. 4 consecutive numbers) starting with any of the numbers from the input list, some of them being invalid and therefore always fail the `all` test and don't distort the `any` test, e.g. `[5,6,7,8]`.

Edit: @Zgarb saved 5 bytes. Thanks!

# Answer
> 5 votes
# MATL, 11 bytes

```
udY'w1=)2>a

```

Try it online

```
u           unique (implicit sort)
d           diff
Y'          run-length-encode
w1=)        exract the length of all runs of ones
2>          check whether they are longer than two
a           any (any non-zero element)

```

# Answer
> 5 votes
# JavaScript (ES6), ~~55~~ 53 bytes

```
a=>(z=[0,1,2,3]).some(b=>z.every(c=>a.includes(c+b)))

```

returns `true` for truthy and `false` for falsy.

### How it works

Return if some value in \[0, 1, 2, 3\] fulfills the condition that for every value in \[0, 1, 2, 3\] the sum of these two values is in the input array.

So, return if the array has every value in \[0, 1, 2, 3\] (impossible), \[1, 2, 3, 4\], \[2, 3, 4, 5\], or \[3, 4, 5, 6\].

# Answer
> 5 votes
# Perl, ~~47~~ ~~43~~ ~~42~~ ~~39~~ ~~37~~ 29 bytes

Includes +1 for `-p`

Run with the sequence on STDIN, e.g.

```
perl -p smallstraight.pl <<< "1 2 3 3 4"

```

`smallstraight.pl`:

```
s//$_|=1x$'.w/reg;$_=/.w{4}/

```

## Explanation

```
s//          / eg             Each possible postfix string (including the
                              empty string) is assigned to $' in turn
                              So each input digit will be the start of $'
                              at least once
       1x$'.w                 Put a w at position $'.
                              e.g. digit 4 becomes 1111w
   $_|=                       Or into existing $_.
                                w        is binary 0111 0111
                                space    is binary 0010 0000
                                digit<=7 is binary 0011 0xxx
                              So an "or" with "w" is always w again:
                                                   0111 0111
                              And no other way can you get a w since w is the
                              only thing that can set the high bits. So the
                              already existing string in $_ has no effect on
                              the number of w's in the result
              r               The $_ that has been "or"ed several times is
                              exfiltrated out of the substitution. It will
                              have a w in every position that the original
                              string had a digit with an extra w at position
                              0 since the s///g will also have matched the
                              empty string at the end
                              So e.g. "1 2 3 5 6" will become "wwww3ww 6"
                  $_=/.w{4}/  We have a small straight if there were 4
                              consecutive numbers, now 4 consecutive w's. But
                              the w we always get at the start of the string
                              doesn't count. Notice that the string cannot
                              have a newline since bit "0010 0000" is always
                              set. So "." to skip one character is safe

```

# Answer
> 5 votes
# Ruby, ~~58~~ ~~55~~ ~~50~~ ~~47~~ ~~43~~ 33 bytes

I just now saw that I have been beaten to the punch by Paul's Ruby answer. I am not deterred however as I think this could still be a decent answer with some more golfing. Based, in part, on xnor's Python answer.

**Edit:** Some golfing and correcting a mix-up in the ternary conditional.

**Edit:** I now use `.any?` like Not that Charles does in their Ruby answer but only because I needed a simple way to remove `a` and to return only a truthy and a falsey with `!([*i..i+3]-l)[0]` since `.map` would return an array of `true` and `false`.

```
->l{l.any?{|i|!([*i..i+3]-l)[0]}}

```

Returns either `true` or `false`.

**Ungolfed:**

```
def f(l)
  a = p
  l.any? do |i|
    if ( (i..i+3).to_a - l )[0]     # if (i..i+3) in l
      a = false                     # a[0] is equivalent to !a.empty?
    else
      a = true
    end
  end
  puts a
end

```

Important note: For those who want to use the `(a2 - a1).empty?` code to determine if all elements of `a2` are in `a1`, note that if you want to make sure that, for example, `[2,1,2]` is in `[1,2,3,3]` to multiplicity of elements, you need other code. Relevant discussion of this problem here.

# Answer
> 5 votes
# Ruby, 31

Instead of trying to be smart like the first Ruby answer, this just goes through the array of integers, and for each integer, sees if there's a small straight in the input starting with that integer. Doesn't worry about the possible values or uniqueness.

This seems to be using the same algorithm as Sherlock's answer.

```
->x{x.any?{|d|[*d..d+3]-x==[]}}

```

# Answer
> 4 votes
# Pyth, ~~13~~ 11

```
@.PQ4.:S6 4

```

2 bytes thanks to Jakube!

Returns a non-empty list for truthy, empty list for falsy.

Try it online or run the Test Suite (split by a syntax error for Readability™).

# Answer
> 4 votes
# Japt, ~~13~~ 12 bytes

```
Uá4 d@7o ¬fX

```

**Test it online!** or **Verify all test cases**.

### How it works

```
       // Implicit: U = input array
Uá4    // Take all permutations of U of length 4.
d@     // Return whether any item X returns truthily to this function:
7o ¬   //  Take the range [0..7) and join. Produces "0123456".
fX     //  Match X in this string.
       //  This returns null if X is not a subset of [0..7), and a (truthy) array otherwise.
       // Implicit output

```

# Answer
> 3 votes
## CJam, ~~16~~ ~~15~~ 12 bytes

```
7,4ewl~f&3f>

```

Yields a non-empty string for truthy test cases and an empty string for falsy ones.

Test suite.

### Explanation

```
7,      e# Push [0 1 2 3 4 5 6].
4ew     e# Get all length-4 sublists. This gives:
        e#   [[0 1 2 3]
        e#    [1 2 3 4]
        e#    [2 3 4 5]
        e#    [3 4 5 6]]
        e# i.e. all possible small straights (and an impossible one).
l~      e# Read and evaluate input.
f&      e# Set intersection of each small straight with the full list.
        e# If any small straight is contained in the list, all 4 of its
        e# elements will be retained.
3f>     e# Discard the first three elements of each intersection. If a
        e# small straight was not in the list, this will give an empty
        e# list. Otherwise, one element will remain.

```

At the end of the program, this list is flattened into a single string and printed to STDOUT. If any of the small straights were found, their remaining elements will be in the string. Otherwise all the lists were empty, and so the string is also empty.

# Answer
> 3 votes
## C#, ~~156~~ ~~151~~ ~~150~~ ~~131~~ ~~121~~ ~~93~~ ~~92~~ 90 bytes

```
int l;bool f(int[]a){foreach(var v in a)l|=1<<v-1;return(l&15)>14||(l&30)>29||(l&60)>59;}

```

**or:** (same number of bytes)

```
int l;bool f(int[]a){foreach(var v in a)l|=1<<v;return(l&30)>29||(l&60)>59||(l&120)>119;}

```

Ungolfed:

```
int l;
bool f(int[] a)
{
    foreach (var v in a)
        l |= 1 << v - 1;
    return (l & 15) > 14 ||   //Bits 1-4 are set OR
           (l & 30) > 29 ||   //Bits 2-5 are set OR
           (l & 60) > 59;     //Bits 3-6 are set
}

```

**Big Edit:** Just realized I only need to post a function, not a whole program. That saves a whole lot. No boilerplate, no need to convert string input into numbers, etc. Now we're actually approaching a respectable number of bytes (for a non-golfing language anyhow).

# Answer
> 3 votes
# 05AB1E, ~~9~~ ~~8~~ 10 bytes

**Truthy** is containing an array in the output, **falsy** is when no output is produced. Code:

```
œvy¦¥1QPiy

```

Explanation *outdated*:

```
œ          # Compute all permutations
 vy        # Map over each permutation
   ¦       # Head, leaves [1:]
    ¥      # Delta, computes the differences between the elements
     P     # Product, which computes the product of the array
      iy   # If equal to 1, push the array again
           # Implicit, if there is a match, an array will be displayed.

```

Try it online!

Uses **CP-1252** encoding.

# Answer
> 3 votes
# Javascript ES6 47 bytes

```
q=>/12+3+4|23+4+5|34+5+6/.test(q.sort().join``)

```

# Javascript ES6 52 bytes

```
q=>/1,+1,+1/.test(q.sort().map((a,i)=>a-q[i-1]||``))

//sort the array
//map each element to the difference from the last element
//Look for three 'increment by ones' (ignore increment by 0s)

```

---

Old answer

# Javascript ES6 64 bytes

thanks to ETHproductions for helping save several bytes

```
q=>q.sort().map(o=>(o-s?o-s<2?t++:t=t>3?t:1:0,s=o),t=1,s=-1)|t>3

```

---

```
q=>              //take an input
q.sort()         //sort it
.map(            //for each number
  o=>
    s=           //set current value =
      !(o-s) ?   //if it's a duplicate
        o :      //just keep the current state (set s to s again)
        (
         o-s < 2 ?  //if the current values is one more than the next one
           t++ :    //increment the total
           t=t>4?t:1 //otherwise, set the total back to 1, unless we've hit 4 total already
         )&&o  //set the current value to the current token
   ,t=1,s=-1)  //init the total, and the current value (set it to -1 since we won't hit that anyways

|t>3 //return total > 3 (so 1 if we get a run of 4 or 5)

```

**Testing**

```
//true and false test cases from OP
tr = [[1, 2, 3, 3, 4], [1, 2, 3, 4, 5], [3, 5, 6, 1, 4], [1, 5, 3, 4, 6], [4, 5, 2, 3, 5], [1, 4, 3, 2, 2], [5, 4, 3, 6, 3], [5, 3, 5, 4, 6], [2, 4, 5, 1, 3], [3, 6, 4, 5, 3], [5, 6, 4, 3, 5], [4, 5, 3, 6, 3], [4, 5, 5, 3, 2], [4, 5, 2, 3, 5], [4, 6, 5, 3, 6], [4, 2, 3, 1, 5], [3, 6, 4, 6, 5], [5, 2, 1, 3, 4], [4, 4, 1, 2, 3], [4, 1, 4, 2, 3], [5, 1, 4, 3, 6], [5, 2, 2, 3, 4], [4, 4, 6, 5, 3], [2, 4, 3, 5, 1], [5, 4, 2, 5, 3], [2, 3, 5, 5, 4], [1, 6, 3, 4, 5], [4, 5, 3, 3, 6], [6, 4, 3, 6, 5], [4, 6, 6, 5, 3], [4, 3, 5, 2, 2], [2, 3, 2, 1, 4], [4, 2, 6, 1, 3], [4, 4, 5, 3, 6], [4, 5, 6, 3, 6]]

fa = [[1, 2, 3, 5, 6], [5, 1, 1, 6, 6], [4, 6, 4, 1, 1], [6, 4, 1, 6, 4], [4, 6, 3, 6, 6], [2, 1, 4, 6, 4], [2, 6, 1, 5, 6], [2, 6, 1, 5, 6], [3, 6, 5, 3, 2], [3, 2, 3, 5, 3], [5, 5, 6, 2, 3], [3, 4, 6, 4, 3], [1, 4, 5, 5, 1], [1, 4, 4, 4, 1], [1, 6, 5, 1, 4], [6, 6, 4, 5, 4], [5, 3, 3, 3, 2], [5, 2, 1, 5, 3], [3, 5, 1, 6, 2], [6, 4, 2, 1, 2], [1, 3, 1, 3, 2], [3, 1, 3, 4, 3], [4, 3, 1, 6, 3], [4, 6, 3, 3, 6], [3, 6, 3, 6, 4], [1, 1, 3, 1, 3], [5, 5, 1, 3, 2], [3, 4, 2, 6, 6], [5, 4, 2, 6, 1], [2, 4, 4, 5, 4], [3, 6, 2, 5, 5], [2, 5, 3, 5, 1], [3, 2, 2, 3, 4], [5, 2, 2, 6, 2], [5, 6, 2, 5, 6]]

f=q=>q.sort().map(o=>(o-s?o-s<2?t++:t=t>3?t:1:0,s=o),t=1,s=-1)|t>3

tr.map(f)   //just look to make sure every value is true
fa.map(f)  //just look to make sure every value is false

```

# Answer
> 3 votes
## TI-BASIC, 25 bytes

```
not(min(fPart(prod(Ans+36)/(65{703,779,287

```

An equivalent (ungolfed) Python expression which you can test:

```
def has_small_straight(l):
    product = reduce(lambda x,y: x*y, [x + 36 for x in l], 1)
    numbers = [37*19*13*5, 19*13*5*41, 13*5*41*7]
    return not(all([product%x for x in numbers]))

```

The idea behind this is divisibility. To check whether a `1, 2, 3, 4`, `2, 3, 4, 5`, or `3, 4, 5, 6` occurs, we can map the numbers 1-6 to 37-42, and then multiply the correct numbers together.

Each of the numbers in \[37,42\] have a prime factor that the other numbers lack.

```
n             |  1 |  2 |  3 |  4 |  5 |  6 |
n + 36        | 37 | 38 | 39 | 40 | 41 | 42 |
Factor        | 37 | 19 | 13 |  5 | 41 |  7 |

```

Therefore, if the product of the five numbers is divisible by 37, the original list contained a 1. If by 19, it contained a 2; etc. If it is divisible by `37*19*13*5` = `65*703`, it contains `1`, `2`, `3`, and `4` and similarly for the other two numbers.

This solution is an improvement on one that @Weregoose posted in 2009.

# Answer
> 3 votes
# Ruby - 80 -\> 79 -\> 76 -\> 54 -\> 48 -\> 40 bytes

Fifth Try (40 bytes):

```
->x{/1234|2345|3456/===x.uniq.sort.join}

```

Uses lambda syntax to define the function. (Thanks to competing Ruby golfer @Sherlock9 for this idea.)

To test using lambda call:

```
s = ->x{/1234|2345|3456/===x.uniq.sort.join}
s.call([1,3,5,4,4])
s.call([1,3,5,4,2])

```

Fourth Try:

```
def s?(x)/1234|2345|3456/===x.uniq.sort.join end

```

Replaced nil? and negation with === operator.

Third Try:

```
def s?(x)!(/1234|2345|3456/=~x.uniq.sort.join).nil?end

```

Uses regular expression.

Second Try:

```
def s?(x)[1234,2345,3456].select{|a|x.uniq.sort.join.include?a.to_s}.any?end

```

New approach uses dedup (uniq), sort and join, plus include? to search for a match of any solutions in the input rendered as a string.

First Try: 79 bytes

```
def s?(x)[[1,2,3,4],[2,3,4,5],[3,4,5,6]].select{|a|(a&x.uniq).length>3}.any?end

```

Tester:

```
x = [1,4,3,3,6]
s?(x)

x = [2,4,5,1,3]
s?(x)

```

Uses deduping (uniq function) plus set intersection (& operator) to test if any of the good sequences matches the given sequence. No sorting needed.

# Answer
> 3 votes
# Dyalog APL, 15 bytes

`{∨/∧/⍵∊⍨⍵∘.+⍳4}`

uses `⎕IO=0`

`⍳4` is `0 1 2 3`

`⍵∘.+⍳4` is 5×4 a matrix of each die incremented by each of `⍳4`

`⍵∊⍨` checks if the elements of the matrix are in the hand, result is a boolean (0-or-1) matrix, we need to find a row of all 1s

`∧/` is the and-reduction by rows, result is a boolean vector

`∨/` is the or-reduction of that vector

# Answer
> 2 votes
## Seriously, 21 bytes

```
3R`;4+@x`M4,╨╗`╜íu`MΣ

```

Try it online!

Outputs a positive value for true, and a 0 for false.

Explanation:

```
3R`;4+@x`M4,╨╗`╜íu`MΣ
3R`;4+@x`M             push [[1,2,3,4], [2,3,4,5], [3,4,5,6]
          4,╨╗         push all 4-length permutations of input to register 0
              `   `M   map:
               ╜íu       push 1-based index of list in permutations, 0 if not found
                    Σ  sum

```

# Answer
> 2 votes
## PHP, 95 bytes

```
function s($d){$a=array_diff;$r=range;return!($a($r(1,4),$d)&&$a($r(2,5),$d)&&$a($r(3,6),$d));}

```
**Exploded view**
```
function s($d){
  $a = array_diff;
  $r = range;
  return !($a($r(1,4),$d)
        && $a($r(2,5),$d)
        && $a($r(3,6),$d));
}

```
**Input / function call**
```
s(Array[int, int, int, int, int]);

```
**Output**
```
bool

```

# Answer
> 2 votes
# Jelly, 9 bytes

There has to be an 8-byte solution, will continue searching... Code:

```
Œ!Ḋ€Iµ7Be

```

This is the same as my **05AB1E** solution.

Explanation:

```
Œ!         # Compute all permutations
  Ḋ€       # Dequeue each, leaving [1:]
    I      # Delta function
     µ     # Start a new monadic chain
      7B   # 7 in binary, which is [1, 1, 1]
        e  # Return 1 if this array exists

```

Try it online!

# Answer
> 2 votes
# PARI/GP, 71 bytes

This can probably be golfed further, but as a start:

```
s=setminus;v->t=s([1..6],Set(v));!#s(t,[1,2])+!#s(t,[5,6])+!#s(t,[1,6])

```

I don't see a way of reducing duplication without using more space; this version is 75 bytes:

```
s=setminus;v->t=s([1..6],Set(v));z=(u->!#s(t,u));z([1,2])+z([5,6])+z([1,6])

```

# Answer
> 2 votes
# Retina, ~~70~~ 54 bytes

Input is a single string of the integers like `13342`. Output is a `1` if found, or a `0` if not.

```
.                       # Replace integer digits with unary
$*x,
+`(x+(x+,))\2           # Sorts the list by repeated swapping
$2$1
(x+,)\1                 # Removes adjacent duplicates
$1
(x+,)x\1xx\1xxx\1       # Matches a small straight

```

Note that the removal of duplicates only needs to occur once, since there are only five numbers. Needing to remove more than one number would mean there isn't a small straight anyway.

**Try it online**

Thanks to Martin for the idea to move the commas inside the capture groups, saving a whopping 16 bytes.

# Answer
> 2 votes
# Scala, ~~76~~ ~~70~~ ~~61~~ 60 bytes

```
(s:Seq[Int])=>(1 to 6)sliding(4)exists(t=>(s diff t).size<2)

```

Tester:

```
val f = <code here>
val truthy = Seq(Seq(1, 2, 3, 3, 4), Seq(1, 2, 3, 4, 5), Seq(3, 5, 6, 1, 4), Seq(1, 5, 3, 4, 6), Seq(4, 5, 2, 3, 5), Seq(1, 4, 3, 2, 2), Seq(5, 4, 3, 6, 3), Seq(5, 3, 5, 4, 6), Seq(2, 4, 5, 1, 3), Seq(3, 6, 4, 5, 3), Seq(5, 6, 4, 3, 5), Seq(4, 5, 3, 6, 3), Seq(4, 5, 5, 3, 2), Seq(4, 5, 2, 3, 5), Seq(4, 6, 5, 3, 6), Seq(4, 2, 3, 1, 5), Seq(3, 6, 4, 6, 5), Seq(5, 2, 1, 3, 4), Seq(4, 4, 1, 2, 3), Seq(4, 1, 4, 2, 3), Seq(5, 1, 4, 3, 6), Seq(5, 2, 2, 3, 4), Seq(4, 4, 6, 5, 3), Seq(2, 4, 3, 5, 1), Seq(5, 4, 2, 5, 3), Seq(2, 3, 5, 5, 4), Seq(1, 6, 3, 4, 5), Seq(4, 5, 3, 3, 6), Seq(6, 4, 3, 6, 5), Seq(4, 6, 6, 5, 3), Seq(4, 3, 5, 2, 2), Seq(2, 3, 2, 1, 4), Seq(4, 2, 6, 1, 3), Seq(4, 4, 5, 3, 6), Seq(4, 5, 6, 3, 6))
val falsy = Seq(Seq(1, 2, 3, 5, 6), Seq(5, 1, 1, 6, 6), Seq(4, 6, 4, 1, 1), Seq(6, 4, 1, 6, 4), Seq(4, 6, 3, 6, 6), Seq(2, 1, 4, 6, 4), Seq(2, 6, 1, 5, 6), Seq(2, 6, 1, 5, 6), Seq(3, 6, 5, 3, 2), Seq(3, 2, 3, 5, 3), Seq(5, 5, 6, 2, 3), Seq(3, 4, 6, 4, 3), Seq(1, 4, 5, 5, 1), Seq(1, 4, 4, 4, 1), Seq(1, 6, 5, 1, 4), Seq(6, 6, 4, 5, 4), Seq(5, 3, 3, 3, 2), Seq(5, 2, 1, 5, 3), Seq(3, 5, 1, 6, 2), Seq(6, 4, 2, 1, 2), Seq(1, 3, 1, 3, 2), Seq(3, 1, 3, 4, 3), Seq(4, 3, 1, 6, 3), Seq(4, 6, 3, 3, 6), Seq(3, 6, 3, 6, 4), Seq(1, 1, 3, 1, 3), Seq(5, 5, 1, 3, 2), Seq(3, 4, 2, 6, 6), Seq(5, 4, 2, 6, 1), Seq(2, 4, 4, 5, 4), Seq(3, 6, 2, 5, 5), Seq(2, 5, 3, 5, 1), Seq(3, 2, 2, 3, 4), Seq(5, 2, 2, 6, 2), Seq(5, 6, 2, 5, 6))
println("Failed truthy: " + truthy.filterNot(f))
println("Failed falsy: " + falsy.filter(f))

```

# Answer
> 2 votes
# Pyth, 11 bytes

```
f!-TQ.:S6 4

```

Test suite

Generate the length 4 substrings of \[1..6\], then filter them on no elements remaining when the elements of the input are removed.

# Answer
> 2 votes
# Jelly, 8 bytes

```
6Rṡ4ḟ€ċ“

```

Try it online! or verify the truthy test cases and the falsy test cases.

### How it works

```
6Rṡ4ḟ€ċ“  Main link. Argument: A (list)

6R        Yield [1, 2, 3, 4, 5, 6].
  ṡ4      Split it into overlapping slices of length 4, yielding
          [[1, 2, 3, 4], [2, 3, 4, 5], [3, 4, 5, 6]].
    ḟ€    Remove all occurrences of A's elements from each slice.
      ċ“  Count the resulting number of empty list.
          This returns the number of distinct small straights in A (0, 1 or 2).

```

# Answer
> 2 votes
# Javascript ES6 43 bytes

```
q=>/1,1,1,1/.test(q.map(a=>l[a]=1,l=[])&&l)

```

---

//couldn't quite get this to work :/
```
q=>q.map(a=>l&=~(1<<a),l=62)&&l<7||l==32

```

This takes the number 62 (111110 in binary) For each number in the input array it removes that bit

The resulting number should either be

```
100000 or
000000 or
000010 or
000110 or
000100

```

so I check if the result is less than 7 (0000111) or if it's equal to 32 (100000)

# Answer
> 2 votes
# Mumps, 113 78 Bytes

The version of Mumps I'm using is InterSystems Cache.

I can't think of a way of golfing this technique any shorter; with a different technique it might be possible, but for now this'll do and at least it's shorter than C++... but not by much. Anyway...

OK, here's a shorter way. Instead of having 3 separate variables for the short runs, use a single variable for all 6 'dice' and extract the portions later:

```
R R S Y=111111 F F=1:1:5{S $E(Y,$E(R,F))=0} W '$E(Y,1,4)!'$E(Y,2,5)!'$E(Y,3,6)

```

*so much for me not finding a better way with the same technique... I should look before I leap, eh? ;-)*

I'll leave my original answer below for historical purposes...

---

---

```
R R S (G,H,I)=1111 F F=1:1:5{S Q=$E(R,F) S:1234[Q $E(G,Q)=0 S:2345[Q $E(H,Q-1)=0 S:3456[Q $E(I,Q-2)=0} W 'G!'H!'I

```

and here's the explanation of what's going on with the code:

```
R R                   ; read from STDIN to variable R
S (G,H,I)=1111        ; set our 3 possible short straights
F F=1:1:5{            ; For loop from 1 to 5
S Q=$E(R,F)           ; get each digit from the input and save in Q
S:1234[Q $E(G,Q)=0    ; If Q is either 1,2,3 or 4, zero out that position in G.
S:2345[Q $E(H,Q-1)=0  ; if Q is either 2,3,4 or 5, zero out that position (-1) in H.
S:3456[Q $E(I,Q-2)=0  ; if Q is either 3,4,5 or 6, zero out that position (-2) in I.
}                     ; and end the loop.
W 'G!'H!'I            ; If G,H, or I are all zeroes (indicating a full straight),
                      ; taking the not of each will make (at least one) of the
                      ; values true. OR-ing all three values will let us know if
                      ; at least one short straight was complete.
                      ; Output is 1 for truthy, 0 for falsy.

```

I didn't test *every single* truthy & falsy input as that involved manually typing them all in; but I did test approximately the first half of each, verified the long straights still show truthy and several of the runs noted to not necessarily work correctly (\[4,2,5,3,4\], \[1,2,3,3,4\] etc.) and seems to be working correctly.

# Answer
> 1 votes
# Jelly, 11

```
QṢṡ4ðfø6Rṡ4

```

Try it online!

This is pretty much a copy of my Pyth answer, just trying to figure out how to chain stuff. Feels like it should be golfable.

### Expansion:

```
QṢṡ4ðfø6Rṡ4  ##  1, 2, 0 chain, 1 argument from command line
QṢṡ4         ##  first chain, uniQue and Sort the input, then
             ##  get overlapping lists of length 4 (ṡ)
    ð        ##  separator
     f       ##  filter left argument on being a member of right argument
      ø      ##  separator
       6Rṡ4  ##  all overlapping lists of length 4, from 1-indexed range of 6
             ##  generates [1,2,3,4],[2,3,4,5],[3,4,5,6]

```

If you want to ask any hard questions, like why the separators are different, then my answer to you is: "I'll answer in 6-8 weeks" :P (More seriously, I think it's the pattern matching, monad-dyad vs nilad-dyad, but I don't know and don't want to spread misinformation.)

# Answer
> 1 votes
## PowerShell v3+, ~~85~~ ~~45~~ 42 bytes

```
-join($args|sort -u)-match"1234|2345|3456"

```

Requires v3 or newer for the `-Unique` flag on the `Sort-Object` cmdlet.

Takes commandline `$args` as individual elements, then `sort`s only the `-u`nique values, and `-join`s it together into a string. If that then regex `-match`es against the `1234|2345|3456` pattern, output is `True`; else, `False`. The Boolean value is left on the pipeline and output is implicit.

*Saved 3 bytes thanks to Titus*

# Answer
> 1 votes
# Minkolang, 24 bytes

Try it here! Saved 3 bytes thanks to El'endia Starman!

```
$ns4[2~c-1R]xs011130$ZN.
$n                          C take all input C
  s                         C sort the stack C
   4[      ]                C repeat that 4x C
     2~c                    C copy 2nd elem. C
        -                   C subtract top 2 C
         1R                 C rot stack once C
            x               C drop top elem. C
             s              C sort the stack C
              011130$Z      C count # of 111 C
                      N.    C output and end C

```

I'm pretty happy that the explanation came in fixed width. It was coincidental the first three times, then I decided to roll with it.

# Answer
> 1 votes
## JavaScript (ES6), 57 bytes

```
s=>(g=(n,m=4)=>!m||~s.search(n)&&g(n+1,m-1))(1)|g(2)|g(3)

```

Takes a string as input, and checks whether it contains all the digits in the sets (1,2,3,4), (2,3,4,5) or (3,4,5,6). Returns 1 if it does and 0 if it doesn't.

# Answer
> 1 votes
# C++17, ~~69~~ ~~68~~ 66 bytes

-1 byte for changing truthy and falsey value. -2 bytes for setting `r` inside the initializer list.

As unnamed generic variadic lambda returning via reference parameter.

```
[](int&r,auto...p){for(int s:{r=30,60,120})r*=s-(s&(...|(1<<p)));}

```

The folding expression `(...|(1<<p))` shifts `1` to the left for each item in `p` and bitwise-or them to create a set of fallen dice. Then compare this with the bitsets of small straights. Returns `0` for detection and otherwise for otherwise.

Ungolfed and usage:

```
#include<iostream>
using namespace std;

auto f=
[](int& r, auto...p){
 for (int s: {r = 30,60,120})
  r *= s - (s & (...|(1<<p)));
}
;

int main() {
  int r;
  f(r,1,2,3,4,6);
  cout << r << endl;
  f(r,2,3,4,5,2);
  cout << r << endl;
  f(r,3,4,5,6,6);
  cout << r << endl;
  f(r,1,1,3,5,4);
  cout << r << endl;
}

```

It seems like GCC 6.2 has a bug, that only left folds of the form `...|f(p)` work, right folds like `f(p)|...` don't work.

## previous ~~77~~ 76 bytes solution

-1 byte for 0-indexing. Another -1 for changing truthy/falsey value.

Heavy use of parameter packs and fold expressions. As unnamed lambda returning via reference parameter:

```
[](int&r,auto...p){[&](auto...s){r=(...*(s-(s&(...|(1<<p)))));}(30,60,120);}

```

Ungolfed & explanation:

```
[](int& r, auto... p){ //out-reference and parameter pack
  [&](auto...s){       //declare inline lambda accepting another parameter pack and reference capture everything
    r=(...*(s-(s&(...|(1<<p-1)))));    //explained below
  }(30,60,120);         //immediately call the lambda with the bitset of small streets
}

    r=(...*(s-(s&(...|(1<<p)))));
                       (1<<p)      shift 1 to the left for each input p
                  (...|(1<<p))     fold with binary-or, create bitset
                s&(...|(1<<p))     binary-and with each constant s
            s-(s&(...|(1<<p)))    subtracts any of the constants, so if any small street is present the result is 0
       ...*(s-(s&(...|(1<<p))))   fold with multiply, like any(...)
    r=(...*(s-(s&(...|(1<<p))))); apply result to output parameter

```

Usage:

```
int main() {
  int r;
  f(r,1,2,3,5,4);
  cout << r << endl;
}

```

# Answer
> 1 votes
## Clojure, 54 bytes

```
#(some(fn[p](every?(set %)p))(partition 4 1(range 7)))

```

`(partition 4 1(range 7))` returns possible small-straights (we can ignore `0`): `((0 1 2 3) (1 2 3 4) (2 3 4 5) (3 4 5 6))`

`some` returns `true` if some arguments of `p` return `true` from the anonymous function and `nil` otherwise. Within `every?` returns true if the "function" (set of values of input list) returns a truthy value for all arguments of `p`. Thus the combination of `some` and `every?` checks if there exists such partition for which all numbers are found from the input argument `%`.

# Answer
> 1 votes
# Perl 6, ~~32~~ ~~24~~ 18 bytes

```
{@_⊇^4+1+any ^3}

```

`^4` is the range of integers from 0 to 3. `^4+1` is the range of integers from 1 to 4. `any ^3` is the or-junction of the values 0, 1, and 2. Adding it to the range 1-4 produces the or-junction of the ranges 1-4, 2-5, and 3-6. A truthy value is returned if the argument list `@_` is a superset of any of those ranges.

# Answer
> 1 votes
# awk, 51 chars

```
{for(;++i<7;)a=a gsub(i,1);exit sub(/[12]{4}/,1,a)}

```

Solution searches for numbers `[1-6]` from given string in that order, packs their frequencies to var `a` (`11235` -\> `21101), searches for four consecutive` 1`s or` 2`s (there can be only 1` 2\`) and exits with search result.

```
$ echo 1,2,2,3,5|awk '{for(;++i<7;)a=a gsub(i,1);exit sub(/[12]{4}/,1,a)}'
$ echo $?
0
$ echo 1,2,3,4,5|awk '{for(;++i<7;)a=a gsub(i,1);exit sub(/[12]{4}/,1,a)}'
$ echo $?
1

```

btw, *small straight* over here is `1,2,3,4,5`.

# Answer
> 1 votes
# Kotlin, ~~80~~ 68 bytes

```
d.toHashSet().zipWithNext{a,b->b-a}.joinToString("").contains("111")

```

Try it online!

# Answer
> 1 votes
# Brachylog, 5 bytes

```
pb~⟦₂

```

Try it online!

Takes input through the input variable and outputs through success or failure. (The output variable contains the smallest and largest numbers within the small straight.)

```
p        Some permutation of the input,
 b       with its first element removed,
  ~⟦₂    is a range.

```

This brute forces permutations until either one of them is of the form `[_ | sorted small straight]` or there aren't any permutations left to check.

# Answer
> 1 votes
# 05AB1E, 6 bytes

```
ê¥JƵAå

```

Try it online!

```
ê          # sorted uniquified input
 ¥         # deltas (e.g. [1, 2, 3, 4, 6] => [1, 1, 1, 2])
  J        # join
   ƵA      # compressed integer 111
     å     # is it a substring of the joined deltas?

```

# Answer
> 1 votes
# K (ngn/k), 16 bytes

```
{|/&/~^x?x+/:!4}

```

Try it online!

Another port of @ngn's APL answer, using `~^x?y` as the membership test.

# Answer
> 0 votes
# R + `pryr`, 49 bytes

(`pryr` is a package that gives shorthand for creating functions)

```
f=pryr::f;f(any(combn(x,4,f(sum(diff(x))))==3))

```

Using @ETHproductions idea of taking all combinations of length 4

# Answer
> 0 votes
# C++, ~~189 168 144~~ 143 bytes

```
void main(int i,char *x[]){char c[6]={0},*v=x[1];for(i=0;v[i];)c[v[i++]-'1']++;printf(c[2]&&c[3]&&(c[0]&&c[1]||c[1]&&c[4]||c[4]&&c[5])?"T":"F")}

```

Input must be a 5-digit integer on the command line, e.g. test.exe 12334

# Answer
> 0 votes
# PHP, 65 bytes

```
while($i++<3)array_intersect($r=range($i,$i+3),$argv)<$r?:die(1);

```

Takes dice from command line arguments; exits with code `1` for straight, `0` else. Run with `-r`.

# Answer
> 0 votes
# Stax, 7 bytes

```
Ç╒t╛♦─├

```

Run and debug it

Algorithm:

* Sort
* Remove duplicates
* Compute pairwise differences
* Check for \[1,1,1\] as contiguous sub-array.

# Answer
> 0 votes
# , 18 bytes

```
4 e.1#.]e.~]+/i.@4

```

Try it online!

Inspired by ngn's APL answer.

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


title: Help me pair my left and right socks!

text:
# Question
Title: Help me pair my left and right socks!
Inspired by Help me pair my socks, and the fact that I have some pairs of socks where the left sock is distinct from the right.

---

## Background

Again, I have a huge pile of socks. And a machine that can give the list of labels of the socks for me. This time, the labels follow these rules:

* Some socks have left and right versions. In this case, left socks are labelled `-n` and right socks are labelled `n`, where `n` is a unique positive integer. The list of such socks will be explicitly given to you.
* The others don't have such a thing, and they just match themselves. All socks of this type are simply labelled `n` (no negative labels).

An example pile would look like this:

```
[3, 3, -2, 4, -1, -1, 1, 4, 4, 3, 2, 3, -1, 4, 4]

```

where 1 and 2 have left and right versions. Then the pairs and leftovers are:

```
pairs: {3: 2, 4: 2, 1: 1, 2: 1} or [1, 2, 3, 3, 4, 4]
leftovers: {4: 1, -1: 2} or [-1, -1, 4]

```

Note that two `-1`s don't make a pair because both are left socks.

## Challenge

Given the **pile of socks** and the **list of sock labels having L/R versions**, output the **pairs** that can be made from the pile, and **leftovers** that are not part of any pairs.

## Input and output

You can assume the following for input:

* Zeros won't appear in either list.
* L/R labels are unique and all positive, but possibly not sorted.
* Negative numbers that are not part of L/R labels won't appear in the pile.

Both outputs can be represented as either a mapping type (label to count) or a flat list (each item appearing once per count). You can output in following ways:

* Pairs can be represented as either a pair `(3, 3) / (-1, 1)` or a single number `3 / 1 / -1`, or a mixture of both. But **the same pairs should be represented in the same way in a single run**, e.g. outputting `[3, (3, 3)]` or `[(-1, 1), (1, -1)]` or `[1, -1]` is not allowed.
* For both pairs and leftovers, a *pair* and *single number* can be wrapped in any kind of containers, e.g. singleton arrays can be used to represent a single leftover.
* For both pairs and leftovers, the order of items is not important.
* If you use a mapping type, zero-count items are allowed, even the ones not in the pile of socks.

## Scoring and winning criterion

Standard rules apply. The shortest code in bytes wins.

## Test cases

```
Pile: [3, 3, -2, 4, -1, -1, 1, 4, 4, 3, 2, 3, -1, 4, 4]
LR: [1, 2]
Pairs: [1, 2, 3, 3, 4, 4]
Leftovers: [-1, -1, 4]

Pile: [1, 1, 2, 2]
LR: [1]
Pairs: [2] (two right 1's and two simple 2's, so only 2's make a pair)
Leftovers: [1, 1]

Pile: [5, -10, 5, 10, -10, 10]
LR: [10, 20]
Pairs: [5, 10, 10]
Leftovers: []

Pile: [-6, 7, -9, 3, 4, -6, 4, -9, 8]
LR: [6, 9, 4]
Pairs: []
Leftovers: [-6, 7, -9, 3, 4, -6, 4, -9, 8]

Pile: []
LR: [1, 2]
Pairs: []
Leftovers: []

```

# Answer
> 5 votes
# 05AB1E, ~~40~~ 27 bytes

```
.¡Ä}εDÄIåài{γζðδKë2ô]€`é.¡g

```

Inputs are in the order `Pile, LR` and outputs in the order `Leftovers, Pairs` in the format (`[[1],[2],[3]], [[1,1], [-2,2], [3,3]]`).

-13 bytes by porting *@AZTECCO*'s Japt answer, so make sure to upvote him!

Try it online or verify all test cases.

**Explanation:**

```
.¡ }              # Group the (implicit) input integer-list `Pile` by:
  Ä               #  Their absolute values
    ε             # Then map each group to:
          i       #  If
       Iåà        #  any values of the second input-list `LR`
     DÄ           #  is in the current group's absolute values:
           {      #   Sort the values in the group
            γ     #   And then group it on subsequent equal values
             ζ    #   Zip/transpose to create pairs of positive & negative values,
                  #   with space as default filler if the lists are of unequal length
              ðδK #   And remove all those spaces
          ë       #  Else:
           2ô     #   Split split the group into parts of size 2
    ]             # Close the if-else statement and map
     €`           # Flatten each inner list once to remove the groups again
       é          # Sort each inner list by length
        .¡g       # And also group by length
                  # (after which this result is output implicitly as result)

```

# Answer
> 5 votes
# APL (Dyalog Unicode), 62 bytes (SBCS)

```
,⌿⎕{⍺∊⍺⍺:((∊|⍴¨⍺××)n)(⍺/⍨0⌈2÷⍨≢⍵↓⍨n←⍺÷⍨+/⍵)⋄/∘⍺¨⌽0 2⊤≢⍵}⌸⍨∘|⍨⎕

```

Try it online!

The initial "straightforward" version was around 76 bytes long; folks at The APL Orchard helped me golf it substantially to the snippet above. Thanks!

## How does it work?

*Explanations written for the original "straightforward" version, not for the most golfed version above.*

At a high level, the  Key operator groups items from the pile such that we get an absolute-valued item as a key on the left and an array of all its occurences (with or without a minus sign) on the right.

```
┌─┬──────────┐
│3│3 3 3 3   │
├─┼──────────┤
│2│¯2 2      │
├─┼──────────┤
│4│4 4 4 4 4 │
├─┼──────────┤
│1│¯1 ¯1 1 ¯1│
└─┴──────────┘

```

Then we essentially do:

```
if the key is in the list of LRs:
    compute leftovers and pairs for LRs
else:
    compute leftovers and pairs for normal socks

```

After doing that for each row, we concatenate the columns (given to us in `leftovers, pairs` order) to a single array each and return those two arrays as a final result.

### Leftovers for LRs:

We sum the items on the right and divide them by the key; this gives us a number of leftovers; we absolute-value that (since it can be negative, eg. `-1 -1 1 -1 -> -2`) and then replicate the key (with the right sign applied) that many times.

```
¯2 ¯2 2 ¯2   ⍝ +/ sum:
¯4           ⍝ ÷2 divide by key:
¯2           ⍝ |  absolute value:
2            ⍝ = number of times to replicate

¯2           ⍝ ×  get sign
¯1           ⍝ ×2 multiply by key:
¯2           ⍝ = item to replicate

2/¯2 ---> ¯2 ¯2

```

### Pairs for LRs:

We sum the items on the right, divide that by the key and get the absolute value. That gives us number of leftovers. We subtract that from the original number of items, which gives us the number of paired items. We divide that by two to get the number of pairs. We repeat the key that many times (it's guaranteed to be positive).

```
¯2 ¯2 2 ¯2   ⍝ +/    sum:
¯4           ⍝ ÷2    divide by key:
¯2           ⍝ |     absolute value:
2            ⍝ (≢⍵)- subtract from count of items:
2            ⍝ ÷2    divide by 2:
1            = number of times to replicate

1/2 ---> 2

```

### Leftovers for normal socks:

We count the items, take remainder after division by 2 (either 0 or 1 odd sock can be the leftover). By problem definition we're guaranteed this number is not negative. We repeat the key that many times.

```
2 2 2        ⍝ ≢  count:
3            ⍝ 2| mod by 2:
1            ⍝ = number of times to replicate

1/2 ---> 2

```

### Pairs for normal socks:

We count the items, divide by two and round down. We repeat the key that many times.

```
2 2 2        ⍝ ≢  count:
3            ⍝ ÷2 divide by 2:
1.5          ⍝ ⌊  round down
1            ⍝ = number of times to replicate

1/2 ---> 2

```

# Answer
> 3 votes
# , ~~138 134~~ 138 bytes

-2 bytes thanks to Giuseppe; +4 bytes to adhere to the output format

```
f=function(p,l,a={},b=a,z=p[1],w=abs(z))`if`(any(p),`if`(m<-match(z-2*z*w%in%l,y<-p[-1],0),f(y[-m],l,c(a,w),b),f(y,l,a,c(b,z))),list(a,b))

```

Try it online!

Recursive function.

Takes the first sock `z` off the pile, and searches the pile for either `z` or `-z` depending on whether `w=abs(z)` is in `LR`. If a match is found, adds `w` to the list of pairs and removes both socks from the pile before recursing, else adds `z` to the list of leftovers and recurses.

Ungolfed:

```
# p is pile of socks
# l is vector of LR socks
# a will be vector of pairs
# b will be vector of leftovers
f = function(p, l, a={}, b=a, z=p[1],  # initialize a and b as NULL; z is first sock of pile
               w=abs(z)}
  if(any(p)){                          # check that p is not empty (would mean end of recursion)
    y <- p[-1]                         # y is all socks except the first
    m <- match(z - 2*z*w%in%l,         # look for either z or -z depending on whether w=abs(z) is in l
             y, 0)                     # find position of first match in y; if no match is found, return 0
    if(m){                             # if a match was found
      f(y[-m], l, c(a, w), b)          # append w to a, remove the matching sock from y, and recurse
      } else {
        f(y, l, a, c(b, z))            # else append z to b and recurse
      }
    } else {
      list(a,b)                        # when p is empty, return a and b
  }
}

```

# Answer
> 3 votes
# Japt, ~~28~~ ~~31~~ 23 bytes

```
üa c_ca øV ?ZüÎyf:ZòÃül

```

Try it

Takes input as pile, labels.
Returns leftovers, every pair list.

```
üa                    group by same absolute value
   c_           Ã     for each group:
     ca øV ?              if labeled (using absolute values)
        ZüÎyf          - group by sign and transpose (saving only truthy values)
            :Zò        :  else slice every 2 elements
                ül    group the result by length

```

~~g1\_cg1~~ no needed

# Answer
> 2 votes
# Jelly, ~~25~~ 23 bytes

```
AĠị$ŒHAf⁹Ɗ?Z$ƙ$ẎL=¥ƇⱮØ½

```

Try it online!

A dyadic link taking the socks as its left argument and LR list as its right. Returns a list of lists with the leftovers as the first sublist (each wrapped on its own in a list) and the pairs as the second sublist.

Thanks to @JonathanAllan for saving a byte!

## Explanation

```
              $          | Following as a monad:
A           $ƙ           | - For each group of the sock list defined by the absolute of the sock list, do the following as a monad:
         Ɗ?              |   - If the following is non-empty:
      A                  |     - Absolute
       f⁹                |     - Filtered to keep only elememts in LR list
   $                     |   - Then:
 Ġị                      |      - Split into groups based on sign
    ŒH                   |   - Else: split into two (almost) equal halves
           Z             |   - Transpose
                Ẏ        | Join outermost lists together
                   ¥ƇⱮØ½ | Filter the list using the following as a dyad and each of [1, 2] as the right argument:
                 L       | - Length
                  =      | - Equals right argument

```

# Answer
> 2 votes
# JavaScript (ES6), 85 bytes

Takes input as `(pile)(lr)`, where *pile* is an array and *lr* is an object.

Returns the pairs as a list and the leftovers as an object which may contain zero-count items.

```
a=>L=>[a.filter(x=>s[i=L[A(x)]?-x:x]?s[i]--:!(s[x]=-~s[x]),s={},A=Math.abs).map(A),s]

```

Try it online!

---

# JavaScript (ES6), 99 bytes

Takes input as `(pile)(lr)`, where *pile* is an array and *lr* is an object.

Returns two lists.

```
a=>L=>[a.filter(x=>~(i=s.indexOf(L[A(x)]?-x:x))?s.splice(i,1):!s.push(x),s=[],A=Math.abs).map(A),s]

```

Try it online!

# Answer
> 1 votes
# Zsh, ~~179~~ 177 bytes

```
typeset -A p l
for x (`<&0`)((l[$x]++))
for k;((p[$k]=l[$k]<l[-$k]?l[$k]:l[-$k],l[$k]-=p[$k],l[-$k]-=p[$k]))
a=({,-}$^@)
for k (${(k)l:|a})((p[$k]=l[$k]/2,l[$k]%=2))
typeset p l

```

Try it online!

Takes the sock pile on stdin, and the achiral pairs as arguments.

Due to Zsh's lack of filtering and mapping tools, we simply loop over the pile incrementing to create a `sock->count` map. Thankfully zero-count items are allowed; otherwise this would probably be in the 220-byte range, since filtering by value isn't easily done.

```
typeset -A p l            # declare p, l as associative arrays
for x (`<&0`)((l[$x]++))  # for each sock in the pile, increment that key of the leftover array
for k; {                  # for each argument (an achiral pair)
  ((p[$k]=l[$k]<l[-$k]?l[$k]:l[-$k]))  # set the paired array to the minimum of the l/r socks
  ((l[$k]-=p[$k],l[-$k]-=p[$k]))       # decrement the leftovers we just paired
}
a=({,-}$^@)               # if our achiral pairs were (2 3), set a=(2 -2 3 -3)
for k (${(k)l:|a})        # take the keys of the leftovers, remove all elements of a
  ((p[$k]=l[$k]/2,l[$k]%=2))    # divmod gets us the pairs and leftovers for the chiral socks
typeset p l               # using typeset to print the current definitions is shorter than
                          # using something like '<<<${(kv)p},${(kv)l}'

```

# Answer
> 1 votes
# Perl 5, 151 bytes

```
sub f{
  $_="@{[sort{abs$a<=>abs$b}sort@{+pop}]}";
  ($p,@p)=sub{push@p,$1;''};
  for$l(@_){1while s/-($l) +$l\b/&$p/e}
  s/\b(\d+) \1\b/$1~~\@_?$&:&$p/ge;
  "@p",$_
}

```

Try it online!

...151 bytes with `\n\s+` removed.

# Answer
> 1 votes
# Python 3.7, 183 Bytes

Try it online! Link includes uncommented version of code with the five test cases.

```
def f(p,l):
 a,b=[],[]          #a = pairs, b = loners
 while p:           #iterate through pile
  i=p.pop(0)        #remove and look at first sock in pile
  n=abs(i)          #Prepare to compare abs(i) to LR list
  #If there is a +ve/-ve pair from LR list
  if(-i in p)*(n in l):
   a+=n,            #Add to pairs
   p.remove(-i)     #Remove other half of pair from the pile
  #If there is a +ve/+ve pair not from LR list
  elif(n in p)*(not n in l):
   a+=n,            #Add to pairs
   p.remove(i)      #Remove other half of pair from the pile
  #Otherwise, add sock to loner list
  else:b+=i,
 return a,b         #Return the completed lists

```

This is my first attempt at a code golf challenge so feel free to comment on any obvious optimizations I have missed.

Cheers

# Answer
> 0 votes
# Charcoal, 58 bytes

```
Ｉ⟦↔Φθ⎇№η↔ι›№…θκ±ι№…θκι﹪№…θκι²Φθ⎇№η↔ι›№…θ⊕κι№θ±ι›﹪№θι²№…θκι

```

Try it online! Link is to verbose version of code. Outputs two double-spaced lists of newline-separated socks in a reproducible but unobvious order. Explanation:

```
Ｉ⟦

```

Cast both lists of socks to string for implicit print and double-space between the lists.

```
↔Φθ

```

Find the matched socks and print their absolute values so that we don't mix left and right socks in the output.

```
⎇№η↔ι

```

Is this a self-pairing sock?

```
›№…θκ±ι№…θκι

```

If not then it matches if there have been more opposite socks in the list so far (not including this sock, so at least as many opposite socks including this sock).

```
﹪№…θκι²

```

If it is then it matches if there have been an odd number of this type of sock so far (not including this sock). (If there are an odd number in total then this sock is actually matched against the next sock of this type.)

```
Φθ

```

Find the mismatched socks.

```
⎇№η↔ι

```

Is this a self-pairing sock?

```
›№…θ⊕κι№θ±ι

```

If not it is mismatched if the number of this type of sock so far (including this sock) is greater than the total number of opposite socks.

```
›﹪№θι²№…θκι

```

If it is then it is mismatched if this is the first of a total number of odd socks of this type.

Explanation for which socks get output as (mis)matches:

```
[[3, 3, -2, 4, -1, -1, 1, 4, 4, 3, 2, 3, -1, 4, 4], [1, 2]]

```
* The `1` gets output as a match for the first `-1` and the second and third `-1` are output as mismatches.
* The `2` gets output as a match for the `-2`.
* The second and fourth `3`s get output as matches for the first and third `3`s.
* The second and fourth `4`s get output as matches for the third and fifth `4`s, while the first `4` is a mismatch.

# Answer
> 0 votes
# Ruby, ~~143~~ 95 bytes

```
->a,l,*b{c=[];(s=a.index [w=a.pop,-w][l.count z=w.abs])?(a.slice!s;b<<z):c<<w while a[0];[b,c]}

```

Try it online!

---
Tags: code-golf
---


# Question
Title: Smallest image containing one of every RGB color
I'm not sure if this kind of golf is allowed, but here it is.

Your objective is to create an image containing one pixel of every possible RGB color. The image with the smallest file size wins.

Rules:

* The image must be a PNG.
* The image must contain *exactly* one of every possible RGB color.
* Acceptable image dimensions are:

```
1x16777216
2x8388608
4x4194304
8x2097152
16x1048576
32x524288
64x262144
128x131072
256x65536
512x32768
1024x16384
2048x8192
4096x4096
8192x2048
16384x1024
32768x512
65536x256
131072x128
262144x64
524288x32
1048576x16
2097152x8
4194304x4
8388608x2
16777216x1

```

Example Image

# Answer
> 7 votes
# ~~49683~~ ~~49280~~ 49131 bytes

Generated by this Python code. I designed the PNG scanlines by hand to be encoded using repetitions of short sequences that compress well. I’ve now written enough of a custom DEFLATE encoder to let me decide where to split the compressed blocks (saving 149 bytes compared to zlib).

```
import itertools
import struct
import zlib

def lsb(b, n):
    assert 0 <= n < 1 << b
    return f"{n:0{b}b}"[::-1] if b else ""

def huffman(lengths, letter):
    code = sum(
        1 << lengths[letter] - length
        for other_letter, length in lengths.items()
        if (length, other_letter) < (lengths[letter], letter)
    )
    return f"{code:0{lengths[letter]}b}"

def literal(letter):
    assert 0 <= letter < 256
    return huffman(literals, letter)

def end():
    return huffman(literals, 256)

def match(length, distance):
    assert 3 <= length <= 258
    assert 1 <= distance <= 32768

    if length == 258:
        bits = huffman(literals, 285)
    else:
        i = max(0, (length - 3).bit_length() - 3)
        bits = huffman(literals, 4 * i + 257 + (length - 3 >> i)) + lsb(
            i, length - 3 & ~(~0 << i)
        )

    j = max(0, (distance - 1).bit_length() - 2)
    bits += huffman(distances, 2 * j + (distance - 1 >> j)) + lsb(
        j, distance - 1 & ~(~0 << j)
    )

    return bits

code_length_order = [16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15]

def encode_lengths():
    hlit = max(literals) + 1 - 257
    hdist = max(distances) + 1 - 1
    hclen = max(map(code_length_order.index, code_lengths)) + 1 - 4
    bits = lsb(5, hlit) + lsb(5, hdist) + lsb(4, hclen)
    for i in code_length_order[: hclen + 4]:
        bits += lsb(3, code_lengths.get(i, 0))
    for length, group in itertools.groupby(
        [literals.get(i, 0) for i in range(hlit + 257)]
        + [distances.get(i, 0) for i in range(hdist + 1)],
        lambda length: length,
    ):
        n = len(list(group))
        while length == 0 and 18 in code_lengths and n >= 11:
            bits += huffman(code_lengths, 18) + lsb(7, min(n - 11, 127))
            n -= min(n - 11, 127) + 11
        while length == 0 and 17 in code_lengths and n >= 3:
            bits += huffman(code_lengths, 17) + lsb(3, min(n - 3, 7))
            n -= min(n - 3, 7) + 3
        # not implemented: 16 (copy previous code)
        bits += huffman(code_lengths, length) * n
    return bits

png_header = struct.pack(
    "!IIBBBBB",
    2 ** 16,  # width
    2 ** 8,  # height
    8,  # bit depth
    2,  # color type
    0,  # compression method
    0,  # filter method
    0,  # interlace method
)

zlib_header = struct.pack(
    "!BB",
    8 | 7 << 4,  # compression method, compression info
    26 | 0 << 5 | 3 << 6,  # check bits, preset dictionary, compression level
)

literals = {1: 2, 2: 4, 256: 4, 268: 4, 284: 4, 285: 1}
distances = {2: 1, 18: 1}
code_lengths = {0: 3, 1: 2, 2: 3, 4: 2, 18: 2}
bits = "0"  # start non-final block
bits += lsb(2, 2)  # compressed with dynamic Huffman codes
bits += encode_lengths()
bits += literal(1) + literal(1) + literal(1) + literal(2) + literal(1) + literal(2)
bits += 2 * match(258, 3)
bits += match(248, 3)
bits += 5 * (
    match(258, 768) + match(258, 3) + 42 * (match(258, 768) + 2 * match(258, 3))
)
bits += match(258, 768) + match(258, 3) + 39 * (match(258, 768) + 2 * match(258, 3))
bits += match(17, 3)
bits += end()

literals = {1: 3, 256: 3, 264: 3, 279: 3, 285: 1}
distances = {0: 1, 2: 1}
code_lengths = {0: 3, 1: 2, 3: 2, 17: 3, 18: 2}
bits += "1"  # start final block
bits += lsb(2, 2)  # compressed with dynamic Huffman codes
bits += encode_lengths()
bits += 96780 * match(258, 1)
bits += match(105, 1)
bits += literal(1) + literal(1)
bits += 762 * match(258, 3)
bits += match(10, 3)
bits += 96780 * match(258, 1)
bits += match(102, 1)
bits += end()

bits += -len(bits) % 8 * "0"
compressed = int(bits[::-1], 2).to_bytes((len(bits) + 7) // 8, "little")

decompressed = zlib.decompress(compressed, wbits=-15)
assert decompressed == bytes(
    [1, *(2 ** 8) * [1, 1, 2, *(2 ** 8 - 1) * [1, 2, 2]]]
    + (2 ** 7 - 1) * [2, *2 ** 16 * [2, 2, 2]]
    + [2, *2 ** 16 * [2, 1, 1]]
    + (2 ** 7 - 1) * [2, *2 ** 16 * [2, 2, 2]]
)

zlib_checksum = struct.pack("!I", zlib.adler32(decompressed))
png_data = zlib_header + compressed + zlib_checksum

png = b"\x89PNG\r\n\x1a\n"
for type, data in [(b"IHDR", png_header), (b"IDAT", png_data), (b"IEND", b"")]:
    crc = 0xFFFFFFFF
    for byte in type + data:
        crc ^= byte
        for bit in range(8):
            crc = 0xEDB88320 * (crc & 1) ^ crc >> 1
    crc ^= 0xFFFFFFFF
    png += struct.pack("!I4s", len(data), type) + data + struct.pack("!I", crc)

print(len(png))
with open("rgb.png", "wb") as f:
    f.write(png)

```

Try it online!

(Note: many PNG readers accept an image missing the `IEND` chunk, but it is required by the PNG specification so I have included it.)

# Answer
> 2 votes
# 256x65536, 49909 bytes

In my experience Google Chrome is the best tool to view this image.

The red channel starts at 255 in the first row and decreases by 1 each row.
The green channel slowly decreases from 255 to 0 in every row and the blue channel repeatly decreases from 255 to 0.

Generated by the following code in Python 3 with numpy and imageio:

```
import os

import imageio
import numpy as np

FILENAME = 'out.png'
DTYPE = np.uint8

values = np.arange(255, -1, -1, dtype=DTYPE)
image = np.empty((256, 256**2, 3), dtype=DTYPE)

image[..., 0] = values[:, np.newaxis]  # r
image[..., 1] = np.repeat(values, 256) # g
image[..., 2] = np.tile(values, 256)   # b

# Verify that all colors are present (slow)
# assert len(np.unique(image.reshape(256**3, 3), axis=0)) == 256 ** 3

imageio.imwrite(FILENAME, image)
os.system('wc ' + FILENAME)

```

I tried to reduce the file size with zopflipng, but even after 50 minutes of running it provided no improvement.

---
Tags: code-challenge, image-processing
---


title: (1) Determine the amount of statues

text:
# Question
Title: (1) Determine the amount of statues
Inspired by this stack of little statues that are currently on my desk at work, given to me by my colleagues from Sri Lanka when they visited The Netherlands:

This is split into two different challenges due to popular demand:
Part 1) Determine the amount of statues (this challenge)
Part 2) Can the statues be stacked?

## Challenge 1:

**Input:**

\\$statues\\$: a multi-line string (or character matrix), containing only the characters  `\n|-#` (where the `|-#` can be other characters of your own choice)

**Output:**

The amount of statues in the input.

**Statues input example:**

```
      ##|
####    |
# ##
#  #  |##
----  |######
      |   ###
|##   |##   #
|## - |######
    # |####

```

The `|` and `-` represent the bases of the statues. So with the input above, we'll have the following statues:

```
       ####
       ## #
       ## ##
####   #  ##
# ##  ## ###  ##      #
#  #  ## ###  ##  #   #
----  ------  --  -  --

```

So the output will be `5`.

## Challenge rules:

* You can use a different consistent character other than `#`, `-`, and/or `|` for the statue if you want ( `\n` are mandatory, though). Please state which one you've used in your answer if it's different than the defaults.
* You are allowed to take the \\$statues\\$ input in any reasonable format. Can be a multi-line string, a list/array/stream of strings, a character matrix, etc.
* You are allowed to pad the statues input with trailing spaces so it's a rectangle.
* You can assume statues are always separated by at least one space or blank line from one-another, so something like `#|#|` or `#||#` won't be in the input.
* You can assume the statues will only have a base at ones side, so a statue like this won't be in the input:

```
##|
##|
--

```
* It is possible that a smaller statue is within the rectangular boundaries of another oddly shaped statue. For example, this is possible:

```
# ##
- ##
  ##
####
# #
----

```
* Statues will never be inside of each other, though. So something like this won't be in the input:

```
 #####
##   #
#  # #
# ## ##
# -- ##
#     #
##    #
-------

```
* You can assume the base determines the width of a statue. So you won't have statues like these in the input:

```
#######
 #####
 ####     ###
  ---     --

```

## General rules:

* This is , so shortest answer in bytes wins.
Don't let code-golf languages discourage you from posting answers with non-codegolfing languages. Try to come up with an as short as possible answer for 'any' programming language.
* Standard rules apply for your answer with default I/O rules, so you are allowed to use STDIN/STDOUT, functions/method with the proper parameters and return-type, full programs. Your call.
* Default Loopholes are forbidden.
* If possible, please add a link with a test for your code (i.e. TIO).
* Also, adding an explanation for your answer is highly recommended.

## Test cases:

```
      ##|
####    |
# ##
#  #  |##
----  |######
      |   ###
|##   |##   #
|## - |######
    # |####

Output: 5
__________________________________________________

# ##
- ##
  ##
####
# #
----

Output: 2
__________________________________________________

      #
|###  #
| #   #
|#### -

Output: 2
__________________________________________________

--- ##|
### ##|
###
### |#

Output: 3
__________________________________________________

####             #####|
# ##
###              |#           |#
#####            |#           |##
-----            |#           |#
                 |#
                 |#
                 |#

Output: 4
__________________________________________________

|# |# |# |# |# #| #| #|

Output: 8
__________________________________________________

|##
|   ##
|#  --

Output: 2
__________________________________________________

      |##
----  |####
# ##
###   |#
      |#  ###|
      |#    #|
      |#   ##|
      |#

Output: 4
__________________________________________________

- |##
#      #
  #| ###
  #| ---

Output: 4
__________________________________________________

#
####
----

--
 #

Output: 2
__________________________________________________
##
##
--

--
##
##

Output: 2

```

# Answer
# Jelly, 11 bytes

```
,ZŒrFċ¥"Ø^S

```

Try it online!

The statues have a polished bottom, so they use `/` instead of `-` and `\` instead of `|`. The input is a list of strings that must be the same length.

## Explanation

```
,ZŒrFċ¥"Ø^S   Main monadic link
,             Pair the input
 Z            with the input transposed
  Œr          Run-length encode everything
       "      Zip with
      ¥       (
    F           Flatten left argument
     ċ          Count the occurences of right argument
      ¥       )
        Ø^    with "/\"
          S   Sum

```
> 3 votes

# Answer
# 05AB1E, 15 bytes

```
„-|v€Åγ˜y¢Iø}Š+

```

Try it online!

**Commented:**

```
„-|              # push string literal "-|"
   v        }    # iterate over this string
    €Åγ          #   run-length encode each line of the input / transposed input
                 #   this pushes the chunk elements and the chunk lengths
       ˜         #   flatten the list
        y¢       #   count the chunks of the current character
          Iø     #   push the transposed input to the stack for the second iteration
             Š   # triple-swap: move the transposed input to bottom
              +  # sum both counts

```
> 6 votes

# Answer
# Ruby, ~~93~~ ~~86~~ ~~61~~ 58 bytes

*Saved seven bytes, thanks to Razetime!*
*Saved three bytes, thanks to ovs!*

```
->s{((s.transpose*"").scan(/\|+/)+(s*"").scan(/-+/)).size}

```

Try it online!

Takes input as a matrix of characters.
> 5 votes

# Answer
# Retina 0.8.2, 37 bytes

```
-+|(?<=(.)*)¦(?!.*¶(?<-1>.)*(?(1)$)¦)

```

Try it online! Uses `¦` instead of `|`. Explanation:

```
-+|

```

Count runs of `-`s, or...

```
(?<=(.)*)¦(?!.*¶(?<-1>.)*(?(1)$)¦)

```

... any `¦`s which do not have a `¦` directly underneath them on the next line. This uses a .NET balancing group to ensure that the two `¦`s are vertically aligned.
> 5 votes

# Answer
# Perl 5 `(-p)`, ~~50~~, 30 bytes

Using `I` instead of `|` (first rule), and padding input with trailing spaces so it's a rectangle (third rule).

```
/
/;$_=()=/-+|I(?!.{@{-}}I)/gs

```

Try it online!

How

* `/-+|I(?=.{@{-}}I)/gs` to match `-` runs or `|` not followed by `|` bellow
* `(()=...)` list context
* `$_=` list is coerced to int size

Saved 13 bytes negating the lookahead, similarly to @Neil's retina answer.
> 3 votes

# Answer
# Charcoal, 36 bytes

```
ＷＳ«Ｆι«Ｆ²⊞υ›⁼κ§-|λ⁼⊟ＫＤ²✳∨⊗λ⁴κκ»⸿»⎚ＩΣυ

```

Try it online! Link is to verbose version of code. Finally managed to beat Retina. Explanation:

```
ＷＳ«

```

Repeat on each line of input.

```
Ｆι«

```

Repeat on each character.

```
Ｆ²⊞υ›⁼κ§-|λ⁼⊟ＫＤ²✳∨⊗λ⁴κ

```

If the character is a `-` or a `|`, then check whether the character to the left is also a `-` or character above is also a `|` as appropriate. Record whether this character therefore begins a new statue.

```
κ»⸿»

```

Print the character and start a new line for every line of the input.

```
⎚ＩΣυ

```

Print the total number of statues seen.

My previous 38-byte approach used direct calculation:

```
ＷＳ⊞υιＩΣ⁺Ｅυ⁻№ι-Ｌ⌕Ａι--ＥＥθ⭆υ§λκ⁻№ι|Ｌ⌕Ａι||

```

Try it online! Link is to verbose version of code. Requires padded input. Explanation: Each base of each horizontal statue contains a number `n` `-`s. But it also contains `n-1` `--`s, if you include overlaps, which the `FindAll` command does. Therefore the number of horizontal statues in a line is the number of `-`s minus the number of overlapping `--`s. It then remains to transpose the input and count the difference between the number of `|`s and the number of overlapping `||`s.
> 2 votes

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


title: Validating a Battleship board

text:
# Question
Title: Validating a Battleship board
Do you know the game Battleship? Well, I want to play with my little brother, but before we can begin we need to set up our ships on the board. This is your input.

Now, we need to check that the ships that we set up are valid. This is where you come in to help. Your task is to write a program or function which checks whether the given 2d array (your board/input) is a valid board or not.

The input will be a 2d array, where `1` represents part of a ship and `0` represents part of the ocean.

**The rules:**

* There must be:
    + One battleship (size 4)
    + Two cruisers (size 3)
    + Three destroyers (size 2)
    + Four submarines (size 1)
* Any additional ships are not allowed, and neither are missing ships
* Each ship must be either vertical or horizontal (aside from submarines, which are a single grid space)
* The ships cannot overlap, but may be adjacent

in addition, you must solve this with a `BF` function (naturally the class will be called `BF`) which receives the 2d array(input) and uses a `validate` function. Afterward, you are free to manipulate the 2d array however you want and add any functions that you want.

here are some more examples(inputs) that your code must pass: is valid:

```
 {1,1,1,1,0,0,0,0,0,0},
 {1,1,1,1,0,0,0,0,0,0},
 {1,1,1,1,0,0,0,0,0,0},
 {1,1,1,1,0,0,0,0,0,0},
 {1,1,1,1,0,0,0,0,0,0},
 {0,0,0,0,0,0,0,0,0,0},
 {0,0,0,0,0,0,0,0,0,0},
 {0,0,0,0,0,0,0,0,0,0},
 {0,0,0,0,0,0,0,0,0,0},
 {0,0,0,0,0,0,0,0,0,0},

```

InvalidShapeOfBoat which is invalid-\>

```
 {1,0,0,0,0,1,1,0,0,0},
 {1,0,0,0,0,0,0,0,1,0},
 {1,1,0,0,1,1,1,0,1,0},
 {0,0,0,0,0,0,0,0,0,0},
 {0,0,0,0,0,0,0,0,1,0},
 {0,0,0,0,1,1,1,0,0,0},
 {0,0,0,0,0,0,0,0,1,0},
 {0,1,0,1,0,0,0,0,0,0},
 {0,1,0,0,0,0,0,1,0,0},
 {0,0,0,0,0,0,0,0,0,0},

```

wrong ships, result is false-

```
 {1,0,0,0,0,1,1,0,0,0},
 {1,0,1,0,0,0,0,0,1,0},
 {1,0,1,0,1,1,1,0,1,0},
 {1,0,0,0,0,0,0,0,0,0},
 {0,0,0,0,0,0,0,0,1,0},
 {0,0,0,0,1,1,1,0,0,0},
 {0,1,0,0,0,0,0,0,1,0},
 {0,0,0,1,0,0,0,0,0,0},
 {0,0,0,0,0,0,0,1,0,0},
 {0,0,0,0,0,0,0,0,0,0},

```

missing ships, is false-\>

```
 {0,0,0,0,0,1,1,0,0,0},
 {0,0,1,0,0,0,0,0,1,0},
 {0,0,1,0,1,1,1,0,1,0},
 {0,0,0,0,0,0,0,0,0,0},
 {0,0,0,0,0,0,0,0,1,0},
 {0,0,0,0,1,1,1,0,0,0},
 {0,0,0,0,0,0,0,0,1,0},
 {0,0,0,1,0,0,0,0,0,0},
 {0,0,0,0,0,0,0,1,0,0},
 {0,0,0,0,0,0,0,0,0,0},

```

check contact, is true-\>

```
 {1,1,1,0,0,0,0,0,0,0},
 {1,1,0,0,0,0,0,0,1,0},
 {1,1,0,0,1,1,1,0,1,0},
 {1,0,0,0,0,0,0,0,0,0},
 {1,0,0,0,0,0,0,0,1,0},
 {0,0,0,0,1,1,1,0,0,0},
 {0,0,0,0,0,0,0,0,1,0},
 {0,0,0,0,0,0,0,0,0,0},
 {0,0,0,0,0,0,0,1,0,0},
 {0,0,0,0,0,0,0,0,0,0},

```

check another one with contact-\>

```
 {1,1,1,0,0,0,0,0,0,0},
 {1,1,0,0,0,0,0,0,1,0},
 {1,1,0,0,1,1,1,0,1,0},
 {1,0,0,0,0,0,0,0,0,0},
 {1,0,0,0,0,0,0,0,1,0},
 {0,0,0,0,1,1,1,0,0,0},
 {0,0,0,0,0,0,0,0,1,0},
 {0,0,0,0,0,0,0,0,0,0},
 {0,0,0,0,0,0,0,1,0,0},
 {0,0,0,0,0,0,0,0,0,0},

```

check invalid, is false-\>

```
 {0,1,1,1,0,0,0,0,0,0},
 {0,0,0,1,1,1,0,0,0,0},
 {0,1,1,1,0,0,0,0,0,0},
 {0,0,0,1,1,1,0,0,0,0},
 {0,1,1,1,0,1,1,0,0,0},
 {0,1,0,0,0,0,1,1,0,0},
 {0,0,0,0,0,0,0,0,0,0},
 {0,0,0,0,0,0,0,0,0,0},
 {0,0,0,0,0,0,0,0,0,0},
 {0,0,0,0,0,0,0,0,0,0},

```

random board which is false-\>

```
{0,1,0,0,0,0,0,0,0,0},
 {1,1,1,1,0,0,0,0,0,0},
 {1,0,1,1,1,0,0,0,0,0},
 {1,1,0,0,0,0,0,0,0,0},
 {1,1,0,0,0,0,0,0,0,0},
 {0,1,0,0,0,0,0,0,1,0},
 {0,0,1,0,0,0,0,0,1,0},
 {0,0,0,0,0,0,0,0,0,0},
 {0,0,0,0,1,0,0,0,0,0},
 {0,0,0,0,1,0,0,0,0,0},

```

Who's code will be the shortest byte solution that passes all these examples successfully?! Good luck. ;)

Any language is allowed.

on the 16th I will award the winner with a nice green tick:)

# Answer
# JavaScript (ES6),  ~~162~~  158 bytes

Returns `0` if the grid is invalid, or a positive integer otherwise.

```
m=>(o=0,g=u=>m.some((r,y)=>r.some((v,x)=>v&&[0,1].map(d=>(r=(w,X=x+!d*w,R=m[y+d*w]||0)=>R[X]&&R[R[X]--,u&(k=1<<w*3)*7&&g(u-k),r(-~w),X]++)``)))|u||++o)(668)*o

```

Try it online!

### Commented

```
m => (                       // m[] = input matrix
  o = 0,                     // o = result
  g = u =>                   // g is a recursive function taking a bit mask u
                             // holding the ship counters on 4 x 3 bits
  m.some((r, y) =>           //   for each row r[] at position y in m[]:
    r.some((v, x) =>         //     for each value v at position x in r[]:
      v &&                   //       abort if v is not set
      [0, 1].map(d =>        //       otherwise, look for a horizontal ship (d = 0)
        (                    //       or a vertical ship (d = 1):
          r = (              //         r is a recursive function taking:
            w,               //           w = ship width - 1
            X = x + !d * w,  //           X = position of the cell in ...
            R = m[y + d * w] //           ... R[] = row of the cell
                || 0         //           (force it to 0 if undefined)
          ) =>               //
          R[X] &&            //           abort if R[X] is not set
          R[                 //
            R[X]--,          //           otherwise, set the cell to 0
            u & 7 *          //           if there's still at least one ship of
            (k = 1 << w * 3) //           width w to be found in the grid:
            && g(u - k),     //             do a recursive call to g with u updated
            r(-~w),          //           do a recursive call to r with w + 1
            X                //
          ]++                //           restore the cell afterwards
        )``                  //         initial call to r with u zero'ish
      )                      //       end of map()
    )                        //     end of some()
  )                          //   end of some()
  | u || ++o                 //   increment o if the grid has been cleared and all
                             //   boats have been found
)(668)                       // initial call to g with u = 668 (001 010 011 100)
* o                          // multiply by o

```
> 4 votes

# Answer
# , 211 bytes

```
v=function(b,f=c(3:1,2,1,1))`if`(any(f),{any(sapply(list(b,t(b)),function(m)any(apply(h<-which(m[1:(dim(m)[1]-f[1]),]>0,T),1,function(x)`if`(all(m[y<-t(x+rbind(0:f[1],0))]),{m[y]=0;v(m,f[-1])},F)))))},sum(b)==4)

```

Try it online!

**How?**
Pseudo-code version:

```
# recursive function:
validate_battleships=
v=function(board,fleet_without_submarines)
    if there's nothing left in the fleet,
    and the board contains the right number of submarines:
        return(TRUE)
    else if any of these:
        try all positions:
            if we can place the first ship in the fleet:
                return result of recursive call
                after removing this ship from the board and the fleet
        return(TRUE)
    else return(FALSE)

```

And the actual, ungolfed  code:

```
validate_battleships=
v=function(b,f=c(3:1,2,1,1))        # f=fleet=ship sizes minus 1, without submarines
  `if`(any(f),{                     # if there are any ships in the fleet:
    any(                            # return TRUE if any of these are true:
      sapply(list(b,t(b)),          # test the board and the transpose of the board (to try horizontal & vertical ship-placements)
        function(m)any(             # check if any of these are true:
          apply(h<-                 # test each nonzero position on the board (excluding the last rows that would make the ship go off the edge)
            which(m[1:(dim(m)[1]-f[1]),]>0,T),1,
              function(x)           # consider the first ship: f[1] (first item in fleet argument)
                `if`(all(m[y<-t(x+rbind(0:f[1],0))]),
                                    # if all the adjacent positions up to the ship size are nonzero (so we can place this ship),
                  {m[y]=0;          # set all these positions to zero
                   v(m,f[-1])}      # and return the result of a recursive call without this ship;
                ,F)                 # otherwise return FALSE
                ))))}
  ,sum(b)==4)                       # if there were no ships in the fleet, check that the nonzero positions on the board
                                    # add-up to 4 (number of submarines): if they do, return TRUE.

```
> 2 votes

# Answer
Here is my answer in Java, I am definitely not skilled enough to get it down to a minimal amount of bytes and I prefer not to say(shortest byte solution for this code is down at the bottom of this post, credit to @ceilingcat for getting my code down to **482 bytes**:P) try it, it works!

thanks to ceilingcat with the **482bytes** solution:

```
int k,R[][],a[]=new int[]{4,3,3,2,2,2},d,e,s,x,y;boolean H(int[][]b,int I){var q=I==6;if(!q)for(int L=a[I++],r=d=b.length,c,M,N,i;r-->0;)for(c=e;c-->0;)for(M=N=i=1;b[x=r][y=c]>0&i<L;i++)q|=(M+=r+(s=L)>d?0:b[r+i][c])==L&&H(R(b,1),I)||(N+=c+L>e?0:b[r][c+i])==L&&H(R(b,0),I);return q;}int[][]R(int[][]n,int o){for(R=new int[k=d][e];k-->0;)R[k]=n[k].clone();for(;s-->0;)R[x+s*o][y-s*~-o]=0;return R;}boolean v(int[][]f){e=f[k=0].length;for(var y:f)for(var x:y)k+=x;return k==20&H(f,0);}

```

so here is my solution. (I went with a recursive solution for finding the ships)

```
public class BF {
    private static int[][] fields;
    public BF(int[][] field) {
        fields=field;
    }
    public boolean validate() {
        int cnt=counter(fields);
        if(cnt!=20)return false;
        return checkBoard(fields, new int[]{4,3,3,2,2,2},0);
    }

    public static boolean checkBoard(int[][] board,int[] allBoats,int index){
        if (index == allBoats.length) {
            return true;
        }
        int boatLen = allBoats[index];
        for (int row = 0; row < board.length; row++) {
            for (int col = 0; col < board[0].length; col++) {
                if(board[row][col]==1 && row+ boatLen <=board.length) {//vertically
                    int cnt=1;
                    for(int i=1;i<boatLen;i++) {//check vertically
                        if(board[row+i][col]==1) {cnt++;}
                    }
                    if(cnt>=boatLen) {
                        int[][] newBoard = deepcopy(board);
                        newBoard= remove(newBoard , row, col, boatLen, "ver");
                        if(checkBoard(newBoard,allBoats,index+1)) { return true;}
                    }
                }
                if(board[row][col]==1 && col+boatLen<=board[0].length) {//horizontally
                    int cnt=1;
                    for(int i=1;i<boatLen;i++) {//check horizontally
                        if(board[row][col+i]==1) {cnt++;}
                    }
                    if(cnt>=boatLen) {
                        int[][] newBoard = deepcopy(board);
                        newBoard= remove(newBoard , row, col, boatLen, "hor");
                        if(checkBoard(newBoard,allBoats,index+1)) { return true;}
                    }
                }
            }
        }
        return false;
    }

   public static int[][] remove(int[][] newBoard,int row,int col,int size,String orien){
       int[][] removedBoard= deepcopy(newBoard);
       if(orien=="ver") {
           for(int i=0;i<size;i++) {
               removedBoard[row+i][col]=0;
           }
           return removedBoard;
       }
       else if(orien=="hor") {
           for(int i=0;i<size;i++) {
               removedBoard[row][col+i]=0;
           }
           return removedBoard;
       }
       return removedBoard;
   }
   public static int[][] deepcopy(int[][] fields){
    int[][] copy= new int[fields.length][fields[0].length];
    for (int row = 0; row < fields.length; row++) {
        for (int col = 0; col < fields[0].length; col++) {
                   copy[row][col]= fields[row][col];
               }
            }
    return copy;
   }
   public static int counter(int[][] f) {// counts amount of tiles on the board with 1's
          int cnt=0;
        for (int col = 0; col < f[0].length; col++) {
            for (int row = 0; row < f.length; row++) {
                if (f[row][col] == 1) {
                 cnt++;
                }
                }
        }
        return cnt;
      }
}

```

here is my Pseudo code on the Check board function

```
/*
 *
 * function gets length of boat(field, size, ships){{3,2,1};
 * loop go through each position in field
 * checks vertically {
 *  finds option for where the boat can be
 *  copies the board
 *  removes the boat from the copy
 *  call remove boat(function gets length of boat) for size-1, deepcopy
 *  if true then return true
 * }
 * check horizontal{
 *  finds option for where the boat can be
 *  copies the board
 *  removes the boat from the copy
 *  call remove boat(function gets length of boat) for size-1, deepcopy
 *  if true then return true
 * }
 * else find next size 4 option
 * }
 */

```

let me know what u think:P

if you want to test it, here is some code for testing in my Java Solution:

```
import org.junit.Test;
import static org.junit.Assert.*;
public class SolutionTest {
    @Test
    public void testContact() {
          int[][] field = {};
        assertTrue("Must return true", new BF(field).validate());
    }
}

```
> 2 votes

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