title: Days and months make years

text:
# Question
Title: Days and months make years
Today's date is quite an interesting one. Let's take a look at why. The date `07/12/2017` (in `DD/MM/YYYY` date format) can be split into the year (`2017`) and the rest (`07/12`). You may notice that the digits in the year can be rearranged to match the digits in the rest of the date, which is the basis of this challenge.

## The task

Given an valid integer (e.g. no leading zeros) representing a year, consisting of exactly four digits, output all **unique** possible valid dates that can be made from those digits. You may take the number as a list of digits, or a string representing the input if you want. Each number in the input must be used **exactly once** in each of the final outputs. As leading `0`s aren't used in integers, the input will be in the range `1000 <= input <= 9999`.

A valid date is one in which the date exists on the Gregorian Calendar, such as `17/05/2000`. The only corner case is February 29th, which is only a valid date when the year is a leap year. You can (but don't have to) assume that leap years are years that are divisible by 4.

You have to output a separator between the day and the month (e.g. `/`) and a **different** separator between different dates. You may optionally output the year with each date, but this must be consistent between dates.

Finally, you may choose between the date format order, i.e. you can output as any of `DD/MM/YYYY`, `MM/DD/YYYY` etc. but leading `0`s are required when the input contains at least one `0`.

Essentially, you may output in any obviously understandable format, such as an array of strings, one concatenated string etc.

This is a so shortest code wins!

## Test cases

```
input
outputs

2017
07/12, 12/07, 17/02, 21/07, 27/01, 27/10

2092
22/09, 29/02

2029
22/09

1000
Nothing

8502
25/08, 28/05

```

Reference Implementation

# Answer
> 6 votes
# Japt, ~~31~~ ~~30~~ ~~26~~ ~~24~~ ~~23~~ ~~22~~ 17 bytes

Locale dependent. Outputs a 2D-array of the format `[["MM","DD"],...]`.

```
á â mò fÈÎ-ÐNcX)Î

```

Try it or Try It Online! (to avoid the locale dependency)

## Explanation

If it wasn't for JavaScript's `Date` object wrapping invalid dates, I'd be able to get this down to about ~~20 18~~ 16 bytes. Even when providing its argument as a single string, which the spec says *shouldn't* lead to wrapping, dates up to 31 still do for months that don't have 31 days. However, as the month's can only wrap over by one, we can take advantage of the fact that string arguments use 1-based months to simply filter by subtraction - if the month rolls over then the result of that subtraction will be `0`.

```
á â mò fÈÎ-ÐNcX)Î     :Implicit input of N=[U="YYYY"]
á                     :Permutations of U
  â                   :Deduplicate
    m                 :Map
     ò                :  Partitions of length 2 (=[["MM","DD"],...])
       f              :Filter
        È             :By passing each X through the following function
         Î            :  First element of X
          -           :  Subtract
           Ð          :  Create new Date from
            NcX       :    N concatenated with X (=["YYYY","MM","DD"], which gets coerced to "YYYY-MM-DD", with MM being 1-based)
               )      :  End date creation
                Î     :  0-based month (=NaN for invalid dates, n-NaN=NaN)

```

---

## Original, 22 bytes

Preserving this, 'cause I really liked the setwise union trick.

```
á
â¡ÐNcXòÃfÈÎ-2îUvÃms7

```

Try it (footer formats the output to match the examples in the challenge)
Or Try it online! to somewhat mitigate the locale dependency - TIO's locale doesn't include leading 0s for dates & months, so they're added back in in the footer.

### Explanation

```
á\nâ¡ÐNcXòÃfÈÎ-2îUvÃms7     :Implicit input of N=[U="YYYY"]
á                           :Permutations of U
 \n                         :Reassign to U, leaving the value in N unchanged
   â                        :Setwise union with
    ¡                       :Map each X in U
     Ð                      :  New Date from
      Nc                    :  N concatenated with
        Xò                  :  Partitions of X of length 2 (=["YYYY","MM","DD"], which gets coerced to "YYYY-MM-DD", with MM being 1-based)
          Ã                 :End map
           f                :Filter by
            È               :Passing each through the following function
             Î              :  Get 0-based month (=NaN for invalid date)
              -             :  Subtract (NaN-n=NaN)
               2î           :  First 2 characters of
                 Uv         :  Remove and return first element of U
                   Ã        :End filter
                    m       :Map
                     s7     :  To locale date string (="DD/MM/YYYY")

```

The reason the setwise union doesn't include any elements from the first array is because `v` modifies that array so the filter ends up removing all elements from it.

In the 16 byte version, which assumes a way to avoid dates wrapping over, we don't need to reassign the array of possible dates to U and instead filter by using `Í` to try to subtract the timestamp from 2, which will result in `NaN` if the date is invalid. We can't use the setwise union trick, though, so `â` get tacked on the end to deduplicate the final array.

# Answer
> 4 votes
# 05AB1E, ~~36~~ 35 bytes

```
œÙ2δôʒ`ÐU13‹rD•ü¯B•5°I4Ö*+ºS₂+Xè‹PĀ

```

05AB1E doesn't have any date builtins, so manual calculations it is. Therefore all years divisible by 4 are counted as leap years (which is allowed in the challenge description), since that's shorter than actual leap year calculations.

Output as a list of `[dd,MM]`-pairs.

Try it online or verify all test cases.

**Explanation:**

```
œ                # Get all permutations of the (implicit) input-integer
 Ù               # Uniquify this list
   δ             # For each permutation:
  2 ô            #  Split it into parts of size 2
ʒ                # Filter this list of [dd,MM]-pairs by:
 `               #  Pop and push both values separated to the stack
  Ð              #  Triplicate the top value MM
   U             #  Pop and store one MM in variable `X`
    13‹          #  Check whether MM is smaller than 13
  r              #  Reverse the values on the stack, so the order is MM<13,MM,dd
   D             #  Duplicate the top value dd
    •ü¯B•        #  Push compressed integer 16365656
     5°          #  Push 10⁵: 100000
       I         #  Push the input-year
        4Ö       #  Check if it's divisible by 4 (1 if truthy; 0 if falsey)
          *      #  Multiply that by the 100000 (100000 if it's a 'leap year'; 0 if not)
           +     #  Add it to the 16365656 (16465656 if it's a 'leap year'; 16365656 if not)
            º    #  Mirror it: 1636565665656461 / 1646565665656461
             S   #  Convert it to a list of digits: [1,6,3/4,6,5,6,5,6,6,5,6,5,6,3/4,6,1]
              ₂+ #  Add 26 to each: [27,32,29/30,32,31,32,31,32,32,31,32,31,32,29/30,32,27]
    X            #  Push MM from variable `X`
     è           #  Index it into this list (0-based modulair, hence the leading dummy 27)
    ‹            #  Check if dd is smaller than the indexed value
  P              #  Take the product of all values on the stack: (MM<13)*MM*dd*(dd<...)
   Ā             #  Check that this is NOT 0
                 # (after which the filtered list of [dd,MM]-pairs is output implicitly)

```

See this 05AB1E tip of mine (section *How to compress large integers?*) to understand why `•ü¯B•` is `16365656`.

# Answer
> 3 votes
# , ~~231~~ ~~216~~ ~~189~~ 186 bytes

*Edit: -42 bytes by keeping numbers as numbers (no conversion to text) and using sprintf to fix the leading zeros*

```
function(y){e=unique(gtools::permutations(4,4,y%/%10^(0:3)%%10,F))
m=e[,1]*10+e[,2];n=e[,3]*10+e[,4]
sprintf("%02d/%02d",m,n)[which(m&n&(m<(31-rep(-1:0,l=13)[-8])[n]-(n==2)*(2-!y%%4)))]}

```

Try it online!

This challenge seemed quite innocuous when I read it, but turned-out to be much, much more complicated than I thought to implement! The actual checking for possible day/month combinations is less than one-third of the code!

Finds all unique permutations of the digits of the year, combines them in pairs as numbers ~~text (to keep leading zeros),~~ then finds the indices that are possible ~~after converting back to numbers~~, and `sprintf`s the output to keep the leading zeros.

Calculates days in months as `(31-rep(-1:0,l=13)[-8])` which gives all correct except Feb, then adjusts with `-(month==2)*(2-!y%%4))` to fix Feb for leap-years.

Original commented code (before quite a lot of golfing):

```
possible_dates=
function(y,                     # y = year (number)
 `+`=as.double,                 # `+` = alias to as.double() function, to easily
                                #       convert text to numbers
  a=apply,                      # a = alias to apply() function (runs helper function over all elements of matrix)
  p=paste0){                    # p = alias to paste0 function (joins text together)
  d=a(                          # d (digits) =
   unique(                      # get the unique combinations of...
    gtools::permutations(4,4,   # all permutations of...
     y%/%10^(0:3)%%10,F))       # the digits of the year...
   ,1,function(i)               # and, for each combination...
    p(i[1:2],i[3:4]))           # paste-together the first & second two digits as text
 a(d,2,p,collapse="/")          # now, paste these together with '/' as separator,
  [which(                       # but only output those that satisfy...
   (m=+d[1,])&                  # first element (days) non-zero, and...
   (n=+d[2,])&                  # second element (months) non-zero, and...
   (m<(31-rep(-1:0,l=13)[-8])[n]  # days less than days in the month...
   -(m==2)*(2-!y%%4))           # with correction for leap-years
  )]
}

```

# Answer
> 3 votes
# Ruby, <sup>~~94~~ ~~91~~ ~~90~~</sup> 88 bytes

*-3 bytes thanks to @Shaggy and another -2 bytes thanks to @vrintle*

```
->y{[]|y.permutation.map{|d|("#{Time.gm y*'',(d*'')[/../],$'}"rescue$/)[/\S+-#$'/]}-[p]}

```

Try it online!

Takes input as an array of digits and returns an array of date strings in `yyyy-mm-dd` format. Leap years are handled correctly, i.e. it is *not* assumed that all years that are divisible by 4 are leap years. A gotcha with the `Time` library is that it sets an upper limit of 31 days for all months, silently wrapping to the next real calendar date, so a sanity check is required. Invalid months are automatically rejected.

```
->y{
  []|                                   # combine with empty array
  y.permutation                         # form all permutations of the year digits
   .map{|d|                             # loop over permutations
     ("#{Time.gm y*'',(d*'')[/../],$'}" # (attempt to) create a time string using the first two digits of the permutation as the month and the last two digits as the day
       rescue$/)                        # if the time is invalid, rescue the exception and return a dummy string ($/) instead
     [/\S+-#$'/]                        # check that the day is the same as expected (to prevent date wrapping) and extract the full date if so
   }
  -[p]                                  # remove nil elements
}

```

# Answer
> 2 votes
# Python 3.8, ~~149~~ 140 bytes

Uses the simplified definition of leap years.

```
lambda y:{i+o+'/'+z+u for z,u,i,o in permutations(str(y))if((m:=int(z+u))==2)*~(y%4>0)+(m//8^m%2)+31>int(i+o)>0<m<13}
from itertools import*

```

Try it online!

# Answer
> 1 votes
## Python 3, ~~186~~ 197 bytes

```
import itertools;import datetime;y=input();s=set()
for p in itertools.permutations(list(y)):
 try:f=datetime.date(int(y),int(p[2]+p[3]),int(p[0]+p[1]));s.add(f)
 except:pass
for d in s:print(d)

```

# Answer
> 1 votes
# k4, 55 bytes

```
{?,/(@[.:;;()]x,"."/:0 0 2_)'(,"")(,/{(1_x),*x}\',')/x}

```

Not the most elegant, but it outputs a list of valid dates (accounting for e.g. leap years). Takes a string as input, e.g. `"2017"`.

* `(,"")(,/{(1_x),*x}\',')/x` builds a list of the permutations of the input
* `x,"."/:0 0 2_` takes each permutation, prepends the input year, and inserts `"."`s to format it as a date. E.g., for an input of `"0127"`, the output is `"2017.01.27"`.
* `@[.:;;()]` is error trap; it attempts to eval the generated date string, returning an empty list if the value is an invalid date.
* `?,/` returns the distinct valid dates

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


title: When is the closest Conway's Doomsday?

text:
# Question
Title: When is the closest Conway's Doomsday?
A quote from MO.SE answer:

> Although it is well known that Conway was able to quickly calculate the day of the week of any given date, it is less well known that one part of the algorithm is easy to remember and useful in practice: In any given year, the following dates all fall on the same day of the week: **4/4, 6/6, 8/8, 10/10, 12/12, 5/9, 9/5, 7/11, 11/7, and the last day of February**. For example, in 2020, all these dates fall on a Saturday. Conway, in his characteristically colorful way, would say that the **Doomsday** of 2020 is Saturday. Knowing this fact allows you to calculate fairly quickly in your head, with no special training, the day of the week for any date in 2020.

Well, it sounds easy, but then we need to check which doomsday is the closest from the given date in order to quickly calculate the day of week. Now *that* sounds hard.

Practically, we'd just compare a given date with the Doomsday in the same month (or adjacent month in case of January and March).

## Task

Given a date consisting of full year, month, and day, output the closest Conway's Doomsday (i.e. one of **4/4, 6/6, 8/8, 10/10, 12/12, 5/9, 9/5, 7/11, 11/7, and the last day of February**) from the given date.

The closest Doomsday can be in the same month, a different month, or even a different year. If the given date has two nearest Doomsdays, output any one or both of them. Also note that the last day of February can be either 28th or 29th (depending on leap-year-ness).

You can take input and produce output in any suitable format, e.g. three integers, a formatted string, or even a built-in Date object (if your language has one). You can assume the given date is valid, and the **input year is between 1901 and 2099 inclusive**. Gregorian calendar is assumed in this challenge.

## Test cases

```
YYYY-MM-DD => YYYY-MM-DD, ...
-------------------------------
2020-05-18 => 2020-05-09
2020-05-30 => 2020-06-06
2020-10-31 => 2020-11-07
2020-10-24 => 2020-10-10 or 2020-11-07
2020-01-20 => 2019-12-12
2020-01-21 => 2020-02-29
2019-01-20 => 2018-12-12 or 2019-02-28

```

Reference implementation in Python.

# Answer
> 4 votes
# Charcoal, ~~138~~ ~~110~~ 98 bytes

```
≔§⪪”)¶⊟eΦＯ∨ü&-T[¿Ｑ№i⧴⊕%⁰q”⁴ＬΦ⪪”)¶ »Ｒ≦ＰH↘{⎚″4χχβ´ΣP”⁴›ι✂θ⁴χ¹η¿⁼Ｉη¹²⁺⊖…θ⁴1212«…θ⁴¿⁻Ση³η«022§9888Ｉ…θ⁴

```

Try it online! Link is to verbose version of code. Edit: Saved 28 bytes by switching I/O to compact ISO format (yyyymmdd). Saved 12 bytes when the supported year range was restricted to 1901 to 2099. Explanation:

```
≔§⪪”)¶⊟eΦＯ∨ü&-T[¿Ｑ№i⧴⊕%⁰q”⁴ＬΦ⪪”)¶ »Ｒ≦ＰH↘{⎚″4χχβ´ΣP”⁴›ι✂θ⁴χ¹η

```

Take the dates (in mmdd format) `0120`, `0317`, `0421`, `0523`, `0623`, `0725`, `0822`, `0922`, `1024`, `1124`. These represent the cutoff points above which the next Doomsday is nearer. (In some cases the Doomsday is equidistant but in particular for `0120` that is not true on leap years.) Work out which cutoff point applies by counting the number of dates that fall before the input date. Then look up the relevant Doomsday date from the list (in mmdd format) `1212`, `1107`, `1010`, `0905`, `0808`, `0711`, `0606`, `0509`, `0404`, `0300`, `0012`.

If I had access to a date library I could then ask it to fix up my date, but unfortunately I have to do that manually:

```
¿⁼Ｉη¹²

```

Is this the `0012` date, meaning the 12th of month 0, i.e. last December?

```
⁺⊖…θ⁴1212«

```

If so then output the previous year and a month and day of 12.

```
…θ⁴

```

Otherwise the year is at least correct...

```
¿⁻Ση³

```

Is this the `0300` date, meaning the 0th of March, i.e. the last day of February?

```
η«

```

If not then this is the date we seek.

```
022

```

Output February the 2?th.

```
§9888Ｉ…θ⁴

```

Output `9` if the year is a multiple of 4, otherwise `8`.

# Answer
> 3 votes
# JavaScript (ES7),  ~~125 ... 114~~  113 bytes

Takes and returns a Date object.

```
D=>[25,-15,...'108088080'].map(b=d=>(v=(q=new Date(D.getFullYear(x+=21-d),x>>4,x&15))-D)*v>b||(b=v*v,o=q),x=0)&&o

```

Try it online!

### How?

The array `[25,-15,...'108088080']` encodes the following pairs \\$(m,d)\\$ where \\$m\\$ is a 0-indexed month and \\$d\\$ is a day:

```
[-1,12], [2,0], [3,4], [4,9], [5,6], [6,11], [7,8], [8,5], [9,10], [10,7], [11,12]

```

Special cases:

* `[-1,12]` is the 12th of December of the previous year
* `[2,0]` (literally "March 0") is the last day of February

It is decoded as follows:

```
[25, -15, ...'108088080'] // array of delta values
.map(d =>                 // for each value d in this list:
  [                       //   build the pair (month, day):
    (x += 21 - d) >> 4,   //     add 21 - d to x; the month is floor(x / 16)
    x & 15                //     the day is (x + 16) mod 16
  ],                      //   end of pair
  x = 0                   //   start with x = 0
)                         // end of map()

```

Try it online!

For each pair \\$(m,d)\\$ we compute the square of the difference (in milliseconds) between the input date \\$D\\$ and a new date \\$q\\$ generated with this month and this day.

```
(v = (q = new Date(D.getFullYear(), m, d)) - D) * v

```

We eventually return the date that leads to the smallest squared difference.

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

```
aMinimalBy[DateObject@{a[[1,1]],##}&@@@36^^3cx83c24e4aw06er~IntegerDigits~13~Partition~2,Abs[#-a]&]

```

Try it online! Pure function. Takes a `DateObject` as input and returns a list of `DateObject`s as output. The Unicode character is U+F4A1 (`\[Function]`). I'd use `Nearest` here, but its default `DistanceFunction` refuses to compare `Quantity` values. Note that the function emits a few warnings on TIO due to its sandboxing.

# Answer
> 3 votes
# APL (Dyalog Unicode), ~~115 99~~ 91 bytes

```
{u/⍨(⊢=⌊/)|(1∆DT⊂⍵)-1∘∆DT¨⊂¨u←(,y∘.,(2/¨2+2×⍳5),(⊢,⌽¨)0 2+⊂5 9),↓y,↑2∘,¨28+0=4|y←(2-⍳3)+⊃⍵}

```

Try it online!

Takes a date array `yyyy mm dd`, and returns all the closest doomsdays. If that is not allowed, then +1 byte.

-16 bytes from Bubbler(simplifying leap year check)

-8 bytes from Bubbler(compressing doomsdays)

`⎕DT` is polyfilled as `∆DT` here(Courtesy of Adám) since tio's version doesn't allow it's usage.

## Explanation

`(2-⍳3)` array (-1,0,1)

`y←(2-⍳3)+⊃⍵` add that to the year and store it as y.

`0=4|` check if each of those is a leap year(This works due to the year range.)

`28+` add 28 to those booleans to get the correct february dates

`↓y,↑2∘,¨` add the respective years, and months(2) to them to get the appropriate dates

`(...),` concatenate with:

`(⊢,⌽¨)0 2` generate array `(5 9)(7 11)(9 5)(11 7)`

`(2/¨2+2×⍳5)` and the numbers 4 6 8 10 12 repeated twice

`,y∘.,` join with the years and flatten to a list to get all the dates

`u←` save all the dates together as u

`1∘∆DT¨⊂¨` get each of their date numbers

`(1∆DT⊂⍵)` and subtract from the input's date number.

`|` convert to their absolute values:

`(⊢=⌊/)` tacit fn: array = minimum? (generates bitmask)

`u/⍨` filter the dates by that (get the dates with minimum distance)

# Answer
> 2 votes
# Red, ~~234~~ ~~182~~ 176 bytes

```
func[n][y: n/2 t: to-date[y 3]second sort/skip
collect[foreach[d m]reduce[4 4 6 6 8 8 10 10 12 12 5 9 9 5 7 11 11 7 t/4 2 -19 1][a:
to-date[d m y]keep absolute a - n keep a]]2]

```

Try it online!

# Answer
> 2 votes
# 05AB1E, 84 bytes

```
4Ö¹тÖ_²3@PU•ΘÏF•5°X*+ºS₂+©²<£O+•23õ₄ƶ₃-¹å•60в.¥X+¦19(šs.xDVdi®ηODY‹O©£θYα®>¹)ë12D¹<)

```

Can definitely be golfed some more.. 05AB1E doesn't have any date builtins, so everything is done manually.

Input as three loose inputs in the order `year,month,day`, output as a triplet in the format `[day,month,year]`.

Try it online.

**Explanation:**

Determine if the input is a leap year, and if the input-month is NOT January nor February:

```
4Ö            # Check if the (implicit) first input-year is divisible by 4
¹тÖ_          # Check that the first input-year is NOT divisible by 100
²3@           # Check that the second input-month is >= 3
    P         # Check if all three are truthy by taking the product of the stack
              # (1 if truthy; 0 if falsey)
     U        # Pop and store this in variable `X`

```

Convert the input to an integer \\$n\\$, being the (1-based) \\$n^{th}\\$ day of the year:

```
•ΘÏF•         # Push compressed integer 5254545
5°            # Push 10 to the power 5: 100000
  X*          # Multiply it by `X`
    +         # Add it to the integer (5354545 if `X` is truthy; 5254545 if falsey)
º             # Mirror it: 5354545454535 or 5254545454525
 S            # Convert it to a list of digits
  ₂+          # Add 26 to each: [31,28 or 29,31,30,31,30,31,31,30,31,30,31,28 or 29,31]
    ©         # Store this list in variable `®` (without popping)
²<            # Push the second input-month, and decrease it by 1
  £           # Leave that many leading values of the list
   O          # Sum them
    +         # And add them to the (implicit) third input-day

```

Create a list of values \\$k\\$, representing the \\$k^{th}\\$ day of the year for the dates `[prevYear-12-12, year-02-28 or 29, year-04-04, year-05-09, year-06-06, year-07-11, year-08-08, year-09-05, year-10-10, year-11-07, year-12-12]`:

```
•23õ₄ƶ₃-¹å•   # Push compressed integer 36033721893183342948
 60в          # Convert it to base-60 as list: [59,35,35,28,35,28,28,35,28,35,48]
    .¥        # Undelta it with leading 0: [0,59,94,129,157,192,220,248,283,311,346,394]
      X+      # Add `X` to each
        ¦     # Remove the leading 0 (or 1)
         19(š # And prepend -19 instead

```

Get \\$k\\$ closest to \\$n\\$:

```
s             # Swap so `n` is at the top of the stack
 .x           # And get the value of the list closest to it
   DV         # And store a copy in variable `Y`

```

And convert that result back into a date to output:

```
di            # If the result is non-negative (>=0):
  ®           #  Push the list from variable `®`
   η          #  Get its prefixes
    O         #  And sum each prefix: [31,60,91,121,152,182,213,244,274,305,335,366,395,426]
  D           #  Duplicate it
   Y‹         #  Check for each whether it's smaller than `Y` (1 if truthy; 0 if falsey)
     O        #  Sum those checks
      ©       #  Store it in variable `®` (without popping)
   £          #  Leave that many leading values from the list
    θ         #  Then only leave its last value
     Yα       #  And take its absolute difference with `Y`
       ®>     #  Push `®` + 1
         ¹    #  Push the first input-year
          )   #  And wrap all three values on the stack into a list
 ë            # Else:
  12D         #  Push two 12s
     ¹<       #  Push the first input-year - 1
       )      #  And wrap all three values on the stack into a list
              # (after which it is output implicitly as result)

```

See this 05AB1E tip of mine (sections *How to compress large integers?* and *How to compress integer lists?*) to understand why `•ΘÏF•` is `5254545`; `•23õ₄ƶ₃-¹å•` is `36033721893183342948`; and `•23õ₄ƶ₃-¹å•60в` is `[59,35,35,28,35,28,28,35,28,35,48]`.

# Answer
> 1 votes
# Bash \+ Core utilities, ~~173~~ 169 bytes

```
y=${1%%-*}
for E in {4..12} {3/1/{$y,$[y+1]}-,1/2/$y-2}1day
{
((E))&&E+=/$[E%2?12^E:E]/$y
a=date\ -d;k=$[(`$a$1 +%s`-`$a$E +%s`)**2];((k<n|!n))&&{ n=$k;D=$E;}
}
$a$D +%F

```

Try the test cases online!

This is a full program. Input is passed as an argument in yyyy-mm-dd format. Output is on stdout in the same format.

This uses several tricks:

* For each month `E` from April to December, the Doomsday day in that month is computed as `E` for even months and `E xor 12` for odd months.
* The last day of February is computed as 1 day before March 1. (This applies to both the current year and the next year.)
* December 12 of the previous year is computed as 21 days before January 2 of the current year.
* The last two computations (ending with `-1day` and `-21day`) are combined using bash's brace expansion).
* The `date` command with first option `-d` is saved in a variable for use like a macro.
* Some spurious error messages are written to stderr.

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


title: Towering Cistercian representation

text:
# Question
Title: Towering Cistercian representation
SE Sandbox Link, Codidact Sandbox Link

Inspired by this video.

Given a positive integer, draw its Cistercian representation as ascii art.

## The Challenge

Cistercian numerals are a decimal-based number representation system which use simple line based drawings to represent 4-digit numerals. Their structure is as follows:

```
     Tens|Units
         |
Thousands|Hundreds

```

The digits are represented as follows (in the units place):

```
1   ⌷ 2   ⌷ 3   ⌷ 4   ⌷ 5   ⌷ 6    ⌷ 7    ⌷ 8    ⌷ 9    ⌷ 0
___ ⌷     ⌷     ⌷     ⌷ ___ ⌷    . ⌷ ___. ⌷    . ⌷ ___. ⌷
    ⌷     ⌷ \   ⌷   / ⌷   / ⌷    | ⌷    | ⌷    | ⌷    | ⌷
    ⌷     ⌷  \  ⌷  /  ⌷  /  ⌷    | ⌷    | ⌷    | ⌷    | ⌷
    ⌷ ___ ⌷   \ ⌷ /   ⌷ /   ⌷    ' ⌷    ' ⌷ ___' ⌷ ___' ⌷

```

(all of these are 4 rows in height.)

As you can see, there are some repeating patterns within the symbols:

```
5 → 4 + 1
7 → 6 + 1
8 → 6 + 2
9 → 6 + 1 + 2

```

In order to represent a general Cistercian number, you will have to place the digits in the correct place for their value.

They should be mirrored horizontally if they are on the left.

They should be mirrored vertically if they are on the bottom i.e. the lines should be reversed, `\` and `/` should be swapped, and `.` and `'` should be swapped. Here's how they should look.

The fun part is when you stack a Cistercian representation on top of another one to accommodate more digits e.g.:

```
  T|U
   |
 Th|H
   |
Hth|Tth
   |
 TM|M

```

like a tower of sorts.

You will need to stack as many 4 part towers as the number requires, and you will need to prepend 0's to the input if it's length is not a multiple of 4.

Hence, given an input number, say, 12345, you should get the following:

`00012345 → 5432,1000`

which turns into:

```
4|5
 |
2|3
 |
0|1
 |
0|0

```

which becomes:

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

```

Note that this is created by making two towers for the 4 digit numbers `2345` and `0001`, stacking them, and adding a link of 4 `|` characters between them.

# Scoring

This is code-golf. Shortest answer in each language wins.

# Answer
> 9 votes
# JavaScript (Node.js), 265 bytes

```
f=n=>n?`01238888765${n<1e4?4:48888}`.replace(e=/\d/g,y=>`4567|3210
`.replace(e,x=>"_ \\/.'|"[q=y/2&2|x>3,y&8?1:(k='40321123'[j=~~('0x'+(1e6+'1023405671567899AB99A899CB99C')[y%4+~-(n/10**q%10)*4])]^x%4?2045>>j&1:'0122233346545'[j])^0xCC6600>>k*4+q&1]))+f(n/1e4|0):''

```

Try it online!

### Encoding

Each digit pattern is a 4x4 matrix consisting of 7 distinct characters. Each character is encoded as a single decimal digit from `0` to `6`:

```
0: "_"
1: " "
2: "\"
3: "/"
4: "."
5: "'"
6: "|"

```

All matrices are built with 13 distinct rows, encoded as a single hexadecimal digit from `0` to `C`:

```
0: 1111 for "    "
1: 0001 for "___ "
2: 2111 for "\   "
3: 1211 for " \  "
4: 1121 for "  \ "
5: 1131 for "  / "
6: 1311 for " /  "
7: 3111 for "/   "
8: 1114 for "   ."
9: 1116 for "   |"
A: 1115 for "   '"
B: 0004 for "___."
C: 0005 for "___'"

```

So, each matrix is fully described by a sequence of 4 hexadecimal digits. For instance, the matrix for `7` is encoded as `B99A`:

```
B99A -> 0004 -> "___."
        1116    "   |"
        1116    "   |"
        1115    "   '"

```

The leading sequence is `0000` and is omitted. The other sequences are stored as:

```
1e6 + '1023405671567899AB99A899CB99C'

```

which expands to:

```
0      1    2    3    4    5    6    7    8    9
(0000) 1000 0001 0234 0567 1567 899A B99A 899C B99C

```

Each matrix row is made of a 'background' character appearing 3 times and a 'foreground' character appearing only once (or not at all). So the rows can be encoded as:

* the position of the 'foreground' character (0 for rightmost to 3 for leftmost, or 4 if none)
* the 'background' character (which is always either `0` for `"_"` or `1` for `" "`)
* the 'foreground' character

This is summarized in the following table:

```
 ID | string | digits | FG position | BG char. | FG char.
----+--------+--------+-------------+----------+----------
  0 | "    " |  1111  |      4      |    1     |    0
  1 | "___ " |  0001  |      0      |    0     |    1
  2 | "\   " |  2111  |      3      |    1     |    2
  3 | " \  " |  1211  |      2      |    1     |    2
  4 | "  \ " |  1121  |      1      |    1     |    2
  5 | "  / " |  1131  |      1      |    1     |    3
  6 | " /  " |  1311  |      2      |    1     |    3
  7 | "/   " |  3111  |      3      |    1     |    3
  8 | "   ." |  1114  |      0      |    1     |    4
  9 | "   |" |  1116  |      0      |    1     |    6
  A | "   '" |  1115  |      0      |    1     |    5
  B | "___." |  0004  |      0      |    0     |    4
  C | "___'" |  0005  |      0      |    0     |    5
----+--------+--------+-------------+----------+----------
                             |           |          |
                             |           |          +--> stored as "0122233346545"
                             |           +-------------> stored as the bit mask 2045
                             +-------------------------> stored as "40321123"

```

# Answer
> 6 votes
# Perl 5, 573 bytes

With some newlines and indentation added:

```
sub f{
  local$_=pop;
  s//0/ while y///c%4;
  $l="    |\n"x3;
  /.{5}/?join$l,reverse map f($_),/.{4}/g:do{
    @c{0..9}=map{join'',map{sprintf"%-4s\n",$_}(split'n')[0..3]}split$/,q(1
___
nnn___
n\n \n2\
n2/n /n/
___n2/n /n/
2.n2|n2|n2'
___.n3|n3|n3'
3.n3|n3|n___'
___.n3|n3|n___')=~s/\d/$"x$&/ger;
    $c{$_.'00'}=join('',map"$_\n",reverse$c{$_}=~/.+/g)=~y|.'|'.|r=~y|/\\|\\/|r for 0..9;
    $c{$_.0}=$c{$_}=~s,.+,reverse"|$&",ger=~y|/\\|\\/|r for map{$_,$_.'00'}0..9;
    $_=[/.+/g]for values%c;
    /(.)(.)(.)(.)/;
    join'',
      (map$c{$3.0}[$_].$c{$4}[$_].$/,0..3),
      $l,
      map$c{$1.'000'}[$_].$c{$2.'00'}[$_].$/,0..3
  }
}

```

Try it online!

# Answer
> 2 votes
# Charcoal, 125 bytes

```
≔⪪⮌Ｓ⁴θＦＬθ«↓∧ι⁴Ｆ⁴«→Ｐ§⪪”~∨VKＴ✂≦M›ζΦNＦ›ιO:υ⊘[⁸À1“ir⊞Py✳⪫℅⁰ψ"´dＤ?5¬→⁼σm‹1“"ξωＴ\⁵⁻Hïg”⸿Σ§◨§θι⁴κ←‖Ｔ¿﹪κ²«↓¹¹‖Ｔ↓»»↓¹²»ＵＭＫＡ⎇№βι§.'›ιdι

```

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

```
≔⪪⮌Ｓ⁴θ

```

Split the reversed input into substrings of length 4.

```
ＦＬθ«

```

Loop over each substring.

```
↓∧ι⁴

```

Except for the first substring, separate each quad of digits with a vertical line of length 4.

```
Ｆ⁴«

```

Loop over each digit in the quad.

```
→Ｐ§⪪”~∨VKＴ✂≦M›ζΦNＦ›ιO:υ⊘[⁸À1“ir⊞Py✳⪫℅⁰ψ"´dＤ?5¬→⁼σm‹1“"ξωＴ\⁵⁻Hïg”⸿Σ§◨§θι⁴κ←

```

Extract the relevant digit from a compressed string of all digits and print it without moving the cursor. (I tried printing the digits by parts but this was at least 16 bytes longer.) Note that at this point I print `b` instead of `.` and `p` instead of `'` as Charcoal knows how to reflect `b`, `d`, `p` and `q`.

```
‖Ｔ

```

Reflect the canvas horizontally, transforming the characters appropriately. There are four reflections in total, so that the units end up with their original orientation, but the tens end up horizontally reflected.

```
¿﹪κ²«

```

On alternate passes, ...

```
↓¹¹

```

... move down 11 lines (actually drawing is golfier, but moving would work), ...

```
‖Ｔ↓

```

... and reflect the canvas vertically. This happens twice, so the units and tens end up with their original reflection, but the hundreds and thousands are vertically reflected (and the thousands also get an overall horizontal reflection).

```
»»↓¹²

```

Print the vertical line down the middle of the four digits.

```
»ＵＭＫＡ⎇№βι§.'›ιdι

```

Translate the `b` (and its horizontal reflection `d`) to `.` and the `p` (and its horizontal reflection `q`) to `'`. `b` and `p` (and `d` and `q`) are also vertical reflections of each other, but we want that, otherwise the `.`s and `'`s would be exchanged by the vertical reflection.

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


title: Recamán's duplicates

text:
# Question
Title: Recamán's duplicates
Recamán's Sequence is defined as follows:

\\$a\_n=\begin{cases}0\quad\quad\quad\quad\text{if n = 0}\\a\_{n-1}-n\quad\text{if }a\_{n-1}-n\>0\text{ and is not already in the sequence,}\\a\_{n-1}+n\quad\text{otherwise}\end{cases}\\$

or in pseudo-code:

```
a(0) = 0,
if (a(n - 1) - n) > 0 and it is not
   already included in the sequence,
     a(n) = a(n - 1) - n
else
     a(n) = a(n - 1) + n.

```

The first numbers are (OEIS A005132):

```
0, 1, 3, 6, 2, 7, 13, 20, 12, 21, 11, 22, 10, 23, 9, 24, 8, 25, 43, 62, 42, 63, 41, 18, 42

```

If you study this sequence, you'll notice that there are duplicates, for instance `a(20) = a(24) = 42` (0-indexed). We'll call a number a duplicate if there is at least one identical number in front of it in the sequence.

---

### Challenge:

Take an integer input **k**, and output either the first **k** duplicate numbers in the order they are found as duplicates in Recamán's Sequence, or only the **k**'th number.

This first duplicated numbers are:

```
42, 43, 78, 79, 153, 154, 155, 156, 157, 152, 265, 261, 262, 135, 136, 269, 453, 454, 257, 258, 259, 260, 261, 262

```

A few things to note:

* **a(n)** does not count as a duplicate if there are no identical numbers in **a(0) ... a(n-1)**, even if **a(n+m)==a(n)**.
* 42 will be before 43, since its duplicate occurs before 43's duplicate
* The sequence is not sorted
* There are duplicate elements in this sequence too. For instance the 12th and the 23rd numbers are both **262** (0-indexed).

---

### Test cases (0-indexed)

```
k      Output
    0      42
    9     152
   12     262
   23     262
  944    5197
  945   10023
10000   62114

```

This is , so the shortest code in each language wins!

**Explanations are encouraged!**

# Answer
# Wolfram Language (Mathematica), ~~88~~ ~~85~~ 76 bytes

```
(For[i=k=j=p=0,k<#,i~FreeQ~p||k++,i=i|p;p+=If[p>++j&&FreeQ[i,p-j],-j,j]];p)&

```

Try it online!

1-indexed.

### Explanation

```
For[

```

`For` loop.

```
i=k=j=p=0

```

Start with `i` (\\$=\\{a\_1, a\_2, \ldots\\}\\$), `k` (number of duplicates found), `j` (\\$=n\\$), `p`(\\$=a\_{n-1}\\$) equal to 0.

```
k<#

```

Repeat while `k` is less than the input.

```
i=i|p

```

Append `p` to `i` using the head `Alternatives` (a golfier version of `List` in this case).

```
p+=If[p>++j&&FreeQ[i,p-j],-j,j]

```

Increment `j`. If `p` is greater than `j` (i.e. \\$a\_{n-1} \> n\\$) and `p-j` is not in `i` (i.e. \\$a\_{n-1} - n\\$ is new), then increment `p` by `-j`. Otherwise, increment `p` by `j`.

```
i~FreeQ~p||k++

```

Each iteration, increment `k` if `p` is not in `i` (the `||` (= `or`) short-circuits otherwise).

```
... ;p

```

Return `p`.
> 5 votes

# Answer
# Python 2, 91 bytes

```
k=input();n=0;l=n,
while k:n+=1;x=l[-1]-n;u=x+2*n*(x<1or x in l);k-=u in l;l+=u,
print l[n]

```

Try it online!

1-indexed.
> 4 votes

# Answer
# Python 2, 78 bytes

```
n=input()
l=[];d=x=0
while n:d-=1;l+=x,d;x+=[d,-d][x+d in l];n-=x in l
print x

```

Try it online!
> 4 votes

# Answer
# APL (Dyalog Unicode), ~~56~~ ~~54~~ ~~49~~ 48 bytes (SBCS)

*Saved ~~2~~ 7 bytes thanks to @ovs!*

*Saved 1 byte thanks to @Adám*

```
0∘{×⍵:r,⍣d⊢(r,⍺)∇⍵-d←⍺∊⍨r←(⊃((≤∨⍺∊⍨-)⌷-,+)≢)⍺⋄⍬}

```

Try it online!

Can be `f k`. Recursively builds up the first k duplicates.

⍺ holds Recamán's sequence (in reverse), and is set to 0 if no argument is given (at the start). If k (⍵) is 0, it returns an empty array (⍬). Otherwise, it computes the next term `r`. If `r` is present in ⍺, it calls itself with `r,⍺` as the left argument and `⍵-1` as the right argument, and prepends `r` to the result of that. If not, it just returns `(r,⍺) f ⍵`, hoping for the next iteration to find a duplicate.

`⎕IO←0` has to be used before using this, since it relies on 0-indexing.

0∘          ⍝ Default argument to start off the sequence
{×⍵:       ⍝ If k is greater than 1:
    r←(⊃((≤∨⍺∊⍨-)⌷-,+)≢)⍺
                       ≢     ⍝ Current n is the size of ⍺.
       ⊃                     ⍝ First element of ⍺ (a_{n-1})
                 ⌷           ⍝ Index into
                   -,+       ⍝ a_{n-1} - n, a_{n-1} + n using
         (≤∨⍺∊⍨-)           ⍝ another train to return 1 or 0
          ≤                  ⍝ If a_{n-1} is not greater than n
           ∨                 ⍝ or
               -             ⍝ a_{n-1} - n
            ⍺∊⍨             ⍝ is already in a,
                            ⍝ use a+n, otherwise a-n
    d←⍺∊⍨r                        ⍝ Whether or not r (a_n) is a duplicate

  (r,⍺)∇⍵-d
  (r,⍺)                           ⍝ Add r to ⍺, because it's part of Recaman's sequence
        ⍵-d                       ⍝ Decrement k if r is a duplicate
       ∇                          ⍝ Call itself, find the next duplicates

  r(,⍣d)(r,⍺)∇⍵-d
     ⍣d                           ⍝ If d is 0, just return (r,⍺)∇⍵-d
  r ,                             ⍝ Otherwise, add r to the list of duplicates (which is returned from (r,⍺)∇⍵-d

⋄⍬        ⍝ If k is 0, return an empty array
}
```
</code></pre>
> 4 votes

# Answer
# 05AB1E, 25 bytes

Outputs the `nth` item `1-indexed`

```
¾ˆµ¯D¤N-DŠD0›*åN·*+©å½®Dˆ

```

Try it online!
> 3 votes

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

Returns the **N-th** term, 0-indexed.

```
i=>(g=x=>!g[x+=x>n&!g[x-n]?-n:n]||i--?g(g[n++,x]=x):x)(n=0)

```

Try it online!

### How?

We use **g()** as our main recursive function *and* as an object to keep track of the duplicates.

```
i => (                    // given i
  g = x =>                // g = recursive function and generic object
    !g[x +=               // update x:
      x > n & !g[x - n] ? //   if x is greater than n and x - n was not visited so far:
        -n                //     subtract n from x
      :                   //   else:
        n                 //     add n to x
    ]                     // if x is not a duplicate
    || i-- ?              // or x is a duplicate but not the one we're looking for:
      g(g[n++, x] = x)    //   increment n, mark x as visited and do a recursive call
    :                     // else:
      x                   //   stop recursion and return x
)(n = 0)                  // initial call to g() with n = x = 0

```
> 3 votes

# Answer
# Pyth, ~~34~~ 33 bytes

```
J]0@LJ.f}K+=G-eJZ*yZ|}GJ<G0~+JKQ1

```

Try it online!

Outputs the `n` first duplicates.

<sub>*\*waits for Jelly or one of the new stack languages to enter\**</sub>
> 2 votes

# Answer
# Rust, 160 bytes

```
|k|{let(mut a,mut r,mut n,mut i,mut v)=(vec!(0),0,1usize,0,0);while i<k{v=if v>n&&!a.contains(&(v-n)){v-n}else{v+n};if a.contains(&v){r=v;i+=1}a.push(v);n+=1}r}

```

Try it online!

Ungolfed:

```
|k| {
  let mut a=vec!(0);
  let mut r=0;
  let mut n=1usize;
  let mut i=0;
  let mut v=r;
  while i < k {
    v = if v > n && !a.contains(&(v-n)) {
      v - n
    } else {
      v + n
    };
    if a.contains(&v) {
      r = v;
      i += 1
    }
    a.push(v);
    n += 1
  }
  r
}

```
> 0 votes

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


# Question
Title: Count the unique fractions with only integers
Count the number of unique fractions with numerators and denominators from 1 to 100, and print the counted number. Example: 2/3 = 4/6 = ...

Rules:

You must actually count in some way. Only integers are allowed, no floating point numbers or fraction types.

Integers count as fractions. So 1/1, 2/1, etc is valid.

# Answer
> 4 votes
# J - 21 17 char

```
+/1=,+./~1+i.100

```

Explained:

* `1+i.100` \- The integers from 1 to 100.
* `+./~` \- Table of GCDs.
* `1=,` \- Run into a list, and then check for equality to 1.
* `+/` \- Add together the results (true is 1, false is 0).

Usage:

```
   +/1=,+./~1+i.100
6087

```

21 char version that actually constructs all the pairs of numbers:

```
#~.,/(,%+.)&>:/~i.100

```

`&>:` increments all the integers and also sets up another golfy thing, while `~.` takes all the unique entries in the list of pairs we construct, and then `#` gives the length of that.

# Answer
> 3 votes
# Ruby, 57 (67 without `Rational`) (-3 if run in IRB)

```
p((a=[*1..100]).product(a).map{|x|Rational *x}.uniq.size)

```

Output:

```
6087

```

Can be 3 less characters if run in IRB, because you can remove the `p(` and `)`.

Uses `product` for the numerator and denominator getting process, and then uses `Rational` for converting them to fractions. If you remove the `.size` at the end, it prints all of the fractions instead of how many there are.

It seems like it might take a long time to run, but it's actually almost instantaneous.

Here's an example IRB session to explain how the code works a bit better:

```
irb(main):027:0> (a=[*1..5]).product(a)
=> [[1, 1], [1, 2], [1, 3], [1, 4], [1, 5], [2, 1], [2, 2], [2, 3], [2, 4], [2, 5], [3, 1], [3, 2], [3, 3], [3, 4], [3, 5], [4, 1], [4, 2], [4, 3], [4, 4], [4, 5], [5, 1], [5, 2], [5, 3], [5, 4], [5, 5]]
irb(main):028:0> Rational 1, 2
=> (1/2)
irb(main):029:0> Rational 2, 4
=> (1/2)

```

`Rational *x` uses the "splat" operator to call the `Rational` function with arguments given in the array `x`. This "splat" is also used in `[*1..100]`.

Here's an alternative that doesn't use `Rational`, weighing in at 66 characters:

```
p((a=[*1..100]).product(a).map{|x,y|z=x.gcd y;[x/z,y/z]}.uniq.size)

```

The fraction simplification method is replaced with this:

```
z=x.gcd y;[x/z,y/z]

```

which divides the numberator and the denominator by their GCD (greatest common denominator), and then sticks them back in an array so that `uniq` can work.

# Answer
> 3 votes
# Bash + GNU tools, 47

```
$ echo 10^9\*{1..100}/{1..100}\;|bc|sort -u|wc -l
6087
$

```

Looks like a similar method to @Doorknob's answer.

# Answer
> 2 votes
## Mathematica - 24

This is just a sequence A018805. `EulerPhi[n]` is the number of coprime to `n` integers `m` that are below `n` (gcd n m == 1)

```
2 Tr@EulerPhi@Range@100 - 1

```

## J - 15

```
<:+:+/5&p:i.101

```

# Answer
> 2 votes
# JavaScript, 64 characters

```
for(n=101,o=0,c={};--n;)for(d=101;--d;)!c[n/d]&&(c[n/d]=++o);o

```

Put into the JS console, returns 6087.

# Answer
> 2 votes
# Haskell, 32 bytes

```
sum[1|1<-gcd<$>r<*>r]
r=[1..100]

```

Try it online!

Tries to follow the spirit of actually computing the result by having a "100" that can be replaced with any number.

# Answer
> 2 votes
# APL (Dyalog Extended), 12 bytes

```
≢⍸1=∘.∨⍨⍳100

```

Try it online!

Original:

```
(+/1=∘,⍳∘.∨⍳)100

```

Explanation:

```
  (+/1=∘, ⍳∘.∨⍳ )100
⍝ ^~~~~~v ^~~~v ^~~~v
⍝       |     |     100 x 100
⍝       |     greatest common divisor table of dimensions
⍝       flatten, count all values equal to one in

```

# Answer
> 1 votes
## Sage, 62 or 42

*Runs in the interactive prompt.*

```
c=0
R=range(1,101)
for i in R:
 for j in R:
  c+=gcd(i,j)==1
c

```

Short and easy to understand.

If use of Euler's totient function is allowed, here's a 42-char one-liner:

```
2*sum(euler_phi(n)for n in range(1,101))-1

```

# Answer
> 1 votes
# CJam - ~~18~~ 22

~~100,:):X{dXf/}%:|,~~
Oops, I had missed the "no floating point" requirement. Here is an integer-based solution:

```
100,:):X_:*f*{Xf/}%:|,

```

CJam is a new language I am developing, similar to GolfScript - http://sf.net/p/cjam. Here is the explanation:

`100,` makes an array \[0 1 ... 99\]
`:)` increments all the elements of the array
`:X` assigns to variable X
`_` duplicates the last value (the array)
`:*` multiplies the array elements together, thus calculating 100!
`f*` multiplies each array element with 100!
`{`...`}%` performs a "map" - applies the block to each element
`Xf/` divides the current number by each element in X; since the numbers were already multiplied by 100!, it is an exact division
`:|` performs a fold with the `|` (set union) operator, on the array of arrays we obtained
`,` counts the number of elements

# Answer
> 1 votes
# Haskell 47

```
sum$filter(<2)[gcd a b|a<-[1..100],b<-[1..100]]

```

Run this from the interpreter.

# Answer
> 1 votes
# Husk, 11 bytes

```
LumF/π2ḣ100

```

Try it online!

# Answer
> 0 votes
# Mathematica, 77

```
Length@Select[Range[100]~Tuples~2,#[[1]]==Numerator@Simplify[#[[1]]/#[[2]]]&]

```

Wow, this is the longest one here. Guess I'm not too good at thinking outside the box...

# Answer
> 0 votes
# C++ - 64

```
#include<iostream>
main(){int i=0;while(++i<6087);std::cout<<i;}

```

It counts in *some* way!

# Answer
> 0 votes
# Python, 81 characters

I guess the following solution is more math golf than code golf: it prints all the fractions as well. The algorithm might be an inspiration for code golfers, though.

```
def f(i,j,k,l):
    m,n = i+k,j+l
    if m > 100 or n > 100:
        return 0
    print("%d/%d" % (m,n))
    return f(i,j,m,n)+f(m,n,k,l)+1

print(f(0,1,1,0))

```

So after proving that this does the right thing (it would not be producing all the right fractions if it didn't, would it?), we can write this as

```
f=lambda i,j,k,l:i+k<101>j+l and f(i,j,i+k,j+l)+f(i+k,j+l,k,l)+1;print f(0,1,1,0)

```

Which is 81 characters. At the interactive prompt, you can save the six characters "print " but that seems like a bit of cheating.

It's worth noting that putting 10001 instead of 101 and adding

```
import sys
sys.setrecursionlimit(100000)

```

in front allows to calculate the number of all fractions with nominator/denominator smaller than 10000 in less than a minute. Which is impressive since every single of the 60794971 fractions is actually generated as well as counted separately. And another thing worth noting is that discounting the break-off condition, all positive fractions in shortest terms are generated by this recursion, one per call.

# Answer
> 0 votes
# 05AB1E, 7 bytes

Port of isaacg's Haskell answer.

```
тLãʒ¿}g

```

Try it online!

## Explanation

```
т         Push 100
 L        Length range: [1 .. 100]
  ã       All possible pairs
   ʒ      Filter where:
    ¿         The gcd of the pairs
     }        is equal to 1
      g   Find the length

```

---
Tags: code-golf, counting, rational-numbers
---


title: Mimic the X11 Primary selection

text:
# Question
Title: Mimic the X11 Primary selection
# Background

In X11 (a windowing system used by a lot of Unix-like OS), what you would call the clipboard behave a bit differently than on other OSes like MacOS or Windows. While the "traditional" clipboard using ctrl+v/ctrl+c works, there is also another clipboard, called PRIMARY selection, that behave as following:

* when you select a piece of text, this selection is added to the clipboard
* when you use the middle mouse button, the content of that selection is pasted where your mouse is.

Some more details for those who are interested : X11: How does “the” clipboard work?

# Challenge

The input in this challenge is any representation of a binary input. In the following I will use 'S' for select and 'P' for paste.

Given the input, you must output the input after making the following changes :

* put the content of the current output in the primary selection when you receive a select instruction
* paste the content of the primary selection in the middle of the current output when you receive a paste instruction. If the current output is odd numbered, the middle is the length divided by 2 and truncated.

## Example

Input is `SPSP` :

```
selection = ""
output = "SPSP"
 SPSP
↑

```

```
selection = "SPSP"
output = "SPSP"
 SPSP
 ↑

```

```
selection = "SPSP"
output = "SPSPSPSP"
 SPSP
  ↑

```

```
selection = "SPSPSPSP"
output = "SPSPSPSP"
 SPSP
   ↑

```

```
selection = "SPSPSPSP"
output = "SPSPSPSPSPSPSPSP"
 SPSP
    ↑

```

Final Output is `SPSPSPSPSPSPSPSP`

## Test Cases

```
"" -> ""
"S" -> "S"
"P" -> "P"
"PS" -> "PS"
"SP" -> "SSPP"
"SPP" -> "SSPSPPPPP"
"SPSP" -> "SPSPSPSPSPSPSPSP"
"SPPSP" -> "SPSPPSPSPSPPSPPSPSPPSPPSPSPPSP"
"SPPSPSSS" -> "SPPSSPPSSPPSSPPSSPPSSPPSPSSSPSSSPSSSPSSSPSSSPSSS"

```

## Reference Implementation

In Python 3 :

```
def clipboard(inp, select="S", paste="P"):
    out = inp
    primary_selection = ""
    for instruction in inp:
        if instruction is select:
            primary_selection = out
        if instruction is paste:
            out = out[:len(out)//2] + primary_selection + out[len(out)//2:]
    return out

```

Try it online!

## Rules

* You may assume that the input contains only the "paste" or "select" characters (you don't need to handle error cases)
* You may take your input newline separated (e.g `S\n P\n S\n`)
* You may use any kind of data representation (e.g binary data,`\n`(newline) as a select character and (space) as a paste character, etc.)
* Standard rules , shortest submission by bytes wins!

# Answer
> 4 votes
# Python 2, ~~64~~ 59 bytes

Input is a list of integers, `0` for select and `1` for paste. Outputs by modifying the input list.

```
def c(o,p=[]):
 for y in o*1:p=[o*1,p][y];o[len(o)/2:0]=p*y

```

Try it online!

**Commented**:

```
def c(o, p=[]):
    # o is the current output, p the current clipbord value
    # Iterate over a copy of the input list
    for y in o*1:
        # If y==0 (select) assign a copy of o to p
        p=[o*1,p][y]
        # Replace the empty slice at index len(o)/2 with:
        #  - a copy of p if y==1 (paste)
        #  - an empty list otherwise
        o[len(o)/2:0]=p*y

```

Try it online!

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

```
f=(s,[c,...a]=(p='')+s)=>c?f(c<'S'?s.slice(0,i=s.length/2)+p+s.slice(i):p=s,a):s

```

Try it online!

# Answer
> 4 votes
# Ruby 2.7 `-pl`, ~~61~~ ~~51~~ 47 bytes

*Saved 10 bytes using* `-pl` *instead of* `-nl`.
*Saved 4 bytes using* `.chars` *instead of* `.each_char`, *thanks to Dingus!*

```
s=''
$_.chars{_1>?P?s=$_*1:$_.insert(~/$//2,s)}

```

Try it online!

TIO uses an older version of Ruby, whereas in Ruby 2.7, we've numbered parameters, i.e., `_1`, which saves 2 bytes.

# Answer
> 3 votes
# Perl 5 `-nF`, 45 bytes

```
@o=@F;/S/?@,=@o:splice@o,@F/2,0,@,for@F;say@o

```

Try it online!

Could be shortened by 1 if the input is `0` and `1` instead of `S` and `P`.

# Answer
> 2 votes
# SNOBOL4 (CSNOBOL4), 119 bytes

```
	O =I =INPUT
N	I LEN(1) $ X REM . I	:F(O)S($X)
S	S =O	:(N)
P	O LEN(SIZE(O) / 2) $ L REM $ R =L S R	:(N)
O	OUTPUT =O
END

```

Try it online!

```
	O =I =INPUT					;* Read input and set O to it as well
N	I LEN(1) $ X REM . I	:F(O)S($X)		;* Next character:get the first character of I and set the REMainder to I
							;* if there are no characters left, goto O
							;* else goto the value of X
S	S =O	:(N)					;* on S: set S to O and goto N
P	O LEN(SIZE(O) / 2) $ L REM $ R =L S R	:(N)	;* on P: get the first (left) half of O and set to L,
							;* set the REMainder (right half) to R, and replace with L S R,
							;* then goto N
O	OUTPUT =O					;* output O
END

```

# Answer
> 2 votes
# Charcoal, 24 bytes

```
Ｆθ≡ιS≔θω≔⪫Ｅ⮌⪪⮌θ⊘⊕Ｌθ⮌κωθθ

```

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

```
Ｆθ

```

Loop over the characters of the input.

```
≡ιS

```

If the current character is an `S`, then...

```
≔θω

```

... overwrite the predefined empty string with the current output.

```
≔⪫Ｅ⮌⪪⮌θ⊘⊕Ｌθ⮌κωθ

```

Otherwise, insert the selection into the middle of the current output. Curiously, the best way to do this appears to be to reverse the string, split it by half its length rounded up, then reverse everything back again, finally joining the two halves together using the selection.

```
θ

```

Print the final output.

# Answer
> 2 votes
# Retina 0.8.2, 67 bytes

```
^
¶$'¶
{`.*¶(.+¶)S
$1$1
}`(¶(.)*)((?<-2>.)*(?(2)$).*¶)P
$1$`$3
2=G`

```

Try it online! Link includes test cases. Explanation:

```
^
¶$'¶

```

Insert a blank line representing the clipboard and a copy of the input which becomes the output.

```
{`
}`

```

Repeat until all of the input has been processed.

```
.*¶(.+¶)S
$1$1

```

If the next character in the input is an `S` then copy the output to the clipboard.

```
(¶(.)*)((?<-2>.)*(?(2)$).*¶)P
$1$`$3

```

But if it's a `P` then insert the clipboard into the middle of the output.

```
2=G`

```

Keep just the final output.

# Answer
> 1 votes
# Ruby, 99 bytes

```
->a{s="";(o=a).chars{|n|(n==?S)?s=o:o=o.chars.each_slice((o.size*0.5).ceil).map(&:join).join(s)};o}

```

Try it online!

# Answer
> 1 votes
# 05AB1E, 16 bytes

```
vy'SQi©ëR2äRí®ýá

```

Try it online or verify all test cases.

**Explanation:**

```
v              # Loop `y` over each character of the (implicit) input-string
 y'SQi        '#  If the current `y` is equals to "S":
      ©        #   Store the current string in variable `®`
               #   (which will use the implicit input with the first occurrence of "S")
     ë         #  Else:
      R        #   Reverse the current string
       2ä      #   Split it into two equal-sized parts
               #   (where the first part is longer for odd lengths; hence the reverse)
         Rí    #   Reverse the pair, and each individual string back
           ®ý  #   Join it by `®`
             á #   And only leave the letters in the string
               #   (`®` is -1 by default, so this'll remove it for inputs starting with a "P")
               # (after the loop, the result is output implicitly)

```

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


title: Spiral neighbourhoods

text:
# Question
Title: Spiral neighbourhoods
If we take the natural numbers and roll them up counter clock-wise into a spiral we end up with the following infinite spiral:

```
                  ....--57--56
                             |
36--35--34--33--32--31--30  55
 |                       |   |
37  16--15--14--13--12  29  54
 |   |               |   |   |
38  17   4---3---2  11  28  53
 |   |   |       |   |   |   |
39  18   5   0---1  10  27  52
 |   |   |           |   |   |
40  19   6---7---8---9  26  51
 |   |                   |   |
41  20--21--22--23--24--25  50
 |                           |
42--43--44--45--46--47--48--49

```

Given some number in that spiral your task is to determine its neighbours - meaning the element above, left, right and below it.

### Example

If we have a look at `27` we can see that it has the following neighbours:

* above: `28`
* left: `10`
* right: `52`
* below: `26`

So the output would be: `[28,10,52,26]`

### Rules

* Input will be a number \\$n \geq 0\\$ in any default I/O format
* Output will be a list/matrix/.. of that numbers' 4 neighbours in any (consistent!) order
* You may work with a spiral that starts with 1 instead of 0, however you should specify that in your answer

### Examples

The output is in the format `[above,left,right,below]` and uses a 0-based spiral:

```
0  ->  [3,5,1,7]
1  ->  [2,0,10,8]
2  ->  [13,3,11,1]
3  ->  [14,4,2,0]
6  ->  [5,19,7,21]
16  ->  [35,37,15,17]
25  ->  [26,24,50,48]
27  ->  [28,10,52,26]
73  ->  [42,72,74,112]
101  ->  [100,146,64,102]
2000  ->  [1825,1999,2001,2183]
1000000  ->  [1004003,1004005,999999,1000001]

```

# Answer
> 7 votes
# , 156 bytes

```
function(n){g=function(h)c(0,cumsum(h((4*(0:(n+2)^2)+1)^.5%%4%/%1/2)))
x=g(sinpi)
y=g(cospi)
a=x[n]
b=y[n]
which(x==a&(y==b+1|y==b-1)|y==b&(x==a+1|x==a-1))}

```

Try it online!

* posted another R answer since it's a slightly different approach than @ngn
* 1-indexed
* neighbours are always sorted by ascending value
* saved 6 bytes removing `round` and using `cospi(x)/sinpi(x)` which are more precise than `cos(x*pi)/sin(x*pi)` in case of half numbers (`0.5`, `1.5` etc...)
* saved another byte removing the minus on y coordinates since the result is the same (just up/down neighbours are reversed)

---

## **Explanation :**

If we look at the matrix coordinates of the values, considering the first value `0` placed at `x=0, y=0`, they are :

```
x = [0,  1,  1,  0, -1, -1, -1,  0,  1,  2,  2,  2,  2,  1,  0, ...]
y = [0,  0,  1,  1,  1,  0, -1, -1, -1, -1,  0,  1,  2,  2,  2, ...]

```

The `x` coordinates follow the A174344 OEIS sequence with the recursive formula :

```
a(1) = 0, a(n) = a(n-1) + sin(mod(floor(sqrt(4*(n-2)+1)),4)*pi/2)

```

The same formula holds for `y` matrix coordinates, but with `cos` instead of `sin` and negated :

```
a(1) = 0, a(n) = a(n-1) - cos(mod(floor(sqrt(4*(n-2)+1)),4)*pi/2)

```

So, in R we can translate the formula to this function, taking `sinpi/cospi` as parameter :

```
g=function(h)c(0,cumsum(h((4*(0:(n+2)^2)+1)^.5%%4%/%1/2)))

```

and we generate the two coordinates vectors (we don't negate the y coords since we'll get the same result, just with up/down neighbours reversed) :

```
x=g(sinpi)
y=g(cospi)

```

Note that we have generated `(n+2)^2` coordinates, which are more than the minimum necessary coordinates containing both `n` and their neighbours (a tighter bound would be `(floor(sqrt(n))+2)^2` but unfortunately is less "golfy").

Therefore, now that we have all the coordinates, we first search the coordinates `a,b` corresponding to our `n` :

```
a=x[n]
b=y[n]

```

finally we select the positions of their neighbours, i.e. :

* the up/down neighbours `where x == a and y == b+1 or b-1`
* the right/left neighbours `where y == b and x == a+1 or a-1`

using :

```
which(x==a&(y==b+1|y==b-1)|y==b&(x==a+1|x==a-1))

```

# Answer
> 5 votes
# ~~Perl 6~~Raku, ~~94~~ ~~83~~ 78 bytes

~~{my \s=0,|\[+\] flat((1,*i...*)Zxx flat(1..Inf Z 1..Inf));map {first :k,s\[$\_\]+$^d,s},i,-1,1,-i}~~

~~{my \s=0,|\[+\] flat((1,*i...*)Zxx(1,1.5...\*));map {first :k,s\[$\_\]+$^d,s},i,-1,1,-i}~~

```
{my \s=0,|[\+] flat (1,*i...*)Zxx(1,3/2...*);(grep :k,1==(s[$_]-*).abs,s)[^4]}

```

Try it online!

`s` is a lazy, infinite list of spiral coordinates, represented as complex numbers. It's constructed from two other infinite lists: `1, *i ... *` makes the list `1, i, -1, -i ...`. `1, 1.5 ... *` makes the list `1, 1.5, 2, 2.5, 3, 3.5 ...`. Zipping these two lists together with list replication produces the list of steps from each spiral coordinate to the next: `1, i, -1, -1, -i, -i, 1, 1, 1, i, i, i ...`. (The fractional parts of the right-hand arguments to the list replication operator are discarded.) Doing a triangular addition reduction (`[\+]`) on this list (and pasting 0 onto the front) produces the list of spiral coordinates.

~~Finally, starting from the complex number `s[$_]` (`$_` being the sole argument to the function), we look up the indexes (`first :k`) in the spiral of the complex numbers which are offset from that number by `i`, `-1`, `1`, and `-i`.~~

I shaved a few bytes off by searching for the matching elements in index order, and by testing that the absolute value of the complex difference between the coordinates is 1, rather than testing for 1, -1, i, and -1 explicitly.

# Answer
> 5 votes
# Brain-Flak, 238 bytes

```
((){[()]<((({}[((()))]<>)<<>{((([{}]({}))([{}]{})())[()]){({}[()])<>}{}}>)<<>({}<(((({}{})()){}<>({}))()())<>>)<>>()())<>{{}((()()()[({})]){}<>({}<{}>))(<>)}>}{}){<>((((())()())()())()())(<>)}{}{({}[()]<<>({}<>)<>({}<({}<({}<>)>)>)<>>)}<>

```

Try it online!

Output is in the order left, up, right, down.

### Explanation

```
# If n is nonzero:
((){[()]<

  ((

    # Push 1 twice, and push n-1 onto other stack.
    ({}[((()))]<>)

    # Determine how many times spiral turns up to n, and whether we are on a corner.
    # This is like the standard modulus algorithm, but the "modulus" used
    # increases as 1, 1, 2, 2, 3, 3, ...
    <<>{((([{}]({}))([{}]{})())[()]){({}[()])<>}{}}>

  # Push n-1: this is the number behind n in the spiral.
  )<

    # While maintaining the "modulus" part of the result:
    <>({}<

      # Push n+2k+1 and n+2k+3 on top of n-1, where k is 3 more than the number of turns.
      # n+2k+1 is always the number to the right in the direction travelled.
      # If we are on a corner, n+2k+3 is the number straight ahead.
      (((({}{})()){}<>({}))()())<>

    >)<>

  # Push n+1.  If we are on a corner, we now have left, front, right, and back
  # on the stack (from top to bottom)
  >()())

  # If not on a corner:
  <>{{}

    # Remove n+2k+3 from the stack entirely, and push 6-2k+(n+1) on top of the stack.
    ((()()()[({})]){}<>({}<{}>))

  (<>)}

>}{})

# If n was zero instead:
{

  # Push 1, 3, 5, 7 on right stack, and implicitly use 1 (from if/else code) as k.
  <>((((())()())()())()())

(<>)}{}

# Roll stack k times to move to an absolute reference frame
# (switching which stack we're on each time for convenience)
{({}[()]<<>({}<>)<>({}<({}<({}<>)>)>)<>>)}<>

```

# Answer
> 4 votes
# MATL, 15 bytes

```
2+1YLtG=1Y6Z+g)

```

Input and output are 1-based.

The output gives the left, down, up and right neighbours in that order.

Try it online! Or verify all test cases except the last two, which time out on TIO.

```
2+      % Implicit input: n. Add 2. This is needed so that
        % the spiral is big enough
1YL     % Spiral with side n+2. Gives a square matrix
t       % Duplicate
G=      % Compare with n, element-wise. Gives 1 for entry containing n
1Y6     % Push 3×3 mask with 4-neighbourhood
Z+      % 2D convolution, keeping size. Gives 1 for neighbours of the
        % entry that contained n
g       % Convert to logical, to be used as an index
)       % Index into copy of the spiral. Implicit display

```

# Answer
> 3 votes
# JavaScript (V8),  ~~165 162~~  151 bytes

Prints the indices.

```
f=(n,x=w=y=n+2)=>y+w&&[-1,0,1,2].map(d=>(g=(x,y)=>(k=2*Math.max(x,-x,y,-y))*k+(k+x+y)*(y>=x||-1))(x+d%2,y+~-d%2)-n||print(g(x,y)))|f(n,x+w?x-1:(y--,w))

```

Try it online!

### How?

For \\$x, y \in \mathbb{Z}\\$, we compute the 0-based index \\$I\_{x,y}\\$ of the spiral with:

$$A\_{x,y}=2\cdot\max(|x|,|y|)$$ $$S\_{x,y}=\begin{cases}1,&\text{if }y\ge x\\\-1,&\text{if }y\<x\end{cases}$$ $$I\_{x,y}=A\_{x,y}^2+(A\_{x,y}+x+y)\times S\_{x,y}$$

*Adapted from this answer from math.stackexchange.*
*Also used in Can you make your way through the Ulam spiral?*
*Saved 1 byte thanks to @att.*

# Answer
> 3 votes
# , 172 bytes

```
function(x,n=2*x+3,i=cumsum(rep(rep(c(1,n,-1,-n),l=2*n-1),n-seq(2*n-1)%/%2))){F[i]=n^2-1:n^2
m=matrix(F,n,n,T)
j=which(m==x,T)
c(m[j[1],j[2]+c(-1,1)],m[j[1]+c(-1,1),j[2]])}

```

Try it online!

This is R, so obviously the answer is 0-indexed.

Most of the work is creating the matrix. Code inspired by: https://rosettacode.org/wiki/Spiral\_matrix#R

# Answer
> 3 votes
# Python 2, ~~177~~ ~~164~~ 1~~46~~ 144 bytes

```
def f(n):N=int(n**.5);S=N*N;K=S+N;F=4*N;return[n+[F+3,[-1,1-F][n>K]][n>S],n+[F+5,-1][n>K],n+[[1,3-F][n<K],-1][0<n==S],n+[F+7,1][n<K]][::1-N%2*2]

```

Try it online!

Calculates `u,l,r,d` directly from `n`.

# Answer
> 2 votes
# APL (Dyalog Unicode), <sup>~~66~~</sup> 60 bytes

```
{(⊃⍸⍵=s)⌷{⊢/4 2⍴⍵}⌺3 3⊢s←{⌽⍉⍵⍪⍨⌽(⍳(⌈/⍴⍵)+⌈/,⍵)~,⍵}⍣(⍵+4)⊢⍪1}

```

Try it online!

1-indexed.

I'd been wanting to solve spiral challenges in APL for a while, so I figured I'd make a spiral creating function for this. I've used simple array magic to make it(and ngn will probably find an insane math relation to calculate it, most likely).

-6 bytes from Adám.

## Explanation

```
{(⊃⍸⍵=s)⌷{⊢/4 2⍴⍵}⌺3 3⊢s←{⌽⍉⍵⍪⍨⌽(⍳(⌈/⍴⍵)+⌈/,⍵)~,⍵}⍣(⍵+4)⊢⍪1} input → n
                                                         ⍪1  to [[1]],
                                                  ⍣(⍵+4)⊢    apply the following n+4 times:
                                (⍳(⌈/⍴⍵)+⌈/,⍵)               range 1..max(i)+max(shape(i))
                                              ~,⍵            without i
                            ⍵⍪⍨                              add that as a row

                          ⌽⍉                                 rotate 90 degrees clockwise

                       s←                                    assign the spiral to s
         {       }⌺3 3⊢                                      to the 3x3 paritions of the spiral:
          ⊢/4 2⍴⍵                                            get every 2nd element

 ⊃⍸⍵=s                                                       find indices of n in the spiral
(     )⌷                                                     and index into the matrix of neighbours

```

# Answer
> 1 votes
# PHP (\>=5.4), 208 bytes

```
<?$n=$argv[1];for(;$i++<($c=ceil(sqrt($n))+($c%2?2:3))**2;$i!=$n?:$x=-$v,$i!=$n?:$y=+$h,${hv[$m&1]}+=$m&2?-1:1,$k++<$p?:$p+=$m++%2+$k=0)$r[-$v][+$h]=$i;foreach([0,1,0,-1]as$k=>$i)echo$r[$x+$i][$y+~-$k%2].' ';

```

To run it:

```
php -n -d error_reporting=0 <filename> <n>

```

Example:

```
php -n -d error_reporting=0 spiral_neighbourhoods.php 2001

```

Or Try it online!

**Notes:**

* The `-d error_reporting=0` option is used to not output notices/warnings.
* This spiral starts with 1.

---

# How?

I'm generating the spiral with a modified version of this answer in a 2 dimensional array.

I decide on the size of the spiral based on the input `n` with a formula to always get an extra round of numbers in the spiral (guarantee for existence of above/below/left/right). An extra round of numbers means `+2` in height and `+2` in width of the 2 dimensional array.

So if `n` will be located in a spiral with maximum size of `3*3`, then generated spiral will be `5*5`.

Spiral size is `c*c` where `c = ceil(sqrt(n)) + k`, if `ceil(sqrt(n))` is odd, then `k` is 2 and if `ceil(sqrt(n))` is even, then `k` is 3.

For example, the above formula will result in this:

* If `n = 1` then `c = 3` and spiral size will be `3*3`
* If `n <= 9` then `c = 5` and spiral size will be `5*5`
* If `n <= 25` then `c = 7` and spiral size will be `7*7`
* If `n <= 49` then `c = 9` and spiral size will be `9*9`
* And so on ...

While generating the spiral, I store the `x` and `y` of `n` and after generation, I output the elements above/below/left/right of it.

---
Tags: code-golf, integer
---


# Question
Title: Can you make your way through the Ulam spiral?
You will be given a point `(x,y)` relative to the center of the Ulam spiral (the center being the point which represents one), and length `z`. The task is to check whether there exists a path from `(0,0)` to `(x,y)` of length `z`, assuming prime numbers are obstacles and each turn in path has an angle of 90 degrees. Path may not overlap with itself. `(x,y)` may not be a prime.

Examples of valid paths:

```
XXXX
   XX
    X
    X
    XXXXXXXX

```

```
    XXXXXX
XXXXX

```

```
XXXXXXXXXXXXXX
             X
             X
             X
             XXXXXXX

```

Examples of invalid paths:

```
XXXXXXXXXXXX
            XXXXX

```

```
XXXXX   XXXXXX
     X X
      X

```

```
XXX
   X
  X
   XXXXXXXXXXX

```

```
       X
       X
XXXXXXX!XXX
       X  X
       XXXX

The path above overlaps in a place marked with !.

```

For the record, this is a fragment of a Ulam spiral with `1 (0,0)` marked:

```
............#...#.......#...#
.#...#...........#.#.....#...
#.#.....#.#.....#.....#......
.........#...........#...#...
....#...#.......#.....#......
...#.........#...#.#...#.#.#.
......#.....#.........#.#...#
.#.....#...#.#...............
..............#.#.....#...#..
...#...#.#...#.......#...#.#.
..............#.#...#........
.....#...#.#.....#.#.#.....#.
#.#.#.#.#.#.#...#.......#....
.............#.#.#...........
........#...#.1##.#.#.#...#.#
.#.......#.#.#...............
..........#...#..............
...#.#...#.#...#...#.#...#...
..#...#...#.....#.....#.#...#
...........#...........#.....
......#.#.....#...#...#......
...#...#...........#.......#.
....#.....#...#.#............
.........#.#...#.....#...#...
#.#.#.........#.#.....#.....#
.#...#...........#.#.........
#.#.....#.....#...#.#........
.......#.........#.......#...
........#.#...#.#.........#..

```

## I/O examples

```
Input: (5, -1), 7 - true
Suggested path:
1##.#.#.#...#.#
XXXXXX.........
#..............

Input: (3, 0), 6 - true
Suggested path:
.#.#.#...........
#.1##X#.#.#...#.#
.#XXXX...........

Input: (-2, -1), 18 - true
Suggested path:
...#...#.#...#.......#...#.#.
..............#.#...#........
.....#...#.#.....#.#.#.....#.
#.#.#.#.#.#.#...#.......#....
.............#.#.#...........
........#...#.1##.#.#.#...#.#
.#.......#.#X#XX............
..........#.XX#XX............
...#.#...#.#.XX#XX.#.#...#...
..#...#...#...XX#X....#.#...#
...........#...XXX.....#.....

Input: (2, 1), 6 - false
Input: (-5, 2), 20 - true
Input: (-1, 0), 5 - false

```

## Additional considerations

`abs(x) <= 20` and `abs(y) <= 20` cases have to be resolved within the TIO time limit (soft bound; 60s) to verify validity of the answers. The answers have to (theoretically and ideally) work on any reasonable input.

# Answer
> 7 votes
# JavaScript (ES6), 169 bytes

*Saved 1 byte thanks to @att*

Expects `(z)(x,y)`. Returns *false* if there's a solution or *true* otherwise.

```
z=>F=(X,Y,i=z,k)=>--i?[-1,0,1,2].every(d=>(g=d=>n%--d?g(d):d==1)(n=(k=2*Math.max(x=X+d%2,-x,y=Y+~-d%2,-y))*k-~(-y<x?y-k-x:k+x-y))|F[k=[x,y]]||F(x,y,i,F[k]=1)|--F[k]):X|Y

```

This is fast enough for all existing test cases, but I guess it's likely to time out on some other ones.

Try it online!

### Commented

NB: the spiral formula is similar to the one I used in my answer to Spiral neighbourhoods.

```
z =>                              // outer function taking z
F = (                             // main recursive function taking:
  X, Y,                           //   (X, Y) = current position
  i = z,                          //   i = move counter initialized to z
  k                               //   k = local variable whose initial value is ignored
) =>                              //
  --i ?                           // decrement i; if it's not equal to 0:
    [-1, 0, 1, 2].every(d =>      //   for each direction d:
      ( g = d => n % --d ? g(d)   //     g is a recursive primality test function
                         : d == 1 //     which is invoked ...
      )(                          //
        n =                       //     ... on the 1-indexed square ID n defined as:
          ( k = 2 * Math.max(     //       k² + (k + x - y) * s + 1
              x = X + d % 2, -x,  //       with:
              y = Y + ~-d % 2, -y //         x = X + dx
            )                     //         y = Y + dy
          ) * k -                 //         k = 2 * max(|x|,|y|) = 2 * max(x,-x,y,-y)
          ~(-y < x ? y - k - x    //         s = -1 if -y < x or 1 otherwise
                   : k + x - y)   //
      )                           //     abort if n is prime
      | F[k = [x, y]]             //     or (x, y) was already visited
      || F(x, y, i, F[k] = 1)     //     otherwise mark (x, y) as visited and do a
                                  //     recursive call with the new position
      | --F[k]                    //     clear the mark afterwards
    )                             //   end of every()
  :                               // else:
    X | Y                         //   falsy if and only if X = Y = 0

```

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

```
(a=0;Do[g@a=b;a-=I^⌈2√b⌉,{b,8#^2}];1!=##2&&!PrimeQ@g@#2&&If[#<2,0==#2,Or@@#0[#-1,#2+I^i,##2]~Table~{i,4}]&@##)&

```

Try it online!

Input \\$z\\$ and a complex number \\$x+iy\\$.

```
1!=##2&&!PrimeQ@g@#2                            (* check if the current path is valid *)
&&If[#<2,0==#2                                  (* if the length is reached, check if the endpoint is the origin *)
    Or@@#0[#-1,#2+I^i,##2]~Table~{i,4}]&        (*  otherwise, check if any child paths succeed *)

(a=0;Do[g@a=b;a-=I^⌈2√b⌉,{b,8#^2}]; % &@##)&    (* cache indices of a sufficiently large spiral first. *)

```

---

### 110 bytes

```
1!=##2&&!PrimeQ[b=1;0//.a_/;a!=#2:>a-I^⌈2√b++⌉;b]&&If[#<2,0==#2,Or@@#0[#-1,#2+I^i,##2]~Table~{i,4}]&@##&

```

Try it online!

Same principle, but takes much longer without cached spiral indices.

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


# Question
Title: (KevinC's) Triangular DeciDigits Sequence
**Input:**

A positive integer ***n*** which is `1 <= n <= 25000`.

**Output:**

1. In this sequence we start with the decimal number 1/***n***.
2. Then we take the sum of digits up until the ***n***'th digit after the comma (1-indexed); followed by the sum of digits up until the (***n***-1)'th, then (***n***-2)'th, etc. Continue until ***n*** is 1.
3. **The output** is the sum of all these combined.

**For example:**

```
n = 7
1/7 = 0.1428571428...
7th digit-sum = 1+4+2+8+5+7+1 = 28
6th digit-sum = 1+4+2+8+5+7 = 27
5th digit-sum = 1+4+2+8+5 = 20
4th digit-sum = 1+4+2+8 = 15
3rd digit-sum = 1+4+2 = 7
2nd digit-sum = 1+4 = 5
1st digit     = 1
Output = 28+27+20+15+7+5+1 = 103

```

**Challenge rules:**

* If the decimal of 1/***n*** doesn't have ***n*** digits after the comma, the missing ones will be counted as 0 (i.e. `1/2 = 0.50 => (5+0) + (5) = 10`).
* You take the digits without rounding (i.e. the digits of `1/6` are `166666` and not `166667`)

**General rules:**

* Standard rules apply for your answer, so you are allowed to use STDIN/STDOUT, functions/method with the proper parameters, full programs. Your call.
* Default Loopholes are forbidden.
* If possible, please add a link with a test for your code.
* Also, please add an explanation if necessary.

**First 1 - 50 in the sequence:**

```
0, 10, 18, 23, 10, 96, 103, 52, 45, 10, 270, 253, 402, 403, 630, 183, 660, 765, 819, 95, 975, 1034, 1221, 1500, 96, 1479, 1197, 1658, 1953, 1305, 1674, 321, 816, 2490, 2704, 4235, 2022, 3242, 2295, 268, 2944, 3787, 3874, 4097, 1980, 4380, 4968, 3424, 4854, 98

```

**Last 24990 - 25000 in the sequence:**

```
1405098782, 1417995426, 1364392256, 1404501980, 1408005544, 1377273489, 1395684561, 1405849947, 1406216741, 1142066735, 99984

```

# Answer
> 6 votes
# Jelly, 9 bytes

```
R⁵*:%⁵+\S

```

Rather slow, but short. Try it online! or verify the first 50 test cases.

### How it works

```
R⁵*:%⁵+\S  Main link. Argument: n

R          Range; yield [1, ..., n].
 ⁵*        10 power; yield [10**1, ..., 10**n].
   :       Divide each power by n.
    %⁵     Take each quotient modulo 10.
           This yields all desired decimal digits.
      +\   Take the cumulative sum of the digits.
        S  Take the sum.

```

# Answer
> 15 votes
## Mathematica, 42 bytes

```
#&@@RealDigits[1/#,10,#,-1].(#-Range@#+1)&

```

or

```
#&@@RealDigits[1/#,10,#,-1].Range[#,1,-1]&

```

or

```
Tr@Accumulate@#&@@RealDigits[1/#,10,#,-1]&

```

### Explanation

Take the example from the challenge spec. We want to compute:

```
  1+4+2+8+5+7+1
+ 1+4+2+8+5+7
+ 1+4+2+8+5
+ 1+4+2+8
+ 1+4+2
+ 1+4
+ 1

```

Rearranging, this is:

```
  1*7 + 4*6 + 2*5 + 8*4 + 5*3 + 7*2 + 1*1
= (1, 4, 2, 8, 5, 7, 1) . (7, 6, 5, 4, 3, 2, 1)

```

where `.` is the scalar product of two vectors.

That's pretty much all the solution does.

```
#&@@RealDigits[1/#,10,#,-1]

```

This gets us the first `N` decimal digits of `1/N` (the `#&@@` extracts the first element of the `RealDigits` result because that also returns the offset of the first digit which we don't care about).

Then we get the list from `N` down to `1` either using `(#-Range@#+1)` or `Range[#,1,-1]`, both of which are shorter than `Reverse@Range@#`, and take the scalar product.

The alternative solution instead uses `Accumulate` to compute a list of all prefix sums and then adds up those prefix sums with `Tr`.

Since this is really fast even for large inputs, here is a scatter plot of the sequence up to `N = 100,000` (doing *all* of them and plotting them took a while though):

Click for larger version.

The blue line is the naive upper bound of `9 N (N+1) / 2` (if all the decimal digits were `9`) and the orange line is exactly half of that. Unsurprisingly this is right inside the main branch of the plot since, statistically, we'd expect the average digit to be 4.5.

The thin line of plot points which you can see below the main branch are fractions which end in `...3333...`, as they all lie very close to `3 N (N+1) / 2`.

# Answer
> 6 votes
# 05AB1E, ~~12~~ 11 bytes

```
Di<ë°¹÷.pSO

```

Try it online! or a Test suite for the first 50 numbers.

**Explanation**

```
              # implicit input n
Di<           # if n == 1 then 0
   ë          # else
    °¹÷       # 10^n // n
       .p     # get prefixes
         SO   # sum digits

```

**A more efficient version for trying big numbers on TIO**

The difference to the shorter version is that here we sum the product of the digits and the reversal of their 1-based index instead of summing digits in prefixes.

```
Di<ë°¹÷SDgLR*O

```

Try it online!

# Answer
> 5 votes
# Java 8, ~~181~~ ~~169~~ ~~166~~ ~~153~~ 142 bytes

```
import java.math.*;n->{int m=n+2,r=0,i;for(;m>2;)for(i=m--;i-->2;r+=(BigDecimal.ONE.divide(new BigDecimal(n),n,3)+"").charAt(i)-48);return r;}

```

**Explanation:**

Try it here.

```
import java.math.*;   // Required import for BigDecimal

n->{                  // Method with integer as both parameter and return-type
  int m=n+2,          //  Copy of the input-integer plus 2
      r=0,            //  Result-integer, starting at 0
      i;              //  Index-integer
  for(;m>2;)          //  Loop (1) as long as `m` is larger than 2
    for(i=m--;        //   Set index `i` to `m`, and decrease `m` by one afterwards
        i-->2;        //   Inner loop (2) from `m` down to 2 (inclusive)
      r+=             //    Add to the result-sum:
         (BigDecimal.ONE.divide(
                      //     1 divided by,
           new BigDecimal(n),
                      //     the input
           n,3)       //     With the minimal required precision
          +"")        //     Convert this to a String
          .charAt(i)  //     Take the character of this String at index `i`
          -48         //     And convert it to a number
     );               //   End of inner loop (2)
                      //  End of loop (1) (implicit / single-line body)
  return r;           //  Return result
}                     // End of method

```

# Answer
> 4 votes
# PHP, ~~66~~ 65 bytes

```
for($b=$c=$argv[$a=1];$c;)$o+=$c--*(($a=10*($a%$b))/$b^0);echo$o;

```

Adapted from this answer (also by me): Division of not so little numbers and Jörg Hülsermann's suggested edit to it. Use like:

```
php -r "for($b=$c=$argv[$a=1];$c;)$o+=$c--*(($a=10*($a%$b))/$b^0);echo$o;" 7

```

edit: corrected a bug for +1 bytes and folded the assignment of $a into $argv\[1\] for -2 bytes for a net 1 byte less.

# Answer
> 3 votes
# Scala, 84 bytes

```
val b=BigDecimal
def?(& :Int)=1 to&map(x=>(""+b(1)/b(&))slice(2,x+2)map(_-48)sum)sum

```

Ungolfed:

```
def f(n: Int)={
  val digits = ""+BigDecimal(1)/BigDecimal(n)
  (1 to n).map( x=>
    digits.slice(2, x+2).map(d => d - 48).sum
  ).sum

```

Explanation:

```
val b=BigDecimal   //define an alias for BigDecimal
def?(& :Int)=      //define a method called ? with an integer & as a parameter
  1 to &           //create a range from 1 to &
  map(x=>          //for each number x...
    (""+b(1)/b(&))   //calculate the fraction
    slice(2,x+2)     //and take the slice starting from the third element,
                     //(dropping the "1.") and containing x elements
    map(_-48)        //for each char, subtract 48 to get the integer value
    sum              //and sum them
  )sum             //and take the sum

```

I could save some bytes by exploiting the way the compiler tokenizes: By calling the argument `&`, you can write `1 to&map` instead of `1 to n map`. The same rule applies to `def?`.

# Answer
> 3 votes
# PHP, 76 bytes

(Edit -1 byte - Thanks user59178 - your solution is even better)

```
for($c=substr(bcdiv(1,$a=$argv[1],$a),2);$i<$a;)$s+=($a-$i)*$c[$i++];echo$s;

```

# Answer
> 3 votes
# Jelly, 11 bytes

```
’aµR⁵*:µDFS

```

**TryItOnline**
First 50

Too slow for the large test cases.

### How?

```
’aµR⁵*:µDFS - Main link: n
’           - decrement
 a          - and (to handle special case where n=1, to return 0 rather than 10)
  µ         - monadic chain separation
   R        - range: [1,2,...n]
    ⁵       - literal 10
     *      - exponentiation: [10,100,...,10^n]
      :     - integer division: [10//n,100//n,...,10^n//n]
       µ    - monadic chain separation
        D   - cast to a decimal list [[digits of 10//n],[digits of 100//n],...]
         F  - flatten into one list
          S - sum

```

# Answer
> 2 votes
# MATL, 19 bytes

```
li/GEY$4LQ)!UYsG:)s

```

**Try it Online!**

**Explanation**

```
l       % Push a 1 literal to the stack
i/      % Grab the input (n) and compute 1/n
GE      % Grab the input again and multiply by 2 (2n)
Y$      % Compute the first 2n digits of 1/n after the decimal
4LQ)    % Get only the digits past the decimal point
!U      % Convert to numbers
Ys      % Compute the cumulative sum
G:)     % Get the first n terms
s       % Sum the result and implicitly display

```

# Answer
> 2 votes
# Groovy, 87 Bytes

This was less painful than I anticipated, and is based on my answer here:

```
{n->(1..n).collect{x->(1.0g.divide(n, n, 1)+"")[2..x+1].getChars().sum()-48*(x)}.sum()}

```

## Explanation

`1.0g` \- Use BigDecimal notation for the one.

`.divide(n, n, 1)+""` \- Divide by n with n precision (BigDecimal function only) and convert to str.

`(...)[2..x+1].getChars()` \- Get the substring of the current iteration as an array of char.

`.sum()-48*(x)` \- Sum the ASCII values of the characters and reduce by 48 for each element. This turns the value from an ASCII digit to an Integer essentially saving bytes over `*.toInteger()`.

`(1..n).collect{...}.sum()` \- Iterate over each of the digits in the division, doing this function, get them all in a single array and sum.

## Saved 2 Bytes and Sacrificed Efficiency...

This is a more efficient version that does not recalculate the BigDecimal each iteration.

```
{n->i=1.0g.divide(n, n, 1)+"";(1..n).collect{x->i[2..x+1].getChars().sum()-48*(x)}.sum()}

```

# Answer
> 2 votes
# J, 27 bytes

```
1#.[:+/\-{.10#.inv%<.@*10^]

```

## Usage

The input is an extended integer.

```
   f =: 1#.[:+/\-{.10#.inv%<.@*10^]
   (,.f"0) (>: i. 50x) , 24990x + i. 11
    1          0
    2         10
    3         18
    4         23
    5         10
    6         96
    7        103
    8         52
    9         45
   10         10
   11        270
   12        253
   13        402
   14        403
   15        630
   16        183
   17        660
   18        765
   19        819
   20         95
   21        975
   22       1034
   23       1221
   24       1500
   25         96
   26       1479
   27       1197
   28       1658
   29       1953
   30       1305
   31       1674
   32        321
   33        816
   34       2490
   35       2704
   36       4235
   37       2022
   38       3242
   39       2295
   40        268
   41       2944
   42       3787
   43       3874
   44       4097
   45       1980
   46       4380
   47       4968
   48       3424
   49       4854
   50         98
24990 1405098782
24991 1417995426
24992 1364392256
24993 1404501980
24994 1408005544
24995 1377273489
24996 1395684561
24997 1405849947
24998 1406216741
24999 1142066735
25000      99984

```

The performance is good and only requires about 3 seconds to compute for the large test cases.

```
   timex 'f 7x'
0.000119
   timex 'f 24999x'
3.8823
   timex 'f 25000x'
3.14903

```

## Explanation

```
1#.[:+/\-{.10#.inv%<.@*10^]  Input: n
                          ]  Get n
                       10^   Raise 10 to the nth power
                  %          Get the reciprocal of n
                      *      Multiply (1/n) with (10^n)
                   <.@       Floor it
           10#.inv           Convert it to a list of base 10 digits
        -                    Negate n
         {.                  Take the last n values from the list of digits
                             (This is to handle the case for n = 1)
   [:  \                     For each prefix of the list of digits
     +/                        Reduce it using addition to get the sum
1#.                          Convert those sums as base 1 digits and return
                             (This is equivalent to taking the sum)

```

# Answer
> 2 votes
# Jelly, 10 bytes

```
⁵*:⁸D+\_ỊS

```

Not the shortest approach, but fairly efficient. Try it online! or verify all test cases.

### How it works

```
⁵*:⁸D+\_ỊS  Main link. Argument: n (integer)

⁵*          Yield 10**n.
  :⁸        Divide 10**n by n (integer division).
    D       Convert the quotient to base 10.
     +\     Take the cumulative sum of the digits.
        Ị   Insignificant; yield (abs(n) <= 1).
       _    Subtract the resulting Boolean from each decimal digit.
            This takes care of edge case n = 1, which would return 2 otherwise.
         S  Take the sum.

```

# Answer
> 1 votes
## Python 2, 90 bytes

```
lambda o:sum([sum([int(i)for i in s])for s in map(lambda x:str(1.0/o)[2:x],range(3,3+o))])

```

Not pretty, but done through float dividing then converting to a string and then iterative string index selection to get the triangle of numbers, then perform list comprehension and convert each char to an int and finally summing them all.

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

```
f=(b,a=1%b,c=b+1)=>c&&(a/b|0)*c+f(b,a%b*10,c-1)

```

## How it works

This answer demonstrates a technique for calculating **c** decimal digits of **a/b**:

```
f=(a,b,c,d=".")=>~c?(a/b|0)+d+f(a%b*10,b,c-1,""):d

```

This will make an excellent starting point for this challenge. First we can change it slightly so that it calculates **b** decimal digits of **1/b**, by reordering the parameters and setting defaults:

```
f=(b,a=1,c=b,d=".")=>~c?(a/b|0)+d+f(b,a%b*10,c-1,""):d

```

Next we can change this so that it calculates the sum of of the first **b** decimal digits, instead of concatenating them (this does away with the `d` parameter):

```
f=(b,a=1,c=b)=>~c?(a/b|0)+f(b,a%b*10,c-1):0

```

We're almost to a solution; now we just need to make it multiply each digit by **c+1**:

```
f=(b,a=1,c=b)=>~c?(a/b|0)*-~c+f(b,a%b*10,c-1):0

```

Hmm, this seems a little long. What if we incremented **c** by 1 to begin with?

```
f=(b,a=1,c=b+1)=>c?(a/b|0)*c+f(b,a%b*10,c-1):0

```

That saves one byte. And here's a way to save one more:

```
f=(b,a=1,c=b+1)=>c&&(a/b|0)*c+f(b,a%b*10,c-1)

```

And now we have our answer. `f(7)` is 103, `f(11)` is 270, `f(1)` is... 2? Oh, we forgot to account for the case where **a/b** is 1 on the first iteration (i.e. **b** is 1). Let's do something about this:

```
f=(b,a=1%b,c=b+1)=>c&&(a/b|0)*c+f(b,a%b*10,c-1)

```

**1 mod b** is always **1**, unless **b** is **1**, in which case it will be **0**. Our program is now correct for all inputs, at **47 bytes**.

# Answer
> 1 votes
# Python 2, 49 bytes

```
lambda n:sum(10**-~k/n%10*(n-k)for k in range(n))

```

Test it on Ideone.

# Answer
> 1 votes
# Husk, 11 bytes

```
ṁΣḣdi*^¹10\

```

Try it online!

## Explanation

```
ṁΣḣdi*^¹10\
          \ reciprocal of input
     *^¹10  multiply with 10^input
    i       convert to int
   d        digits
  ḣ         prefixes
ṁΣ          map-sum with sum

```

# Answer
> 1 votes
# 05AB1E, 9 bytes

```
L°¹÷T%ηOO

```

Try it online!

```
L°¹÷T%ηOO  # full program
        O  # sum of...
       O   # sums of...
           # (implicit) each element of...
      η    # prefixes of...
 °         # 10 to the power of...
           # (implicit) each element of...
L          # [1, 2, 3, ...,
           # ..., implicit input]...
   ÷       # integer divided by...
  ¹        # input...
     %     # modulo...
    T      # 10
           # implicit output

```

# Answer
> 0 votes
**C, 53 bytes**

```
f(n,i,x,s){while(i)x=10*(x%n),s+=i--*(x/n);return s;}

```

Below the main for to do some test...

```
//44,79
#define R return
#define F for
#define U unsigned
#define N int
#define B break
#define I if
#define L(i) for(;i-->0;)
#define J(a,b)  if(a)goto b
#define G goto
#define P printf
#define D double
#define C unsigned char
#define A getchar()
#define O putchar
#define M main
#define Y malloc
#define Z free
#define S sizeof
#define T struct
#define E else
#define Q static
#define X continue
main()
{N  k, a=0, b=0, i;

 F(i=1;i<50;++i)
       P("f(%u)=%u |", i, f(i,i,1,0));
 P("\n");
 F(i=24990;i<=25000;++i)
       P("f(%u)=%u |", i, f(i,i,1,0));
 P("\n");
 R 0;
}

/*
f(1)=0 |f(2)=10 |f(3)=18 |f(4)=23 |f(5)=10 |f(6)=96 |f(7)=103 |f(8)=52 |f(9)=45
f(10)=10 |f(11)=270 |f(12)=253 |f(13)=402 |f(14)=403 |f(15)=630 |f(16)=183 |f(17)=660
f(18)=765 |f(19)=819 |f(20)=95 |f(21)=975 |f(22)=1034 |f(23)=1221 |f(24)=1500
f(25)=96 |f(26)=1479 |f(27)=1197 |f(28)=1658 |f(29)=1953 |f(30)=1305 |f(31)=1674
f(32)=321 |f(33)=816 |f(34)=2490 |f(35)=2704 |f(36)=4235 |f(37)=2022 |f(38)=3242
f(39)=2295 |f(40)=268 |f(41)=2944 |f(42)=3787 |f(43)=3874 |f(44)=4097 |f(45)=1980
f(46)=4380 |f(47)=4968 |f(48)=3424 |f(49)=4854 |
f(24990)=1405098782 |f(24991)=1417995426 |f(24992)=1364392256 |f(24993)=1404501980
f(24994)=1408005544 |f(24995)=1377273489 |f(24996)=1395684561 |f(24997)=1405849947
f(24998)=1406216741 |f(24999)=1142066735 |f(25000)=99984
*/

```

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


title: (2) Can the statues be stacked?

text:
# Question
Title: (2) Can the statues be stacked?
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
Part 2) Can the statues be stacked? (this challenge)

## Challenge 2:

**Input:**

\\$statues\\$: a list of multi-line strings (or character matrices), containing only the characters  `\n|-#` (where the `#` can be another character of your own choice). You're also allowed to take it as a single multi-line string input and parse it into a list yourself.

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

```

**Output:**

Two distinct values of your own choice indicating truthy/falsey; so yes, `1`/`0` is allowed as output in languages like Java/C# .NET and such (relevant forbidden loophole). The output will be truthy if the statues can be stacked.

**How can the statues be stacked?**

When stacking statues, we can only stack statues with a width of the base that is \\$\leq\\$ the width of the top of the statue beneath it. So with the statues above, these are all possible pairs of how we could stack two statues on top of each other:

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

```

One possible complete stack keeping that in mind could therefore be:

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

```

So in this case the result is truthy, since the statues can be stacked.

## Challenge rules:

* You can use a different consistent character other than `#` for the statue border if you want (other than `- \n`). Please state which one you've used in your answer if it's different than `#`.
* You can use any two distinct output values to indicate truthy/falsey respectively.
* You are allowed to take the \\$statues\\$ input in any reasonable format. Can be a single multi-line string, a list/array/stream of multi-line strings, a list of character matrices, 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/newline from one-another, so something like `#|#|` won't be in the input.
* You can assume the statues will only have a base at the bottom side, so a statue like this won't be in the input:

```
--
##
##
--

```
* You can assume all statues will only be placed on top of each other, and never next to each other if the top of a statue is large enough to hold two adjacent statues with small bases, or if it could fit on a smaller ledge. For example, these towers of statues aren't allowed when verifying if the statues can be stacked:

```
                        #
  #                     # #
#--                     - -
####                    ###
----                    ---
Statue on lower ledge   Two statues next to each other on top of single statue

```
* You can assume the top and base parts of a statue are always a single piece, without any gaps. So a statue like this won't be in the input:

```
#  #
----

```

But a statue like this is possible:

```
#
#  #
----

```
* 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:

Truthy test cases:

```
       ####
       ## #
       ## ##
####   #  ##
# ##  ## ###  ##      #
#  #  ## ###  ##  #   #
----  ------  --  -  --
__________________________________________________

  ##
  ##
  ##
####
# #  #
---- -
__________________________________________________

  # #
### #
# # #
--- -
__________________________________________________

###
###
### ## #
--- -- -
__________________________________________________

      #
####  #
# ##  #
###   #         #
##### # ###### ###
----- - ------ ---
__________________________________________________

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

```

Falsey test cases:

```
#
# # ##
--- --
__________________________________________________

     #
     #  #
 ### ## # #
## # ## ### #####
---- -- --- -----
__________________________________________________

     # #
## ### # #
-- --- - -
__________________________________________________

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

```

# Answer
> 2 votes
# Ruby 2.7, ~~83~~ 77 bytes

```
->a{a.map{[_1[/-+/].size,_1[/#+/].size]}.sort.each_cons(2).any?{_2[1]<_1[0]}}

```

Try it online!

Takes an array of string (statues), and outputs the *swapped* boolean values. TIO uses an older version of Ruby, whereas in Ruby 2.7, we've numbered parameters, which saves four bytes.

# Answer
> 2 votes
# Python 3.8, 98 bytes

```
lambda x,Q=sorted:[*sum(Q(s:=[(-len(b),-len(a))for a,*_,b in map(str.split,x)]),())]==Q(sum(s,()))

```

Try it online! The footer converts from the format of testcases in the challenge to a list of multiline statues.

This sorts the pairs `(base_width, top_width)` in descending order and verifies that `top_width` and `base_width` of adjacent pairs are descending by comparing the flattened list with the sorted list of all widths.
The same logic can be found in my 494-byter for the original challenge, which had to deal with rotated and somewhat overlapping statues:

```
Q=sorted
E=enumerate
def f(G):
 s=[];B,S=[{(x,y)for y,r in E(G)for x,v in E(r)if v in e}for e in('-|','#')]
 while B:
  u,U=l,L=x,y=d=min(B);b={d};R=G[y];exec("l-='-'[:l]==R[l-1];u+=R[u+1:]>[]!=R[u+1]=='-';L-='|'[:L]==G[L-1][x];U+=G[U+1:]>[]!=G[U+1][x]>'-';b|={(l,y),(u,y),(x,L),(x,U)};"*len(G+R));B-=b;z=-len(b);h=[]
  while b:b={h.append(abs([x-a,y-p][R[x]<'|']))or(a,p)for a,p in S if any(abs(c-a)+abs(d-p)<2for c,d in b)};S-=b
  s+=(z,-h.count(max(h))),
 return[*sum(Q(s),())]==Q(sum(s,()))

```

Try it online! and an ungolfed version.

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