title: Is this a valid Takuzu board?

text:
# Question
Title: Is this a valid Takuzu board?
Takuzu is a logic game in which you have to complete a grid with cells containing `0`s and `1`s. The grid must follow 3 rules:

1. No three horizontal or vertical consecutive cells can be the same.
2. There must be an equal number of `0`s and `1`s in each row and column.
3. No two rows can be the same, and no two columns can be the same.

Let's look at a finished grid:

```
0011
1100
0101
1010

```

As you can see, this board follows rule `1`, `2` and `3`. There are no three horizontal or vertical cells that are the same, all the rows and columns contain an equal number of `0`s and `1`s, and no two rows and no two columns are the same.

Let's look at a grid that isn't valid:

```
110100
010011
011010
101100
100011
001101

```

There's a bunch of problems with this grid. For example, row `5` has three `0`s in a row, and column `2` has three `1`s in a row, followed by three `0`s. Therefore, this is not a valid grid.

## Task:

Your task is to make a program which, given a 2D array of `n` * `n` `0`s and `1`s, verifies the board to see if it's a valid, finished Takuzu board.

## Examples:

```
0011
1100
0101
1010

```

This board follows all the rules, and is therefore a valid Takuzu board. You must return a truthy value for this.

```
11
00

```

This is not a valid board - row `1` doesn't follow rule `2`. You must return a falsey value for this.

```
100110
101001
010101
100110
011010
011001

```

This is not a valid board, it fails (only) due to rule 3 - the first and fourth rows are the same.

```
110100
001011
010011
101100
100110
011001

```

This is not a valid board, it fails (only) due to rule 3 - the first and fourth columns are the same.

```
011010
010101
101100
010011
100110
101001

```

This is a valid board.

## Rules and Specs:

* You can assume that all boards are square of dimensions `n * n`, where `n` is a positive even integer.
* You can assume that all boards are finished.
* You may take input as a 2D array containing values signifying `0` and `1`, or as a string.
* You must output consistent truthy and falsey values for truthy and falsey boards, and the values representing "truthy" and "falsey" cannot be the same.

This is , so shortest code in bytes wins!

# Answer
# Brachylog, ~~20~~ 18 bytes

```
≠\≠,?¬{∋s₃=|∋ọtᵐ≠}

```

Try it online!

### Explanation

```
≠                           All rows are different
 \                          Transpose
  ≠                         All columns are different
   ,?                       Append the list of rows to the list of columns
     ¬{          }          It is impossible that:
       ∋                      A row/column of the matrix…
        s₃=                   …contains a substring of 3 equal elements
           |                Or that:
            ∋ọ                The occurences of 1s and 0s in a row/column…
              tᵐ≠             …are not equal

```
> 16 votes

# Answer
# Husk, ~~19~~ 18 bytes

```
S=‼(Tf§=LṁDum(ṁ↑2g

```

Try it online!

1 byte saved thanks to H.PWiz!

The main idea is applying a series of transformations to the input that are identities for a valid board and checking if the final result is the same as the original input.

### Explanation

```
S=‼(Tf§=LṁDum(ṁ↑2g
            m(ṁ↑2g    in each line, take at most two items for each sequence of equal items
           u          remove duplicate lines
     f§=LṁD          keep only those lines where the sum of each element doubled is equal to the length of the line
    T                 transpose the matrix (swap rows with columns)
  ‼                   do all the previous operations again
S=                    check if the final result is equal to the original input

```
> 11 votes

# Answer
# Jelly, 17 bytes

```
-*S;E3Ƥ€F$TȯQZµ⁺⁼

```

Try it online!

-6 bytes thanks to miles and Jonathan Allan.
> 7 votes

# Answer
# Mathematica, 143 bytes

```
And@@Flatten@(((s=#;Equal@@(Count[s,#]&/@{0,1})&&FreeQ[Subsequences@s,#]&/@{{1,1,1},{0,0,0}})&/@#)&&(DeleteDuplicates@#==#)&/@{#,Transpose@#})&

```

**input**

> \[{{0, 0, 1, 1}, {1, 1, 0, 0}, {0, 1, 0, 1}, {1, 0, 1, 0}}\]
> 5 votes

# Answer
# Python 2, 127 bytes

```
a=input()
n=len(a)
b=zip(*a)
print[n/2]*n*2==map(sum,a+b)>len(set(a))==len(set(b))==n<'0, 0, 0'not in`a+b`>'1, 1, 1'not in`a+b`

```

Try it online!

Reads a list of *n* *n*-tuples as input.

I could output by exit code by writing `1/(…)` instead of `print…` but it feels scummy. Should I?

## Explanation

`n` is the size of the board; `b` is a list of columns (transpose of `a`). The rest is one long chained comparison:

* `[n/2]*n*2==map(sum,a+b)` checks rule 2. Each row and column should sum to n/2.
* `map(sum,a+b)>len(set(a))` is always true (list \> int).
* `len(set(a))==len(set(b))==n` checks rule 3.
* `n<'0, 0, 0'` is always true (int \< str).
* `'0, 0, 0'not in`a+b`>'1, 1, 1'not in`a+b`` checks rule 1. ``a+b`` is the string representation of all the rows and columns; for the example input on TIO it is

```
"[(0, 0, 1, 1), (1, 1, 0, 0), (0, 1, 0, 1), (1, 0, 1, 0), (0, 1, 0, 1), (0, 1, 1, 0), (1, 0, 0, 1), (1, 0, 1, 0)]"

```

The ``a+b`>'1, 1, 1'` in the center is always true since this string is guaranteed to start with `"["`, which is greater than `"1"`.
> 5 votes

# Answer
# MATL, 27 bytes

```
,G@?!]tEqts~w7BZ+|3<bXBSdvA

```

Input is a matrix containing `0` and `1`. Output is `0` for falsy, `1` for truthy.

**Try it online!** Or see test cases: **1**, **2**, **3**, **4**, **5**.

### Explanation

```
,       % Do twice. First iteration will use the input, second its transpose
  G     %   Push input
  @     %   Push iteration index: first 0, then 1
  ?     %   If nonzero
    !   %     Transpose
  ]     %   End
  t     %   The top of the stack contains the input or its transpose. Duplicate
  Eq    %   Convert to bipolar form, i.e. replace 0 by -1
  t     %   Duplicate
  s     %   Sum of each column
  ~     %   Negate. If all results are true, condition 2 is fulfilled
  w     %   Swap. Moves copy of bipolar input/transposed input to top
  7B    %   Push [1 1 1], obtained as 7 converted to binary
  Z+    %   2D convolution. Gives a matrix of the same size as the input
  |3<   %   Is each entry less than 3 in absolute value? If all results are true,
        %   condition 1 is fulfilled
  b     %   Bubble up. Moves copy of input/transposed input to top
  XB    %   Convert each row from binary to a number
  Sd    %   Sort, consecutive differences. If all results are nonzero, condition 3
        %   is fulfilled
  v     %   Concatenate all results so far into a column vector
  A     %   True if all entries are nonzero
        % End (implicit). Display (implicit)

```
> 3 votes

# Answer
# Husk, ~~27~~ 25 bytes

```
Λ§&Λȯ¬VEX3§&Λ§=#0#1S=uSeT

```

Input is a list of lists and output is `1` for `True` and `0` for `False`

Try it online!

### Explaination

```
                      SeT    Create a list with the input and itself transposed
Λ                            Is the following function true for all in the list
 §&                          And the results of the following functions
   Λȯ¬VEX3                     Test for rule 1
          §&                   The and of:
            Λ§=#0#1                Test for rule 2
                   S=u             Test for rule 3

```

### Test 1

```
Λȯ¬VEX3
Λ         Is it True for all ...
   V      Are any of the ...
     X3   Substrings of length 3 ...
    E     All equal
 ȯ¬       Logical not

```

### Test 2

```
Λ§=#0#1
Λ         Is it true for all that ...
 §=       The results of the two functions are equal
   #0         Number of 0s
     #1       Number of 1s

```

### Test 3

```
S=u
S=    Is the result of the following function equal two its argument
  u   Remove duplicates

```
> 3 votes

# Answer
# Pyth, 31 bytes

Thanks a lot to @Leaky Nun.

```
.Asm++mqy/k\0lQdm<hk3srL8d{Id,C

```

**Verify all the test cases or Try it here!**

---

# Pyth,  ~~48 46 44~~  42 bytes

This is the initial solution.

```
&{IQ&{I.TQ.Am&q/d\0/d\1!+/d*3\0/d*3\1sC,.T

```

**Verify all the test cases or Try it here!**

```
&{IQ&{I.TQ.Am&q/d\0/d\1!+/d*3\0/d*3\1sC,.T     Full program with implicit input.

 {IQ                                           Is the input invariant under deduplicating?
&    {I.TQ                                     And is its transpose invariant too?
                                        .TQ    Transpose.
                                           Q   The input.
                                     sC,       Zip the above, [^, ^^] (and flatten).
    &                                          And is the following condition met?
          .Am                                  All elements are truthy when mapping over ^^.
              q/d\0/d\1                        There are as many 0s as 1s.
             &         !+/d*3\0/d*3\1          And there are no runs of 3 equal elements.

```
> 3 votes

# Answer
# Retina, ~~129~~ ~~89~~ 85 bytes

```
.+
$&,$&
O#$`.(?=.*,)
$.%`
.+
$&;$&
+`(01|10)(?=.*;)

1ms`(.)\1\1|\d,?;|(\D\d+\b).*\2

```

Try it online! Outputs 0 for valid, 1 for invalid. Edit: Saved 4 bytes thanks to @MartinEnder. Explanation:

```
.+
$&,$&

```

Duplicate each row with `,` separators.

```
O#$`.(?=.*,)
$.%`

```

Transpose the first duplicate.

```
.+
$&;$&

```

Duplicate again, this time with `;` separators.

```
+`(01|10)(?=.*;)

```

Delete all matching pairs of digits that precede a semicolon.

```
1ms`(.)\1\1|\d,?;|(\D\d+\b).*\2

```

Check to see whether any column or row fails any of the rules; `(.)\1\1` checks for three identical digits in a row, `\d,?;` checks for an unpaired digit and `(\D\d+\b).*\2` checks for a duplicate.
> 3 votes

# Answer
# Java 8, ~~350~~ ~~326~~ ~~325~~ ~~312~~ ~~303~~ ~~299~~ ~~298~~ ~~259~~ 255 bytes

```
int r,z,c,p,i,j,k,d,u,v=1;int c(int[][]b){v(b);k=v-=u=1;v(b);return r;}void v(int[][]b){String m="",x;for(d=b.length;j<d|k<d;k+=u,j+=v,r=m.contains(x)|z!=0?1:r,m+=x)for(x="#",c=0,k*=u,j*=v;j<d&k<d;z+=i|i-1,c*=i^p^1,x+=p=i,r=++c>2?1:r,k+=v,j+=u)i=b[k][j];}

```

Returns `0` when it's a valid board; `1` if it's invalid for one or more of the three rules.

-95 bytes thanks to *@Nevay*.

**Explanation:**

Try it here.

```
int r,z,c,p,i,j,k,d,u,v=1;
                     // Temp integers on class-level

int c(int[][]b){     // Method (1) with int-matrix parameter and int return-type
  v(b);              //  Validate the rows
  k=v-=u=1;          //  Switch rows with columns, and reset `u` to 1
  v(b);              //  Validate the columns
  return r;          //  Return the result
}                    // End of method (1)

void v(int[][]b){    // Separated method (2) with int-matrix parameter and no return-type
  String m="",s;     //  Two temp Strings to validate uniqueness of rows
  for(d=b.length;    //  Set the dimension of the matrix to `d`
      j<d|k<d        //  Loop (1) as long as either `j` or `k` is smaller than `d`
    ;                //   After every iteration:
     k+=u,j+=v       //    Increase the loop-indexes
     r=m.contains(s) //    If we've found a duplicated row,
     |z!=0?          //    or if the amount of zeroes and ones on this row aren't equal
      1:r,           //     Set `r` to 1 (invalid due to either rule 2 or 3)
     m+=s)           //    Append the current row to the String `m`
    for(s=",",       //   Set String `x` to a separator-character
        c=0,         //   Reset the counter to 0
        k*=u,j*=v,   //   Increase the loop-indexes
        j<d&k<d      //   Inner loop (2) as long as both `j` and `k` are smaller than `d`
     ;               //    After every iteration:
      z+=i|i-1,      //     Increase or decrease `z` depending on whether it's a 0 or 1
      c*=i^p^1,      //     Reset `c` if current digit `i` does not equal previous `p`
      s+=p=i,        //     Set previous `p` to current digit, and append it to String `s`
      r=++c>2?       //     If three of the same adjacent digits are found:
         1:r;        //      Set `r` to 1 (invalid due to rule 1)
        k+=v,j+=u)   //      Increase the loop-indexes
      i=b[k][j];     //    Set `i` to the current item in the matrix
                     //   End of inner loop (2) (implicit / single-line body)
                     //  End of loop (2) (implicit / single-line body)
}                    // End of separated method (2)

```
> 2 votes

# Answer
# , ~~114~~ 107 bytes

*-7 thanks to Giuseppe, calling functions out of order and really compressing the conditions down*

```
function(x)any(f(x),f(t(x)))
f=function(x)c(apply(x,1,function(y)max(rle(y)$l)>2+mean(y)-.5),duplicated(x))

```

Try it online!

This just applies the rules to the columns of the matrix, then the columns of the transpose of the matrix.

Takes input in the form:

```
matrix(c(0,0,1,1,1,1,0,0,0,1,0,1,1,0,1,0), ncol=4)

```

Which is just how R takes 2D arrays.

Outputs TRUE for failures, FALSE for passes.
> 2 votes

# Answer
# Perl 6, ~~100~~ 93 bytes

*Junctions FTW! They save 7 bytes.*

For the time being, this seems to be beating all the other submissions written in non-golfy languages. Yippie!

```
{!max (@(.map(*.join)).&{.repeated| |.map:{$_~~/000|111/|.comb(0)-.comb(1)}}for @^a,[Z] @^a)}

```

Try it online!

**Explanation**: It's a block that takes the board as list of lists. We make a transpose with `[Z] @^a` (reduce the list of lists with zip operator). So `@^a,[Z] @^a` is a list of the board and its transpose. We loop over it with `for` which works exactly like `map`, just being 1 char cheaper in this case.

Inside, we first join the lists constituting rows into strings, so we have list of strings instead of list of lists (`@(.map(*.join))`). Then we use an anonymous block on it (`.&{...}`), where we actually evaluate the rules. We'll evaluate them only row-wise. (Since we do it for the original array and the transpose as well.)

To save quite some `!`'s, we use a bit of logic and instead of testing `(NO repeated rows) AND (NO 3 consecutive same symbols) AND (NOT different counts of 0 and 1)`, we test `NOT[ (repeated rows) OR (3 consecutive same symbols) OR (different counts) ]`. That's what we do in the anonymous block: `.repeated` gives all rows that occur more than once, then we map over the rows, try to match 3 consecutive symbols using a regex, and subtract the counts of 0's and 1's. These are OR'red with the `|`. (Actually it creates a very powerful thing called a *junction*, but we don't use any of its powers :)) After all of this, we get a list of 2 "bools" (uncollapsed junctions). We finally or them (using `max`) and negate (`!`), which gives the desired result.
> 2 votes

# Answer
# J, ~~40~~ ~~38~~ 55 bytes

```
0=[:([:+/^:_(3(0=3|+/)\"1 ]),:-.@~:,:#=[:+/"1+:@])|:,:]

```

Try it online!

Defines a function taking a square matrix as input.

~~At least it's beating Pyth (for now...)~~ (erroneously). I should go back to counting the emoji hidden in my code since J also lends itself well to that:

`[:` `/^:` `:1` `|:` `:]` `:-.@` `:#` `:@]` `:~@`

# Explanation (slightly outdated)

This looks different from my answer, and I may get to updating it. Parts of it are still the same -- I just was not checking for rule 3 for and improperly checking for rule 2 before.

Split into a few functions and ungolfed:

```
join_trans  =. |: ,: ]
part_3      =. 3 (0 = 3 | +/)\"1 ]
f           =. 1 - 2 * ]
main        =. 0 = [: ([: +/^:_ part_3 , f) join_trans

```

# join\_trans

```
|: ,: ]
|:       Transpose
   ,:    Laminated to
      ]  Input

```

This joins the transpose of the matrix to itself, creating an array of matrices.

# part\_3

```
3 (0 = 3 | +/)\"1 ]
                  ]  Input (matrix and transpose)

```

This checks the sum of partitions of 3 row-wise to see if it is 3 or 0 (since either of these means an invalid board), returning 1 if it is and 0 otherwise. It operates on both the matrix and its transpose since it's given both.

# f

```
1 - 2 * ]

```

For lack of a better name, I call this `f`. It replaces the 0s with \_1 and leaves the 1s unchanged. This is to allow me to eventually check if the number of 0s and 1s are equal in each row and column (the sum of each of the rows should be 0).

### main

```
0 = [: ([: +/^:_ part_3 , f) join_trans
                             join_trans  Join transpose to input
                 part_3 , f              Apply the validity checks and join them
           +/^:_                         Sum until it converges
0 =                                      Equate to 0

```

Basically, I leverage the fact that I've set it up so that `f join_trans` and `part_3 join_trans` both should sum to 0 iff the board is valid. `part_3` should be all zeroes for a valid board and the entirety of `f` should sum to zero for a valid board, meaning that the sum of their sums is 0 only for a valid board.
> 2 votes

# Answer
# Haskell, ~~137~~ ~~136~~ 127 bytes

*9 bytes saved thanks to Lynn!*

```
import Data.List
j=isSubsequenceOf
l x=x==nub x&&and[sum y*2==length x&&not(j[0,0,0]y||j[1,1,1]y)|y<-x]
g x=l x&&l(transpose x)

```

Try it online!
> 2 votes

# Answer
# Python 3, 187 bytes

```
lambda m,c=lambda m:all([len({*m})==len(m),sum(~-("000"in x)*~-("111"in x)and x.count("1")==x.count("0")for x in m)==len(m)]):c(["".join(x[i]for x in m)for i in range(len(m[0]))])and c(m)

```

Try it online!

Takes input as a list of lines.
> 1 votes

# Answer
# 05AB1E, 29 bytes

```
ø‚D€ÙQIDøì©O·IgQP®εŒ3ù€Ë_P}PP

```

Try it online!

**Explanation**

Rule: 3

```
ø‚        # pair the input with the zipped input
  D       # duplicate
   €Ù     # deduplicate each
     Q    # check for equality with the unmodified copy

```

Rule: 2

```
IDøì          # prepend zipped input to input
    ©         # store a copy in register for rule 1
     O        # sum each row/column
      ·       # double
       IgQ    # check each for equality to length of input
          P   # product

```

Rule: 1

```
®ε            # apply to each row/column in register
  Œ3ù         # get sublists of length 3
     €Ë       # check each if all elements are equal
       _      # logical not
        P     # product
         }    # end apply
          P   # product

```

Then we take the product of the result of all 3 rules with `P`
> 1 votes

# Answer
# Dyalog APL, ~~64~~ ~~52~~ ~~51~~ ~~49~~ 48 bytes

Requires `⎕IO←0`

```
{⍲/{(∨/∊⍷∘⍵¨3/¨⍳2)∧((⊢≡∪)↓⍵)∧∧/(≢=2×+/)⍵}¨⍵(⍉⍵)}

```

Try it online!
> 1 votes

# Answer
# PHP, 245+1 bytes

ew this is bulky. linebreaks are for reading convenience only:

```
$t=_;foreach($a=($i=str_split)($s=$argn)as$i=>$c)$t[$i/($e=strlen($s)**.5)+$i%$e*$e]=$c;
for(;$k++<2;$s=$t)$x|=preg_match("#000|111|(\d{"."$e}).*\\1#s",chunk_split($s,$e))
|($m=array_map)(array_sum,$m($i,$i($s,$e)))!=array_fill(0,$e,$e/2);echo!$x;

```

Takes a single string without newlines, prints `1` for truthy, nothing for falsy.

Run as pipe with `-nR` or try it online.
> 1 votes

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


title: These Days Work for Me

text:
# Question
Title: These Days Work for Me
# Background

You're an attractive code golfer and quite a few people are asking you out.

You don't have time to think about which days exactly you're available, so you decide to create a function the accepts a date and returns the days of that week.

You then take those days of the week, insert it into your calendar program to see if anyone else has asked you out already.

# Rules

* Accepts a date in YYYY-MM-DD format
* Returns an array/list of dates of that week. (Sunday is the first day)
    + The dates can be displayed as the milliseconds between January 1, 1970 and that date, in a "common" date format1, or date objects.
* The order of the dates must be ascending.
    + (Although you're smart enough to include support for a descending list, the program is able to work quickest with an ascending list and who has a few milliseconds to spare?)
* Must work with on any day since 1993. (Yes, you're 24 years old at the time of writing!)
* Every Javascript answer gets a high five!

# Specs

**Sample Input:** `whichDates(2017-08-29)`

**Output:** (the equivalent of)

```
console.log([
  Date.parse('2017-08-27'),
  Date.parse('2017-08-28'),
  Date.parse('2017-08-29'),
  Date.parse('2017-08-30'),
  Date.parse('2017-08-31'),
  Date.parse('2017-09-01'),
  Date.parse('2017-09-02'),
]);
```

1 A format that is fairly well known. Such as YYYY-MM-DD.

2 This is ! Shortest code per language wins, but the shortest code overall gets the emerald checkmark!

# Answer
> 1 votes
# Japt, 15 bytes

```
ÐU
7Æf1X+Uf -Ue

```

Test it

---

## Explanation

Implicit input of string `U`.

```
ÐU

```

Convert `U` to a date object and reassign to `U`.

Create an array of integers from `0` to `6`, passing each through a function where `X` is the current element.

```
f1

```

Set the date of `U`.

```
X+Uf

```

Add the current date of `U` to `X`.

```
-Ue

```

Subtract the current day of the week of `U`.

Implicitly output the resulting array.

# Answer
> 5 votes
# Perl 6, 47 bytes

```
{my$d=Date.new($_);map($d+*-$d.day-of-week,^7)}

```

Try it online!

The code is almost self-explanatory. First we make up a Date object `$d` from the string, which happens to be in the nice ISOwhatever format. We can perform arithmetic with the dates (adding an integer = adding that many days, the same with subtracting). So `$d-$d.day-of-week` is the ~~last~~ this (oh my god, week has always started with Monday for me :D) week's Sunday. (`.day-of-week` is 1 for Monday to 7 for Sunday.) We then map over 0 to 6 (`^7`) and add that to the Sunday, getting all the days in the week. The number we're mapping over appears in the place of the star `*`. This list is then returned.

# Answer
> 5 votes
# JavaScript (ES6), ~~73~~ ~~63~~ 62 Bytes

I thought I'd also have a go at it in JavaScript.

Edit: Using the milliseconds approach, as allowed by the prompt, I reduced it down to 62 bytes.

```
s=>[..."0123456"].map(i=>(x=new Date(s))-(x.getDay()-i)*864e5)

```

You could perform a `.map(x=>new Date(x))` on the returned array if you wanted to convert it.

---

Maintaining the date approach (**72 Bytes**)

```
s=>[..."0123456"].map(i=>new Date((x=new Date(s))-(x.getDay()-i)*864e5))

```

---

There was a bug in my initial submission, it is fixed. Thanks to an observation by milk, I was able to remove the bug and still lower the byte count.

# Answer
> 3 votes
# JavaScript (ES6), 76 bytes

I think I've finally found the environment least conducive to efficient golfing: from behind my bar, while serving pints with my other hand!

```
s=>[...""+8e6].map((_,x)=>d.setDate(d.getDate()-d.getDay()+x),d=new Date(s))

```

Try it online (Snippet to follow)

---

## Explanation

```
s=>

```

Anonymous function taking the string (of format `yyyy-(m)m-(d)d`) as an argument via parameter `s`.

```
[...""+8e6]

```

Create an array of 7 elements by converting `8000000` in scientific notation to a string and destructuring it, which is shorter than `[...Array(7)]`.

```
.map((_,x)=>          )

```

Map over the array, passing each element through a function where `_` is the current element, which won't be used, and `x` is the current index, 0-based.

```
,d=new Date(s)

```

Convert `s` to a `Date` object and assign it to variable `d`

```
d.setDate(     )

```

Set the date of `d`.

```
d.getDate()

```

Get the current date of `d`.

```
-d.getDay()

```

Subtract the current weekday number, 0-indexed, to get Sunday.

```
+x

```

Add `x`.

# Answer
> 3 votes
# MATL, ~~22~~ 21 bytes

```
7:j8XOs21Y2=f-GYO+1XO

```

Output is in `dd-mm-yyyy` format.

Try it at **MATL Online!**

### Explanation

```
7:     % Push [1 2 3 4 5 6 7]
j      % Input as a string
8XO    % Convert date to string with format 8, which is 'Mon', 'Tue' etc
s      % Sum
21Y2   % Push predefined literal [298 302 288 305 289 296 310]. The first number
       % is the sum of ASCII codes of 'Mon', the second is that of 'Tue', etc.
=      % Is equal?, element-wise
f      % Index of nonzero value. For example, if input is a Friday this gives 5
-      % Subtract, element-wise. For a Friday this gives [-4 -3 -2 -1 0 1 2]
G      % Push input again
YO     % Convert to date number: number of days from January 0, 0000
+      % Add, element-wise
1XO    % Convert to date format 1, which is 'dd-mm-yyyy'. Implicitly display

```

# Answer
> 2 votes
# Python 3, ~~133~~ ~~124~~ ~~126~~ 112 bytes

-9 bytes thanks to Mr. Xcoder
+2 bytes because the week starts with Sunday
**-14 bytes** thanks to notjagan

```
from datetime import*
a=date(*map(int,input().split('-')))
for i in range(7):print(a-timedelta(a.weekday()-i+1))

```

That didn't go as well as I had hoped.

# Answer
> 2 votes
# Bash + common utilities, 53

```
jot -w@ 7 `date -f- +%s-%w*86400|bc` - 86400|date -f-

```

Try it online.

This assumes that the output of GNU date is a "common" date format, e.g. `Fri Sep 1 00:00:00 UTC 2017`.

### Explanation

```
           date -f- +%s-%w*86400                       # read date from STDIN, output expression "seconds-since-epoch - (index of day in week * 60 * 60 * 24)
                                |bc                    # arithmetically evaluate generated expression - result is date of required sunday in seconds-since-epoch
jot -w@ 7 `                        ` - 86400           # output seconds-since-epoch for all 7 required days of the week, prefixed with "@"
                                            |date -f-  # convert all seconds-since-epoch dates back to regular dates

```

# Answer
> 1 votes
# Java 8 (~~161~~ ~~154~~ ~~123~~ ~~122~~ 102 + ~~19~~ 36 bytes)

Try it online!

```
import static java.time.LocalDate.*;

e->{for(int i=0;i<7;System.out.println(parse(e).plusDays(i++-parse(e).getDayOfWeek().getValue()%7)));}

```

# Answer
> 1 votes
# Mathematica 20 bytes?

Mathematica expresses the list of days as a single date object. If such date object is acceptable output, the following 20-byte pure function will work:

```
#~DateObject~"Week"&

```

**Example**

```
#~DateObject~"Week"&["2017-08-29"]

```

# Answer
> 1 votes
# Python 2, 115 Bytes or 111 Bytes, depending on input format.

Basically, this is almost the same code in the answer for Python3 written by Sobsz, but made to work in Python 2.

---

### If input is in the form `YYYY-MM-DD`:

(This assumes the input is not wrapped in single-quotes to denote a string as input)

Key difference is that we need `raw_input` instead of `input`, unless we explicitly specify the date in `'YYYY-MM-DD'` within the apostrophes to identify it as a string literal. Without the string literal input, we get a Syntax Error, hence the use of `raw_input` to accept dates in `YYYY-MM-DD` directly without putting it in string literals.

This of course assumes that the input is put in like so: `2017-08-29`.

```
from datetime import*
a=date(*map(int,raw_input().split('-')))
for i in range(7):print a-timedelta(a.weekday()-i+1)

```

+4 from Sobsz's answer, then -1 because we don't need parentheses for the `print` statement and save a byte from the closing parenthesis not being there; total of +3 bytes difference.

Try it Online!

---

### If input is in the form `'YYYY-MM-DD'`:

(Note that we must have the date provided inside quotes in order for this answer to work)

We get to save 4 bytes because we don't need the `raw_` and this is effectively the same answer as Sobsz provides, minus a byte because we don't need the parentheses around the `print` command.

Thanks to Mr. Xcoder for pointing this one out, though this is **technically an exact duplicate then, minus one byte, of Sobsz's answer**.

```
from datetime import*
a=date(*map(int,input().split('-')))
for i in range(7):print a-timedelta(a.weekday()-i+1)

```

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


# Question
Title: Find out how Abstractly Capacious™ someone is!
At the Code-Golf™ Psychological Society, you are delighted to present a new method of measuring mental age: *Abstract Capacity™*.

To get the *Abstract Capacity* of a person, you take their actual age divided by 4, take their IQ divided by 9, then add the two values together. Then, round this sum down to find the *Abstract Capacity*.

**Challenge**

Write a program, given an actual age *A* and an IQ of *I*, produces the *Abstract Capacity* using those values. The program should also print how older (age) or how smarter (IQ) someone should be in order to raise their *Abstract Capacity* by 1.

An input will always look something like

> *A* *I*

and an output will always look something like

> *AC* *A'* *I'*

where AC, A' and I' respectively denote the *Abstract Capacity*, how older someone has to be to raise their *Abstract Capacity*, and how smarter someone has to be to raise their *Abstract Capacity*.

**Examples**

**Input**

```
13 43

```

**Output**

```
8 4 9

```

**Input**

```
92 5

```

**Output**

```
23 2 4

```

**Input**

```
40 17

```

**Output**

```
11 1 1

```

**Rules**

Your code must be able to find the *Abstract Capacity* for any given *A* and *I* when 1 \< *A*,*I* \< 400.

This is . Shortest answer in bytes wins!

# Answer
> 2 votes
# Python 2, 61 bytes

```
def f(a,i):r=a*9+i*4;print r/36,(r+44-i*4)/9-a,(r+39-a*9)/4-i

```

**Try it online!**

# Answer
> 2 votes
# Python 2, 50 bytes

-1 byte thanks to Mr. Xcoder (`print` instead of `return`).

```
def f(a,i):x=a*9+i*4;m=x%36;print x/36,4-m/9,9-m/4

```

**Try it online!**

# Answer
> 1 votes
## JavaScript (ES6), ~~67~~ 50 bytes

```
f=
(a,i,r=a*9+i*4)=>[r/36|0,4-(r%36/9|0),9-(r%36>>2)]
```

```
<div oninput=[ac.textContent,ea.textContent,ei.textContent]=f(a.value,i.value)>Age: <input type=number id=a><br>IQ: <input type=number id=i><br>Abstract Capacity: <span id=ac></span><br>Extra age needed: <span id=ea></span><br>Extra IQ needed: <span id=ei>
```

Edit: Although originally I was trying to verify @Mr.Xcoder's comment I ended up verifying @JonathanAllan's answer instead.

# Answer
> 1 votes
# Pyth, 26 bytes

```
/K+*9Q*4E36-4/J%K36 9-9/J4

```

**Try it here!**

# Answer
> 1 votes
# MATL, ~~25~~ 22 bytes

```
K9hGy/sktQ3M1YS-b*XkG-

```

-3 bytes thanks to @LuisMendo

Try it online!

# Answer
> 1 votes
# 05AB1E, ~~21~~ ~~19~~ 18 bytes

```
94S©*O36‰RĆÁ®÷®RαÁ

```

Try it online!

**Explanation**

Example for `input = [92, 5]`

```
94                   # push the number 94
  S©                 # split to a list of digits and store a copy in register
                     # STACK: [9,4]
    *                # element-wise multiplication with input
                     # STACK: [828, 20]
     O               # sum
                     # STACK: 848
      36‰            # divmod 36
                     # STACK: [23, 20]
         R           # reverse
          Ć          # append the head (the mod result)
           Á         # rotate right
                     # STACK: [20, 20, 23]
            ®÷       # element-wise integer division with the register
                     # STACK: [2, 5, 23]
              ®Rα    # absolute difference with the register reversed
                     # STACK: [2, 4, 23]
                 Á   # rotate right

```

# Answer
> 0 votes
# Excel, 89 bytes

```
=INT(A2/4+B2/9)&" "&ROUNDUP(4-MOD(A2*9+B2*4,36)/9,0)&" "&ROUNDUP(9-MOD(A2*9+B2*4,36)/4,0)

```

Using @Jonathan Allan's approach.

# Answer
> 0 votes
# Java 8, ~~77~~ 67 bytes

Nicked from @JonathanAllan

```
a->i->System.out.printf("%d %d %d",(i=a*9+i*4)/36,4-i/9%4,9-i/4%9);

```

---
Tags: code-golf, math, arithmetic
---


title: Draw some ASCII stars

text:
# Question
Title: Draw some ASCII stars
Write a program or function that draws an ASCII star, given the size of the arms as input.

Here's a star of size `1`

```
_/\_
\  /
|/\|

```

Here's a star of size `2`

```
   /\
__/  \__
\      /
 \    /
 | /\ |
 |/  \|

```

Here's a star of size `3`

```
     /\
    /  \
___/    \___
\          /
 \        /
  \      /
  |  /\  |
  | /  \ |
  |/    \|

```

And so on.

### Input

A single positive integer in any convenient format, `n > 0`.

### Output

An ASCII-art representation of a star, following the above rules. Leading/trailing newlines or other whitespace are optional, provided that the points line up appropriately.

### Rules

* Either a full program or a function are acceptable. If a function, you can return the output rather than printing it.
* Standard loopholes are forbidden.
* This is so all usual golfing rules apply, and the shortest code (in bytes) wins.

# Answer
> 12 votes
# Charcoal, ~~20~~ 17 bytes

*-3 bytes thanks to Neil.*

```
Ｎν↙ν↑↑ν↖ν ×_ν↗ν‖Ｍ

```

Try it online! Link is to verbose version.

I'm pretty happy with this golf so...

## Explanation

```
Ｎν                 take a number as input and store in ν
  ↙ν               print / ν times downwards to the left
    ↑              move up once
     ↑ν            print | ν times upwards
       ↖ν          print \ ν times upwards to the left
                   print a space
          ×_ν      print _ ν times
             ↗ν    print / ν times upwards to the right
               ‖Ｍ  reflect horizontally

```

```
     /\
    /  \    "No, this is Patrick!"
___/    \___
\   ☉ ☉    /
 \       /
  \      /
  |  /\  |
  | /  \ |
  |/    \|

```

# Answer
> 5 votes
# SOGL V0.12, ~~27~~ 24 bytes

```
╔*¹.╚№┼№.╝+ø┐.∙.1ž.╚┼+╬³

```

Try it Here!

Explanation:

```
╔*                        push a string with input amount of underscores
  ¹                       wrap that in an array
   .╚                     push a "/" diagonal of the size of the input (the top lines)
     №                    reverse vertically
      ┼                   add horizontally the underscores behind the array
       №                  reverse vertically back
        .╝+               below that add a "\" diagonal (middle lines)
           ø              push an empty string as the base of the vertical bars
            ┐.∙           get an array of "|" with the length of the input
               .1ž        at [input; 1] in the empty string insert that
                  .╚┼     horizontally append a "/" diagonal
                     +    add that below everything else
                      ╬³  palindromize horizontally

```

# Answer
> 4 votes
# Python 2,  ~~166 160 157 155~~  152 bytes

The `exec` approach is exactly the same byte count.

```
i=input();t,z=" \\";y=t*2
for k in range(i*3):s=k%i;o=i+~s;p=i+o;g="_ "[i>k+1]*p;print[g+"/"+y*k+z+g,t*s+z+y*p+"/",~-i*t+"|"+o*t+"/"+y*s+z+o*t+"|"][k/i]

```

Try it online!

*Saved 3 bytes thanks to Jonathan Frech.*

# Answer
> 3 votes
# Java 8, ~~385~~ ~~376~~ ~~344~~ ~~304~~ ~~285~~ ~~280~~ ~~268~~ ~~264~~ ~~252~~ 250 ~~\+ 19~~ bytes

```
n->{int s=2*n,w=2*s,e=n-1,i=0,o,l[][]=new int[n*3][w];for(;i<n;l[i][s+~i]=l[n+i][w+~i]=l[o][s+~i]=47,l[i][o]=l[o][o]=l[n+i][i]=92,l[e][i]=l[e][w-++i]=95,l[o][e]=l[o][s+n]=124)o=s+i;for(int[]b:l)System.out.println(new String(b,0,w).replace("�"," "));}
```

Try it online!

# Answer
> 2 votes
# Mathematica, 189 bytes

```
n(
  s_±x_±y_:=s->Array[If[x==y,s," "]&,{n,n}];
  StringRiffle[Characters@{"_/\\_","\\  /","|/\\:"}/.
    {"_"±#±n,"|"±#2±n,":"±#2±1,"\\"±#±#2,"/"±(n-#+1)±#2," "±0±1}
    /.":"->"|"//ArrayFlatten,"
",""])

```

Line 2 defines the helper operator `±`, which is used to make line 4 evaluate to:

```
{"_"  -> Array[If[#1 == n,          "_", " "] &, {n, n}],
 "|"  -> Array[If[#2 == n,          "|", " "] &, {n, n}],
 ":"  -> Array[If[#2 == 1,          ":", " "] &, {n, n}],
 "\\" -> Array[If[#1 == #2,         "\\"," "] &, {n, n}],
 "/"  -> Array[If[1 + n - #1 == #2, "/", " "] &, {n, n}],
 " "  -> Array[If[0 == 1,           " ", " "] &, {n, n}]}

```

In line 3, the `ReplaceAll` (`/.`) takes a matrix representing the star of size 1 as well as the list of rules above. For the final steps, we use `ArrayFlatten`, which is shorter than `SubstitutionSystem`, and `StringRiffle`.

# Answer
> 2 votes
# Java 7, 295 bytes

Solution is method `f`.

```
String s(String s,int n){while(n-->0)s=" "+s;return s;}String f(int x){String n="\n",s="/",b="\\",o="",u="_";int i=0;for(x--;i<x;u+="_")o+=s(s,2*x-i+1)+s(b,2*i++)+n;o+=u+s+s(b,2*i)+u+n;while(i>=0)o+=s(b,x-i)+s(s,4*x-2*(x+~i--))+n;while(i++<x)o+=s("|",x)+s(s,x-i)+s(b,2*i)+s("|",x-i)+n;return o;}

```

Try It Online (JDK 8)

## Ungolfed

```
String s(String s, int n) {
    while (n-- > 0)
        s = " " + s;
    return s;
}

String f(int x) {
    String
        n = "\n",
        s = "/",
        b = "\\",
        o = "",
        u = "_"
    ;
    int i = 0;
    for (x--; i < x; u += "_")
        o += s(s, 2*x - i + 1) + s(b, 2 * i++) + n;
    o += u + s + s(b, 2 * i) + u + n;
    while (i >= 0)
        o += s(b, x - i) + s(s, 4*x - 2*(x + ~i--)) + n;
    while (i++ < x)
        o += s("|", x) + s(s, x - i) + s(b, 2 * i) + s("|", x - i) + n;
    return o;
}

```

## Acknowledgments

* -1 byte thanks to Kevin Cruijssen

# Answer
> 0 votes
# Python 2, 137 bytes

```
n=input()
b,f,s,v='\/ |'
for i in range(3*n):u=i/~-n*n*'_';d=f+i%n*2*s+b;print[u+d+u,b+s*2*(3*n+~i)+f,v+d.center(2*n)+v][i/n].center(4*n)

```

Try it online!

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


title: Shout the input

text:
# Question
Title: Shout the input
Given a string that consists entirely of printable ASCII, convert all lowercase letters to their uppercase equivalent. Non-lowercase characters are left untouched.

I am not going to outright ban builtin solutions, but if you are going to post a solution that uses the builtin, please also post one that doesn't in your answer.

This is a so shortest code wins, standard rules apply.

## Test cases

```
input => output

Hello, World! => HELLO, WORLD!
TEST => TEST
1gN0r3 50M3 cH4r4C73r5 => 1GN0R3 50M3 CH4R4C73R5

```

GOOD LUCK GOLFERS!

# Answer
> 2 votes
# Japt, 05AB1E & 2sable (and probably others), 1 byte

```
u

```

**Try it:** Japt | 05AB1E | 2sable

Thanks to Mr. Xcoder for pointing out the polyglots.

---

## Japt Without Built-in, 16 bytes

```
c_¨#a©Z§#z?Z-H:Z

```

Try it

# Answer
> 1 votes
# Python 3, 9 bytes

```
str.upper

```

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

---

# Python 3, 50 bytes

Saved many bytes thanks to @FelipeNardiBatista.

```
lambda k:''.join(chr(ord(c)-32*(c>'_'))for c in k)

```

Try it online!

# Answer
> 1 votes
# Pyth, 3 bytes

```
rQ1

```

Equivalent to `str.upper` in python.

# Answer
> 1 votes
# Perl 5, 6 bytes

**5 bytes code + 1 for `-p`.**

```
$_=uc

```

Try it online!

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

```
s=>s.toUpperCase()

```

# Answer
> 1 votes
# Mathematica, 11 bytes

```
ToUpperCase

```

# Answer
> 1 votes
# Jelly, 2 bytes

```
Œu

```

Try it online!

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


title: Perfect License Plates

text:
# Question
Title: Perfect License Plates
# Perfect License Plates

Starting a few years ago, I made myself a little game while driving around: checking if nearby license plates are "perfect". It's relatively rare, but exciting when you find one.

To check if a license plate is perfect:

1. Sum up the characters, with A = 1, B = 2, ... Z = 26.
2. Take each consecutive chunk of numerals, and sum them; multiply each of these sums together.

If the values in part 1 and part 2 are equal, congratulations! You've found a perfect license plate!

### Examples

```
License plate: AB3C4F

Digits -> 3 * 4
        = 12
Chars  -> A + B + C + F
        = 1 + 2 + 3 + 6
        = 12
12 == 12 -> perfect!

License plate: G34Z7T

Digits -> (3 + 4) * 7
        = 49
Chars  -> G + Z + T
        = 7 + 26 + 20
        = 53
49 != 53 -> not perfect!

License plate: 10G61

Digits -> (1 + 0) * (6 + 1)
        = 7
Chars  -> G
        = 7
7 == 7 -> perfect!

```

## The Challenge

I used license plates of length 5 and 6 as examples, but this procedure is valid for any plate length. Your challenge is, for a given length N, return the number of perfect license plates of that length. For the purposes of the challenge, a valid license plate is any combination of digits 0-9 and characters A-Z. The plate must contain *both a character and a numeral* to be considered potentially perfect. For checking purposes, here are the values I got (though I can't be 100% about their correctness, hahaha)

```
N < 2: 0
N = 2: 18
N = 3: 355
N = 4: 8012

```

### Notes

If somehow it makes the problem simpler in your language, you may output the **proportion** of perfect license plates for a given N, to at least 2 significant digits.

```
N < 2: 0
N = 2: 0.0138888...
N = 3: 0.0076088...
N = 4: 0.0047701...

```

OR, you may output the equivalent value **mod 256**

```
N < 2: 0
N = 2: 18
N = 3: 99
N = 4: 76

```

Shortest wins!

# Answer
> 9 votes
# Python 3.6, 150 bytes

```
f=lambda n,t=-1,p=-1,a=0:sum(f(n-1,*((t,c+p*(p>=0),a),((t<0 or t)*(p<0 or p),-1,a-c))[c<0])for c in range(-26,10))if n else 0<(t<0 or t)*(p<0 or p)==a

```

results:

```
f(2) = 18
f(3) = 355
f(4) = 8012
f(5) = 218153

```

Ungolfed version with explanation:

```
digits=[*range(10)]
letters=[*range(1,27)]

def f(n, dt=-1, dp=-1, lt=0):
    if n:
        for d in digits:
            yield from f(n - 1,
                         dt,
                         d if dp < 0 else dp + d,
                         lt
                         )

        for l in letters:
            yield from f(n - 1,
                         dp if dt < 0 else dt if dp < 0 else dt*dp,
                         -1,
                         lt + l
                         )
    else:
        yield 0 < lt == (dt<0 or dt)*(dp<0 or dp)

```

The problem boils down to searching a tree in which each level of the tree corresponds to a position in a license plate number and each node has 36 children (10 digits and 26 letters). The function does a recursive search of the tree, accumulating the values for the digits and letters as it goes.

```
n is the number of levels to search.
dp accumulates the sum of a group of digits.
dt accumulates the product of the digit sums.
lt accumulates the sum of the letter values.

For dp and dt, a value < 0 indicates it is not initialized.

```

Golf included, converting the for loops to sums of generators:

```
sum(f(n-1,
      dt,
      d if dp < 0 else dp + d,
      lt) for d in digits)
+
sum(f(n-1,
      dp if dt<0 else dt if dp<0 else dt*dp,
      -1,
      lt+l) for l in letters)

```

Then combining the generators. Encode letters, A to Z, as -1 to -26 and digits as 0 to 9. So the sum becomes:

```
sum(f(n-1, *args) for c in range(-26, 10)),

```

where args is:

```
((dp if dt<0 else dt if dp<0 else dt*dp, -1, lt-l) if c <0 else
 (dt, d if dp<0 else dp+d, lt))

```

The rest of the golfing is converting the function to a lambda, shortening variable names, and simplifying expressions.

# Answer
> 6 votes
# Dyalog APL, ~~57~~ 56 bytes

```
+/(+/0⌈a-9)=×/c*⍨-2-/0,⌈\(+\a×b)×c←2>/0,⍨b←9≥a←↑1↓,⍳⎕⍴36

```

(assumes `⎕io←0`)

`a` matrix of all valid licence plates (except `00...0`) encoded with: 0-9 for digits, 10-35 for letters

`b` bitmask for where digits occur

`c` bitmask for the last digit in every group of consecutive digits

# Answer
> 4 votes
# Python 2, ~~359~~ 295 bytes

Rather long; this is the trivial solution. I'm confident this is correct, though it does not match the test cases in the challenge. The solutions I'm getting match Dada's answers.

```
import itertools as i,re as r,string as s
print len([''.join(x)for x in i.product(s.lowercase+s.digits,repeat=input())if(lambda t:r.search('\\D',t)and r.search('\\d',t)and reduce(int.__mul__,[sum(map(int,k))for k in r.split('\\D+',t)if k])==sum([k-96 for k in map(ord,t) if k>96]))(''.join(x))])

```

-64 bytes thanks to suggestions from @numbermaniac

# Answer
> 4 votes
# Python 2, ~~291~~ ~~287~~ ~~276~~ 273 bytes

```
lambda n:sum(1for x in s.product(y+z,repeat=n)if(lambda p,s=set:reduce(int.__mul__,[sum(map(int,i))for i in re.findall(r"\d+",p)],1)==sum(ord(i)-64for i in p if ord(i)>64)and s(p)&s(y)and s(p)&s(z))(''.join(x)))
import re,itertools as s,string as t
y=t.uppercase
z=t.digits

```

Try it online!

---

Results:

```
0 0
1 0
2 18
3 355
4 8012

```

# Answer
> 3 votes
# Perl 5, 117 bytes

116 bytes of code + `-p` flag.

```
$"=",";@F=(A..Z,0..9);map{$r=1;$r*=eval s/./+$&/gr for/\d+/g;$r+=64-ord for/\pl/g;$\+=!$r*/\pl/*/\d/}glob"{@F}"x$_}{

```

Try it online!

It feels quite suboptimal, but I 'm out of ideas right now.
The code itself is very inefficient as it computes every permutation of `a..z,0..9` of length `n` (it takes roughly 1 second for `n=3`, ~15 seconds for `n=4` and ~7 minutes for `n=5`).
The algorithm is quite straight forward: for every possible plate of size `n` (generated with `glob"{@F}"x$_` \- the `glob` operator is quite magic), `$r*=eval s/./+$&/gr for/\d+/g;` computes the product of every chunk of digits, and `$r+=64-ord for/\pl/g` subtract to it the weight of the letters. Then, we increment the counter `$\` if the `$r` is `0` (`!$r`) and if the plate contains numbers and letters (`/\pl/*/\d/`). `$\` is implicitly printed at the end thanks to `-p` flag.

Note that the numbers I obtain are `n=2 -> 18`, `n=3 -> 355`, `n=4 -> 8012`, `n=5 -> 218153`. I'm pretty sure these are the right ones, but I might be mistaken, in which case let me know and I'll deleted this answer.

# Answer
> 3 votes
# APL (Dyalog), 71 bytes

Full program body. Prompts for N. N≥4 requires huge amounts of memory and computation.

```
+/((+/⊢⍳∩)∘⎕A=(×/'\d+'⎕S{+/⍎¨⍵.Match}))¨l/⍨∧⌿∨/¨c∘.∊l←,(∊c←⎕D⎕A)∘.,⍣⎕⊂⍬

```

Try it online!

# Answer
> 3 votes
## GAP, 416 bytes

Won't win on code size, and far from constant time, but uses math to speed up a lot!

```
x:=X(Integers);
z:=CoefficientsOfUnivariatePolynomial;
s:=Size;

f:=function(n)
 local r,c,p,d,l,u,t;
 t:=0;
 for r in [1..Int((n+1)/2)] do
  for c in [r..n-r+1] do
   l:=z(Sum([1..26],i->x^i)^(n-c));
   for p in Partitions(c,r) do
    d:=x;
    for u in List(p,k->z(Sum([0..9],i->x^i)^k)) do
     d:=Sum([2..s(u)],i->u[i]*Value(d,x^(i-1))mod x^s(l));
    od;
    d:=z(d);
    t:=t+Binomial(n-c+1,r)*NrArrangements(p,r)*
         Sum([2..s(d)],i->d[i]*l[i]);
   od;
  od;
 od;
 return t;
end;

```

To squeeze out the unnecessary whitespace and get one line with 416 bytes, pipe through this:

```
sed -e 's/^ *//' -e 's/in \[/in[/' -e 's/ do/do /' | tr -d \\n

```

My old "designed for Windows XP" laptop can calculate `f(10)` in less than one minute and go much further in under an hour:

```
gap> for i in [2..15] do Print(i,": ",f(i),"\n");od;
2: 18
3: 355
4: 8012
5: 218153
6: 6580075
7: 203255386
8: 6264526999
9: 194290723825
10: 6116413503390
11: 194934846864269
12: 6243848646446924
13: 199935073535438637
14: 6388304296115023687
15: 203727592114009839797

```

## How it works

Suppose that we first only want to know the number of perfect license plates fitting the pattern `LDDLLDL`, where `L` denotes a letter and `D` denotes a digit. Assume we have a list `l` of numbers such that `l[i]` gives the number of ways the letters can give the value `i`, and a similar list `d` for the values we get from the digits. Then the number of perfect licence plates with common value `i` is just `l[i]*d[i]`, and we get the number of all perfect licence plates with our pattern by summing this over all `i`. Let's denote the operation of getting this sum by `l@d`.

Now even if the best way to get these lists was to try all combinations and count, we can do this independently for the letters and the digits, looking at `26^4+10^3` cases instead of `26^4*10^3` cases when we just run through all plates fitting the pattern. But we can do much better: `l` is just the list of coefficients of `(x+x^2+...+x^26)^k` where `k` is the number of letters, here `4`.

Similarly, we get the numbers of ways to get a sum of digits in a run of `k` digits as the coefficients of `(1+x+...+x^9)^k`. If there is more than one run of digits, we need to combine the corresponding lists with an operation `d1#d2` that at position `i` has as value the sum of all `d1[i1]*d2[i2]` where `i1*i2=i`. This is the Dirichlet convolution, which is just the product if we interpret the lists as coefficients of Dirchlet series. But we have already used them as polynomials (finite power series), and there is no good way to interpret the operation for them. I think this mismatch is part of what makes it hard to find a simple formula. Let's use it on polynomials anyway and use the same notation `#`. It is easy to compute when one operand is a monomial: we have `p(x) # x^k = p(x^k)`. Together with the fact that it is bilinear, this gives a nice (but not very efficient) way to compute it.

Note that `k` letters give a value of at at most `26k`, while `k` single digits can give a value of `9^k`. So we will often get unneeded high powers in the `d` polynomial. To get rid of them, we can compute modulo `x^(maxlettervalue+1)`. This gives a big speed up and, though I didn't immediately notice, even helps golfing, because we now know that the degree of `d` is not bigger then that of `l`, which simplifies the upper limit in the final `Sum`. We get an even better speed up by doing a `mod` calculation in the first argument of `Value` (see comments), and doing the whole `#` computation at a lower level gives an incredible speed up. But we're still trying to be a legitimate answer to a golfing problem.

So we have got our `l` and `d` and can use them to compute the number of perfect licence plates with pattern `LDDLLDL`. That is the same number as for the pattern `LDLLDDL`. In general, we can change the order of the runs of digits of different length as we like, `NrArrangements` gives the number of possibilities. And while there must be one letter between the runs of digits, the other letters are not fixed. The `Binomial` counts these possibilities.

Now it remains to run through all possible ways of having lengths of runs digits. `r` runs through all numbers of runs, `c` through all total numbers of digits, and `p` through all partitions of `c` with `r` summands.

The total number of partitions we look at is two less than the number of partitions of `n+1`, and the partition functions grows like `exp(sqrt(n))`. So while there are still easy ways to improve the running time by reusing results (running through the partitions in a different order), for a fundamental improvement we need to avoid looking at each partition seperately.

## Computing it fast

Note that `(p+q)@r = p@r + q@r`. On its own, this just helps avoid some multiplications. But together with `(p+q)#r = p#r + q#r` it means that we can combine by simple addition polynomials corresponding to different partitions. We can't just add them all, because we still need to know with which `l` we have to `@`-combine, which factor we have to use, and which `#`-extensions are still possible.

Let's combine all polynomials corresponding to partitions with the same sum and length, and already account for the multiple ways of distributing the lengths of runs of digits. Different from what I speculated in the comments, I don't need to care about the smallest used value or how often it is used, if I make sure that I won't extend with that value.

Here is my C++ code:

```
#include<vector>
#include<algorithm>
#include<iostream>
#include<gmpxx.h>

using bignum = mpz_class;
using poly = std::vector<bignum>;

poly mult(const poly &a, const poly &b){
  poly res ( a.size()+b.size()-1 );
  for(int i=0; i<a.size(); ++i)
    for(int j=0; j<b.size(); ++j)
      res[i+j]+=a[i]*b[j];
  return res;
}

poly extend(const poly &d, const poly &e, int ml, poly &a, int l, int m){
  poly res ( 26*ml+1 );
  for(int i=1; i<std::min<int>(1+26*ml,e.size()); ++i)
    for(int j=1; j<std::min<int>(1+26*ml/i,d.size()); ++j)
      res[i*j] += e[i]*d[j];
  for(int i=1; i<res.size(); ++i)
    res[i]=res[i]*l/m;
  if(a.empty())
    a = poly { res };
  else
    for(int i=1; i<a.size(); ++i)
      a[i]+=res[i];
  return res;
}

bignum f(int n){
  std::vector<poly> dp;
  poly digits (10,1);
  poly dd { 1 };
  dp.push_back( dd );
  for(int i=1; i<n; ++i){
    dd=mult(dd,digits);
    int l=1+26*(n-i);
    if(dd.size()>l)
      dd.resize(l);
    dp.push_back(dd);
  }

  std::vector<std::vector<poly>> a;
  a.reserve(n);

  a.push_back( std::vector<poly> { poly { 0, 1 } } );
  for(int i=1; i<n; ++i)
    a.push_back( std::vector<poly> (1+std::min(i,n+i-i)));
  for(int m=n-1; m>0; --m){
    //    std::cout << "m=" << m << "\n";
    for(int sum=n-m; sum>=0; --sum)
      for(int len=0; len<=std::min(sum,n+1-sum); ++len){
        poly d {a[sum][len]} ;
        if(!d.empty())
          for(int sumn=sum+m, lenn=len+1, e=1;
              sumn+lenn-1<=n;
              sumn+=m, ++lenn, ++e)
            d=extend(d,dp[m],n-sumn,a[sumn][lenn],lenn,e);
      }
  }
  poly let (27,1);
  let[0]=0;
  poly lp { 1 };
  bignum t { 0 };
  for(int sum=n-1; sum>0; --sum){
    lp=mult(lp,let);
    for(int len=1; len<=std::min(sum,n+1-sum); ++len){
      poly &a0 = a[sum][len];
      bignum s {0};
      for(int i=1; i<std::min(a0.size(),lp.size()); ++i)
        s+=a0[i]*lp[i];
      bignum bin;
      mpz_bin_uiui( bin.get_mpz_t(), n-sum+1, len );
      t+=bin*s;
    }
  }
  return t;
}

int main(){
  int n;
  std::cin >> n;
  std::cout << f(n) << "\n" ;
}

```

This uses the GNU MP library. On debian, install `libgmp-dev`. Compile with `g++ -std=c++11 -O3 -o pl pl.cpp -lgmp -lgmpxx`. The program takes its argument from stdin. For timing, use `echo 100 | time ./pl`.

At the end `a[sum][length][i]` gives the number of ways in which `sum` digits in `length` runs can give the number `i`. During computation, at the beginning of the `m` loop, it gives the number of ways that can be done with numbers greater than `m`. It all starts with `a[0][0][1]=1`. Note that this is a superset of the numbers we need to compute the function for smaller values. So at almost the same time, we could compute all values up to `n`.

There is no recursion, so we have a fixed number of nested loops. (The deepest nesting level is 6.) Each loop goes through a number of values that is linear in `n` in the worst case. So we need only polynomial time. If we look closer at the nested `i` and `j` loops in `extend`, we find an upper limit for `j` of the form `N/i`. That should only give a logarithmic factor for the `j` loop. The innermost loop in `f` (with `sumn` etc) is similar. Also keep in mind that we compute with numbers that grow fast.

Note also that we store `O(n^3)` of these numbers.

Experimentally, I get these results on reasonable hardware (i5-4590S): `f(50)` needs one second and 23 MB, `f(100)` needs 21 seconds and 166 MB, `f(200)` needs 10 minutes and 1.5 GB, and `f(300)` needs one hour and 5.6 GB. This suggests a time complexity better than `O(n^5)`.

# Answer
> 2 votes
# Scala, 265 bytes

```
(n:Int)=>{val i=('A'to'Z')++('0'to'9');Seq.fill(n)(i).flatten.combinations(n).flatMap(_.permutations).map(_.mkString).count(l=>"(?=.*[A-Z])(?=.*\\d)".r.findAllIn(l).size>0&&l.map(_-64).filter(_>0).sum==l.split("[A-Z]").filter(""<).map(_.map(_-48).sum).reduce(_*_))}

```

**Explanations :**

```
(n:Int) => {
    val i = ('A' to 'Z') ++ ('0' to '9');                       // All license plates available characters.
    Seq.fill(n)(i).flatten                                      // Simulate combination with repetition (each character is present n times)
        .combinations(n)                                        // and generate all combinations of size n (all license plates).
        .flatMap(_.permutations)                                // For each combination, generate all permutations (ex. : Seq('A', '1') => Seq('A', '1') and Seq('1', 'A')), and
        .map(_.mkString)                                        // convert each permutation to String (Seq('A', '1') => "A1").
        .count ( l =>                                           // Then count all strings having :
            "(?=.*[A-Z])(?=.*\\d)".r.findAllIn(l).size > 0 &&   // at least 1 character and 1 digit and
            l.map(_ - 64).filter(_ > 0).sum ==                  // a sum of characters (> 'A' or > 64) equals to
            l.split("[A-Z]").filter(""<)
                .map(_.map(_ - 48).sum)
                .reduce(_*_)                                    // the product of sum of digits groups (split String by letters to get digits groups)
        )
}

```

*Notes :*

* `-64` and `-48` are used to transform a `Char` (respectively letter and digit) to its `Int` value (`'A' - 64 = 1`, `'B' - 64 = 2`, ..., `'9' - 48 = 9`)
* The filter in `l.split("[A-Z]").filter(""<)` is used to eliminate `""` values if `l` starts with a letter (example : `"A1".split("[A-Z]") => Array("", 1)`). There might be a better and shorter solution

**Test cases :**

```
val f = (n:Int) => ...  // assign function
(1 to 5).foreach ( i =>
    println(s"N = $i: ${f(i)}")
)

```

**Results :**

```
N = 1: 0
N = 2: 18
N = 3: 355
N = 4: 8012
N = 5: 218153

```

The function is pretty slow for `n > 4` since all combinations must be generated.

# Answer
> 2 votes
# Java, ~~382~~ 365 bytes

* Saved 17 bytes, thanks to **Kevin Cruijssen**

**Golfed**

```
int h(String s){int m=0;for(int c:s.toCharArray())m+=c-48;return m;}
int g(String t){int d=1,c=0;for(String s:t.split("[^0-9]"))d*=h(s);for(String s:t.split("[^A-Z]"))c+=s.charAt(0)-65;return d==c?1:0;}
int f(String t,int n){int m=0;if(t.length()==n)return g(t);for(int d=48;d<58;)m+=f(t+d++,n);for(int c=65;c<91;)m+=f(t+c++,n);return m;}
int s(int n){return f("",n);}

```

**Detailed**

```
// return sum of adjecent digits
int h(String s)
{
    int sum = 0;
    for(char c : s.toCharArray()) sum += c-'0';
    return sum;
}

// check if perfect
int g(String t)
{
    int d = 1;
    int c = 0;

    for(String s : t.split("[^0-9]")) d *= h(s);
    for(String s : t.split("[^A-Z]")) c += s.charAt(0)-'A';

    return d == c ? 1 : 0;
}

// tree of enumerations
int f(String t, int n)
{
    // base case
    if(t.length() == n)
    {
        return g(t);
    }

    // enumeration
    int sum = 0;
    for(char d='0'; d<='9'; d++) sum += f(t+d, n);
    for(char c='A'; c<='Z'; c++) sum += f(t+c, n);

    return sum;
}

int s(int n){ return f("",n); }

```

# Answer
> 0 votes
# Pyth, 55 bytes

```
FNQI<xrG1N0=+ZsN).?=+YZ=Z0;qu*G?HH1Y1sm?<xrG1d00hxrG1dQ

```

---
Tags: code-golf, sequence
---


title: Can I Settle Down?

text:
# Question
Title: Can I Settle Down?
In The Settlers of Catan board game, there are five resource types: Brick, Log, Ore, Wheat, and Sheep. Building a settlement costs a Brick, a Log, a Wheat, and a Sheep. However, you can also trade in four identical resources to get a resource of a different type. For instance, if you had four ores in your hand, you could trade all of them in and get one sheep.

Your job is to determine whether or not I can build a settlement, given my hand.

## Your Task

Input will be a sequence of the letters `B`, `L`, `O`, `W`, and `S`, taken in any reasonable format. These letters correspond to the five resource types given above. You should output whether or not I have the resources necessary to build a settlement, taking into account the possibility of trading four of a kind.

This is , so shortest code in bytes wins.

## Notes

* You do not have to output what trades I need to perform or how many settlements I could build. A simple "yes" or "no" will do.
* You may *not* assume that the input is in any specific order. In particular, you may not assume that resources of the same type are grouped together, so `OBLSO` is a valid input.
* This is , so you may use any value you want to mean "yes" and "no", as long as the two chosen values are distinct and consistent.
* The only rules we're concerned with here are the ones listed above. More complicated Settlers of Catan rules like trading with other players or at harbours are not relevant here.
* The input characters (`B`, `L`, `O`, `W`, `S`) can be substituted with other values if it is easier for your particular language of choice, so long as there are five distinct inputs. If you use other input values, please specify them in your answer.

## Examples

```
BLWS -> Yes
OOOOWLB -> Yes (trade four O for a S)
OOW -> No
BBBO -> No
(empty input) -> No
BBBBLW -> No
BBBBBLW -> Yes (trade four B for a S)
OOOOOOOOOOOOOOOO -> Yes (sixteen O; trade for B, L, W, S)
BLBLBLBLBL -> Yes (trade L for W and B for S)
BLSWBLSWBLSW -> Yes (extra, unused resources are ignored)

```

# Answer
# Python 2, 54 bytes

```
lambda s:sum((s+"BLSW"*3).count(n)/4for n in"BLSWO")>3

```

Try it online!

For each of our resources, we count the number of *“freedoms”* given by having *n* of that resource. A freedom represents an *opportunity* to fill one of the brick-log-wheat-sheep slots we need to fill in order to settle, accounting for the fact that we can convert our resources.

For all of BLSW, having *one* of the resource gives us one such freedom, and every additional excess of 4 gives us another. The freedom-counting rule is like this:

```
* Having 1 brick/log/wheat/sheep gives 1 freedom.
* Having 5 bricks/logs/wheat/sheep gives 2 freedoms.
* Having 9 bricks/logs/wheat/sheep gives 3 freedoms.
* …

```

So *n* bricks/logs/wheat/sheep give ⌊(n+3)/4⌋ freedoms.

For ores, only the excess foursomes count. The freedom-counting rule is like this:

```
* Having 4 ores gives 1 freedom.
* Having 8 ores gives 2 freedoms.
* Having 12 ores gives 3 freedoms.
* …

```

So *n* ores give ⌊n/4⌋ freedoms.

**Theorem:** we can settle if and only if we have ≥ 4 such “freedoms”.

So we count our freedoms and check if there are ≥ 4 of them. To handle counting ores as ⌊n/4⌋ but other resources ⌊(n+3)/4⌋, we artificially inflate the counts for the other resources by 3 and then count ⌊n/4⌋ for all of them. We do this by mapping `(s+"BLSW"*3).count` instead of `s.count`.

**Proof**:

* Suppose we can settle. Then for each of \[B, L, S, W\], we either (a) used 1 of that resource that we already had, or (b) sacrificed 4 of some other resource (including ores) to create it. In either case, we count at least 1 freedom by the above rules. So we have ≥ 4 freedoms.
* Suppose we have 4 freedoms, k of which are due to “excesses” (every freedom from ores is an excess, and every freedom from other resources *past* the first one also is) and 4−k of which are witness of owning at least one brick/log/wheat/sheep (the one that gave the “first freedom”). Then we fill 4−k slots with the brick/log/wheat/sheep that gave us our first freedom, and fill the remaining k slots by converting our excesses. All 4 slots are filled and we can settle. We can obviously still do this if we have *more* than 4 freedoms.

This proof sucks, but I’m sleepy. I’m sure there’s a better explanation.
> 16 votes

# Answer
# Python 2,  ~~52~~  51 bytes

-1 byte thanks to Luke (replace `>=0` with `<0`, inverting the `False`/`True` results)

```
lambda h:sum(~-(h+"O").count(c)/4for c in"BOWLS")<0

```

An unnamed function taking a string of the characters **B**, **O**, **W**, **L**, and **S** (as in the OP) and returning `False` if you can settle or `True` if not.

**Try it online!** (coerces the output to the `yes/no` of the OP).

### How?

This is a port of my Jelly answer. We need to make up for any missing **B**, **W**, **L**, or **S** from the remainder after using one of each of them. As such we can add an extra **O** to our hand, then reduce all the counts by one, then integer divide all counts by four and then sum - if the result is zero or more we can settle (either because there were no missing required resources or because we can trade to acquire the missing one(s)).

```
lambda h:sum(~-(h+"O").count(c)/4for c in"BOWLS")<0
lambda h:                                           - a function that takes h (a string)
                                 for c in"BOWLS"    - for each letter, c, in "BOWLS":
                h+"O"                               -   append "O" to h
               (     ).count(c)                     -   count c instances
              -                                     -   negate
             ~                                      -   bitwise not (this is -x-1)
                               /4                   -   integer divide by 4
                                                    -    (NB: -1 and 0 are not affected)
         sum(                                   )   - sum the five values
                                                 <0 - less than zero? (inverted result)

```
> 8 votes

# Answer
# Pyth, 14 bytes

```
gsm/t/+Q4d4U5Z

```

**Try it here! or Verify all the test cases.**

# Pyth,  ~~31 27 17~~  16 bytes

```
<3s/R4/L+Q*3U4U5

```

**Verify the test cases.**

# How do these work?

### Explanation #1

```
gsm/t/+Q4d4U5Z   - Full program.

  m        U5    - Map over the range [0, 5) with a variable d.
      +Q4        - The input, with a 4 appended (this corresponds to O)
     /   d       - Count the occurrences of the current value in ^.
    t            - Decrement.
   /      4      - Integer division by 4.
 s               - Sum
g            Z   - Is non-negative (is the sum ≥ 0)?
                 - Output implicitly.

```

### Explanation #2

```
<3s/R4/L+Q*3U4U5   - Full program.

          *3U4     - The range [0, 4) repeated 3 times.
        +Q         - The input with ^ appended.
      /L      U5   - Count the occurrences of each element in [0, 5) in ^.
   /R4             - Integer division of each by 4.
  s                - Sum.
<3                 - Is higher than 3?
                   - Output implicitly.

```

---

These are the codes used by my program:

```
B -> 0
L -> 1
S -> 2
W -> 3
O -> 4

```
> 7 votes

# Answer
# Jelly,  ~~13~~  12 bytes

```
;5ċÐ€5’:4S>-

```

A monadic link accepting a list of numbers representing the resources you own and returning `1` if you can settle down or `0` if not.

The resources are `1, 2, 3, 4, 5` where `5` represents **Ore**.

**Try it online!** or see the test-suite (using the OP IO).

### How?

The idea is to first count the resources by type, then reduce all counts of **B**, **L**, **W**, and **S** by one - if we counted none for any of these four then they will now have entries of **-1** \- we need to acquire them from our remaining resources (This is actually achieved by adding an extra **O** (`5`) and reducing *all five* counts by **1**). Next we integer-divide all these values by four to see how many units we may trade for with each of our remaining counts by resource type while not affecting the **-1** and **0** counts (note that **-1** integer-divided by four is **-1**, not **0**). Lastly we add up the values and check if the result is greater than or equal to zero (here greater than **-1** can be used since we always have integers).

```
;5ċÐ€5’:4S>- - Link: list of numbers (BLWSO:12345) e.g. [3,2,2,2,2,2,5,5,5,5] (WLLLLLOOOO)
;5           - concatenate a five                       [3,2,2,2,2,2,5,5,5,5,5]
     5       - literal 5
   Ð€        - map across implicit range(5) = [1,2,3,4,5]:
  ċ          -   count                                  [ 0, 5, 1, 0, 5]
      ’      - decrement (vectorises)                   [-1, 4, 0,-1, 4]
       :4    - integer divide by four                   [-1, 1, 0,-1, 1]
         S   - sum                                      0
           - - literal -1                              -1
          >  - greater than?                            1

```
> 7 votes

# Answer
# Java 8, 101 bytes

Lambda from `int[]` to `boolean`. Assign to `Function<int[], Boolean>`.

```
a->{int h,f[]=new int[5],i=0;for(int x:a)f[x]++;for(h=f[4]/4;i<4;)h+=--f[i]>>-1|f[i++]/4;return~h<0;}

```

Try It Online

## Input and output

Input is an array of integers from 0 to 4, inclusive. 4 represents Ore, and the other mappings are immaterial. My test cases are direct translations of those in the question, with 0 as Brick, 1 as Log, 2 as Wheat, and 3 as Sheep.

Output is whether a settlement can be built.

## Ungolfed

```
a -> {
    int
        h,
        f[] = new int[5],
        i = 0
    ;
    for (int x : a)
        f[x]++;
    for (h = f[4] / 4; i < 4; )
        h += --f[i] >> 31 | f[i++] / 4;
    return ~h < 0;
}

```

## Explanation

`h` is the number of resource quadruples available to trade. We iterate over each resource type (except Ore), incrementing `h` for each quadruple of extra resources we have, and decrementing where no resources are present. Then our result is whether `h` is nonnegative.

The line

```
h += --f[i] >> 31 | f[i++] / 4;

```

adjusts `h` appropriately regardless of whether there are no resources (shortage) or there is at least one resource (surplus). `f[i]` is decremented to account for the required resource in the surplus case, producing -1 in the shortage case. The signed right shift reduces the expression to 0 (surplus case) or -1 (shortage case), so that a bitwise OR with the number `f[i++] / 4` of surplus quadruples (in the surplus case) has no effect in the shortage case but results in the number itself in the surplus case.

## Acknowledgments

* -9 bytes thanks to Nevay, master of bits
> 5 votes

# Answer
# Retina, 34 bytes

```
^
BBBLLLWWWSSS
O`.
((.)\2{3}.*){4}

```

Try it online! Explanation: Building a settlement requires 4 resources which are either your first B, L, W, or S, or any other 4 resources of the same type. This is equivalent to adding three of each of those four types of resources, and then counting to see whether you have four sets of four.
> 4 votes

# Answer
# Jelly, 23 bytes

```
œ-4R¤©Ġs€4ẎL€>3+®e€$S>3

```

Try it online!

Refer to the following table for the values:

```
B: 1
L: 2
O: 5
W: 3
S: 4

```
> 3 votes

# Answer
# Retina, 43 bytes

```
O`.
O{4}
a
}`([^a])\1{4}
$1a
O

D`[^a]
.{4}

```

Try it online!
> 2 votes

# Answer
# Python 3, 79 78 bytes

**Edit:** -1 byte thanks to @Mr.Xcoder

```
lambda x:3<sum((a>0)+~-a*(a>1)//4for a in map(x.count,"BLSW"))+x.count("O")//4

```

Try it online!
> 2 votes

# Answer
# MATL, 19 bytes

```
Oh!5:=s4&\w4:)ghs3>

```

Input is a numeric row vector where the letters are represented as numbers as follows:

```
B: 1
L: 2
W: 3
S: 4
O: 5

```

Output is `1` for truthy, `0` for falsy.

Try it online!: verify all test cases.

### How it works

1. Count ocurrences of each resource.
2. Div-mod them by 4.
3. Count how many of the remainders for the first four resources (letters `BLWS`) are nonzero. This gives a number *c*.
4. Sum the quotients. This gives a number *s*.
5. Output whether *c*+*s* ≥ 4.

### Commented code

```
Oh     % Append 0 to implicit input. This is just in case inpout is empty
!      % Convert into column vector
5:     % Push row vector [1 2 3 4 5]
=      % Compare for equality, element-wise with broadcast
s      % Sum of each column. Gives number of times that each entry of
       % [1 2 3 4 5] appears in the input
4&\    % Mod-div 4, element-wise. Pushes vector of remainders and then vector
       % of quotients of division by 4
w      % Swap. Brings remainders to top
4:)    % Get the first four entries
g      % Convert to logical. This transforms non-zero values into 1
h      % Concatenate with vector of quotients
s      % Sum
3>     % Does the result exceed 3? Implicitly display

```
> 2 votes

# Answer
# \>\<\>, 61 bytes

```
510ap\~1(n;
1+$ap> i:0(?v8%:ag
0:ga:v?=5:+1<$-}$,4-%4:-}-${:)

```

Try it online!

Uses the following resource mapping:

```
O -> 0
B -> 1
L -> 2
W -> 3
S -> 4

```

It doesn't really matter what mapping is used, as long as they're in the range `0-4`, and `0` is used for O. Makes use of the fact that looking for the combination `BLWS` is the same as looking for the combination `OBLWS` while already having an `O` in hand.
> 2 votes

# Answer
# 05AB1E, 19 bytes

0 -\> Ore
1 -\> Brick
2 -\> Log
3 -\> Wheat
4 -\> Sheep

Returns 0 when false, and 1 otherwise.

```
{γvyDĀi¼¨}g4÷}¾)O3›

```

Try it online!

**Explanation:**

```
{γvyDĀi¼¨}g4÷}¾)O3› Implicit input, e.g. 0030201
{                   Sort -> 0000123
 γ                  Split into chunks of consecutive elements: [0000, 1, 2, 3]
  vy                For each chunk...
    DĀ                 ...is different than 0?
      i¼¨}                ...if true: increment the counter by 1, and
                              remove 1 element from the chunk
          g4÷         ...divide the number of elements by 4
             }      End For
              ¾     Push the counter
               )    Wrap the entire stack in a list
                O   Sum of that list
                 3> True if > 3
                    Implicit output

```

# Non-competive solution: 17 bytes

There was a bug in 05AB1E when I first submitted that solution, where some operators badly handled empty inputs. This resulted in this solution answering `1` on an empty input. This has now been fixed, so this solution works just fine.

The difference here is that we add an ore prior to removing one of each resource, indiscriminately, counting the number of resources removed that way. We then decrement the counter by 1 to get the correct number of B, L, W and S.

```
0«{γε¨g4÷¼}O¾<+3›

```

Try it online!
> 1 votes

# Answer
# Kotlin, ~~131~~ 129 bytes

## Submission

```
fun r(i:String):Any=i.split("").groupingBy{it}.eachCount().map{when(it.key){
""->0
"O"->it.value/4
else->(it.value+3)/4}}.sum()>3

```

## Test

```
fun r(i:String):Any=i.split("").groupingBy{it}.eachCount().map{when(it.key){
""->0
"O"->it.value/4
else->(it.value+3)/4}}.sum()>3

data class TestData(val input:String, val output:Boolean) {
    fun run() {
        val out = r(input)
        if (out != output) {
            throw AssertionError("Failed test: ${this} -> $out")
        }
    }
}
fun main(args: Array<String>) {
    listOf(

            TestData("BLWS", true),
            TestData("OOOOWLB", true),
            TestData("OOW", false),
            TestData("BBBO", false),
            TestData("", false),
            TestData("BBBBLW", false),
            TestData("BBBBBLW", true),
            TestData("OOOOOOOOOOOOOOOO", true),
            TestData("BLBLBLBLBL", true),
            TestData("BLSWBLSWBLSW", true)
    ).forEach(TestData::run)
    println("Test passed")
}

```

**Cannot work on TryItOnline, but works on** try.kotlinlang.org
> 0 votes

# Answer
# JavaScript (SpiderMonkey), 116 bytes

```
s=>Array.from("BLOWS").reduce((m,c)=>Math.floor(((s+"BLSW".repeat(3)).match(new RegExp(c,'g'))||"").length/4)+m,0)>3

```

Try it online!

Super Clunky bad answer. I'm sure it could be cleaned up more. Method inspired by Lynn's answer in this thread.
> 0 votes

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


title: Let's converge to 9!

text:
# Question
Title: Let's converge to 9!
Given an integer ***n \> 2***, print or return the smallest non-negative integer ***k*** such that ***a(n, k) = 9***, where ***a(n, k)*** is defined by:

* ***a(n, 0) = n***
* ***a(n, k+1) =***
    + ***a(n, k) / 2 + 1*** if ***a(n, k)*** is even
    + the sum of the digits of ***a(n, k)²*** (in base 10) if ***a(n, k)*** is odd

## Examples

For ***n = 5***, the expected output is ***k = 4***:

```
a(5, 0) = 5
a(5, 1) = 7  (5² = 25 and 2 + 5 = 7)
a(5, 2) = 13 (7² = 49 and 4 + 9 = 13)
a(5, 3) = 16 (13² = 169 and 1 + 6 + 9 = 16)
a(5, 4) = 9  (16 / 2 + 1)

```

For ***n = 40***, the expected output is ***k = 2***:

```
a(40, 0) = 40
a(40, 1) = 21 (40 / 2 + 1)
a(40, 2) = 9  (21² = 441 and 4 + 4 + 1 = 9)

```

## Clarifications and rules

* The input is guaranteed to be greater than 2.
* Your program should theoretically work for any value of ***n***. (In practice, it may be limited by the maximum integer size supported by your language.)
* ***k*** may be either 0-indexed or 1-indexed. Please state it in your answer.
* This is , so the shortest answer in bytes wins!

## First values

Below are the first values from ***n = 3*** to ***n = 422***, with ***k*** 0-indexed. (For 1-indexing, just add `1` to these values.)

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

```

# Answer
# Husk, 13 bytes

```
€9¡?o→½ȯΣd□¦2

```

This is 1-indexed. Try it online!

## Explanation

Nothing too fancy here.

```
€9¡?o→½ȯΣd□¦2  Implicit input, say n = 5
  ¡            Iterate the following function:
   ?       ¦2   If divisible by 2,
    o→½         then halve and increment,
       ȯΣd□     else square, take digits and get their sum.
               This gives an infinite sequence: [5,7,13,16,9,9,9,9,9..
€9             1-based index of 9; print implicitly.

```
> 6 votes

# Answer
# Perl 6, 41 bytes (40 chars)

```
{+($_,{$_%2??[+] $_².comb!!$_/2+1}...9)}

```

Try it online!

This uses 1-indexing of k's, so it gives 1 higher answers than the examples in OP. If this is not what the 1-indexing means, I'll have to add 1 byte more.

**Explanation**: It's an anonymous function. We just use the Perl 6's facility for generating lists using recursion :—). It looks like this: `(first element),(block that takes the previous element and gives the next)...(end condition)`. In this case, the first element is `$_` (argument of the main function) and the end condition is `9` (fulfilled when we generate a 9). In the middle block, we use `$_` to refer to its argument ( = the previous element of the sequence). The `?? !!` is the old ternary operator (better known as `? :`). Finally, we take the length of this list by forcing numerical context by `+(...)`.

The last weird thing here is the sum of digits. Numbers are `Cool` (behave both like strings and numbers), so we use a string method `.comb` on `$_²` (give list of characters = digits), then adding the characters up (that converts them back to numbers).
> 10 votes

# Answer
# Python 2, ~~129~~ ~~126~~ ~~76~~ ~~68~~ ~~67~~ ~~64~~ ~~54~~ 53 bytes

*-3 bytes thanks to Jonathan Frech. -8 bytes thanks to Maltysen. -7 bytes thanks to Jonathan Allan. -1 byte thanks to Mr. Xcoder.*

```
f=lambda n:n-9and-~f(n%2*sum(map(int,`n*n`))or 1+n/2)

```

Try it online!

From somebody who probably doesn't know enough math, this seems completely arbitrary. :P
> 7 votes

# Answer
# Jelly, 17 bytes

```
²DSµH‘$Ḃ?ßµ-n9$?‘

```

Try it online!

Straight-forward approach. Uses 0-based indexing.

## Explanation

```
²DSµH‘$Ḃ?ßµ-n9$?‘  Input: n
               ?   If
            n9$      n != 9
          µ        Then
        ?            If
       Ḃ               n % 2 == 1
   µ                 Then
²                      Square
 D                     Decimal digits
  S                    Sum
      $              Else
    H                  Halve
     ‘                 Increment
         ß           Call recursively
                   Else
           -         The constant -1
                ‘  Increment

```
> 7 votes

# Answer
# Mathematica, 58 bytes

1-indexed

```
If[#!=9,#0@If[OddQ@#,Total@IntegerDigits[#^2],#/2+1]+1,0]&

```

Try it online! (in order to work on Mathics, `Tr` is replaced with `Total`)
here is -1 byte version *by @JungHwanMin* (but it doesn't work on mathics so I kept both)

# Mathematica, 57 bytes

```
If[#!=9,#0@If[2∣#,#/2+1,Total@IntegerDigits[#^2]]+1,0]&

```
> 6 votes

# Answer
# JavaScript (ES6), ~~59~~ 50 bytes

0-indexed.

```
f=n=>n-9&&f(n%2?eval([...""+n*n].join`+`):n/2+1)+1

```

---

## Try it

```
o.innerText=(
f=n=>n-9&&f(n%2?eval([...""+n*n].join`+`):n/2+1)+1
)(i.value=5);oninput=_=>o.innerText=f(+i.value)
```

```
<input id=i min=3 type=number><pre id=o>
```

---

## Explanation

The first thing we do is calculate `n-9`. If `n==9` then that, obviously, gives `0` and things stop there. If `n!=9` then `n-9` will give a non-zero value which, being truthy, means we can continue on through the logical AND. We call the function again, passing a new `n` to it, calculated as follows:

```
n%2?

```

If `n` modulo `2` is truthy - i.e., `n` is odd.

```
[...""+n*n]

```

Multiply `n` by itself, convert it to a string and destructure that string to an array of individual characters (digits).

```
 .join`+`

```

Rejoin the characters to a string using `+`, giving us a mathematical expression.

```
eval(                   )

```

Evaluate that expression, giving us the sum of the digits of `n*n`.

```
:n/2+1

```

If `n%2` is falsey (i.e., `n` is even) then we simply divide `n` by `2` and add `1`.

To the result of calling the function again, we then add `1`. So, using an initial input of `5`, the process goes as follows:

```
f(5)
= -4&&f(7)+1
= -2&&(f(13)+1)+1
=  4&&((f(16)+1)+1)+1
=  7&&(((f(9)+1)+1)+1)+1
=     (((0+1)+1)+1)+1
= 4

```
> 6 votes

# Answer
# Jelly,  ~~16~~  15 bytes

-1 byte thanks to miles (use of ternary if)

```
²DSµH‘µḂ?_9$Ð¿L

```

A monadic link taking and returning numbers.
**1-indexed**

**Try it online!** or see a test-suite (coerces results to be 0-indexed and formats like OP code-block)

### How?

```
²DSµH‘µḂ?_9$Ð¿L - Link: number, n
            Ð¿  - collect results in a list while:
           $    -   last two links as a monad:
         _9     -     subtract nine
        ?       -   if:
       Ḃ        -     bit - current loop input modulo by 2 (1 if odd, 0 if even)
   µ            -   ...then:
²               -     square the current loop input
 D              -     cast to a list of its decimal digits
  S             -     sum
      µ         -   ...else:
    H           -     halve current loop input
     ‘          -     increment
              L - length (get the number of results collected
                -         - this includes the 9, so is 1-indexed w.r.t. k)

```
> 4 votes

# Answer
## Haskell, ~~62~~ 59 bytes

```
f 9=0
f a=1+f(cycle[div a 2+1,sum[read[d]|d<-show$a^2]]!!a)

```

Try it online!

Edit: -3 bytes thanks to @Ørjan Johansen.
> 4 votes

# Answer
# Perl 5, 56 + 1 (-n) = 57 bytes

```
$|++,$_=$_%2?eval$_**2=~s/./+$&/gr:1+$_/2while$_-9;say$|

```

Try it online!
> 2 votes

# Answer
# 05AB1E, 16 bytes

```
[Ð9Q#Èi2÷>ënSO]N

```

Try it online!

**Explanation**

```
[                  # start a loop
 Ð                 # triplicate current number
  9Q#              # if it equals 9, break
     Èi            # if even
       2÷>         # divide by 2 and increment
          ë        # else
           n       # square
            SO     # sum digits
              ]    # end loop
               N   # push the iteration counter N

```
> 2 votes

# Answer
# Japt, ~~22~~ 21 bytes

0-indexed.

```
NcUÆ=v ?U/2Ä:U²ìxÃ b9

```

Try it

---

## Explanation

Implicit input of integer `U`.

```
UÆ             Ã

```

Generate an array of integers from `0` to `U-1` and pass each through a function.

```
=

```

Set the value of `U`.

```
v ?

```

If `U` is divisible by 2.

```
U/2Ä

```

`U` divided by 2, plus 1 (`Ä`).

```
:U²ìx

```

Else: `U` to the power of 2 (`²`), split to an array of digits (`ì`) and reduced by addition (`x`).

```
Nc

```

Append the resulting array to the array of inputs.

```
b9

```

Find the index of the first occurrence of `9` in the array. Implicitly output the result.
> 1 votes

# Answer
# VB.NET (.NET 4.5.2), 107 + 20 (imports) = 117 bytes

Requires `Imports System.Linq`

```
Function A(n)
While n<>9
n=If(n Mod 2=0,n/2+1,CStr(n^2).Sum(Function(c)Val(c)))
A+=1
End While
End Function

```

Function which takes `n` as an integer input and returns a 0-based `k`.

Ungolfed:

```
Function A(n) ' input/output types are Object, but we will be casting to integer
    'A = 0 ' VB will create an implicit variable with the same name as the function

    ' loop until a(n, k) = 9
    ' using n as the variable to store a(n, k)
    While n <> 9

        n = If(n Mod 2 = 0, ' equivalent to c# ternary ?: operator

            n / 2 + 1, ' even case

            CStr(n ^ 2).Sum(Function(c) Val(c)))
            ' odd case
            ' cast number to string
            ' then convert each char to the number it represents
            ' and do a linq sum

        A += 1 ' Object + Integer will coerce to an integer
    End While

    ' Where's the return?
    ' That implicit variable with the matching name will get returned if there's no explicit return
End Function

```
> 1 votes

# Answer
# Golfscript, 34 bytes

Try it online!

I really need a better way than I have to add up the digits of a number.

```
~{9-}{.2%{.*`{+48-}*48-}{2/)}if}/,

```
> 1 votes

# Answer
# Pyth,  ~~23~~  22 bytes

For now, this is a recursive function ~~but I'll try to switch to `.W` (functional while) to save bytes instead~~.

```
L&-b9hy|*%b2sj^b2Th/b2

```

**Try it here!** (with additional code to call the function - use **`y`**`<your_number>` \- without spaces)
> 1 votes

# Answer
# Clojure v1.8, ~~124~~ ~~113~~ 112 bytes

0-indexed

```
(fn[n](loop[a n k 0](if(= a 9)k(recur(if(even? a)(+(/ a 2)1)(apply +(map #(-(int %)48)(str(* a a)))))(inc k)))))

```

Try it online!

# Explanation

```
(loop[a n k 0](if(= a 9)...))  Loop until a=9
(if(even? a)(+(/ a 2)1)...)    If even, a(n, k) / 2 + 1 if a(n, k)
(if(even? a)...(apply +(map #(-(int %)48)(str(* a a)))))  If odd, calculate the sum of digits of a(n, k)²
#(-(int %)48)                  Convert character to number

```
> 1 votes

# Answer
# Java 8, ~~110~~ 98 bytes

```
n->{int k=0,s;for(;n!=9;k++){s=0;for(int c:(n*n+"").getBytes())s+=c-48;n=n%2<1?n/2+1:s;}return k;}

```

0-indexed

**Explanation:**

Try it here.

```
 n->             // Method with integer as both input and return-type
   int k=0,      //  Result-integer `k` starting at 0
       s;        //  Sum-integer
   for(;n!=9;    //  Loop (1) as long as `n` is not 9
        k++){    //    And increase `k` by 1 after every iteration
     s=0;        //   Reset sum `s` to 0
     for(int c:(n*n+"").getBytes())
                 //   Do `n*n` and inner loop (2) over the digits as characters
       s+=c-48;  //    And increase the sum `s` with these digits
                 //   End of inner loop (2) (implicit / single-line body)
     n=n%2<1?    //   If `n` is even:
        n/2+1    //    Change `n` to `n/2+1`
       :         //   Else:
        s;       //    Change `n` to sum `s`
  }              //  End of loop (1)
  return k;      //  Return the result `k`
}                // End of separated method (2)

```
> 1 votes

# Answer
# Pyth, 18 bytes

```
tl.u?%N2sj*NNTh/N2

```

Try it online: Demonstration

### Explanation:

```
tl.u?%N2sj*NNTh/N2
  .u                 apply the following function to the input,
                     until it runs into a fixed point
    ?%N2                if value % 2 == 1:
          *NN               value * value
         j   T              convert to digits
        s                   sum
                        else:
               /N2          value / 2
              h              + 1
 l                   get the length of all visited values
t                     - 1

```
> 1 votes

---
Tags: code-golf, sequence
---