title: CGCC Rocket Biking

text:
# Question
Title: CGCC Rocket Biking
Something I found while looking through some old files. It seemed like a neat idea for a code golf challenge.

## The intro

One of the most popular events at the annual Cyclist's Grand Competition for Charity (CGCC) is the rocket bike parcours. The rules are simple: Inspect the parcours and place a bet on wheather is it possible to reach and exactly stop on the finish line. The drivers who bet that it's possible then have to prove it to win. If they can't prove it, the drivers who bet against it win.

## The parcours

The rules for the parcours are as follows:

* A parcours consists of uphills, downhills and flat bits. In the examples, it's modelled as a sequence of `/`, `\` and `_` respectively.
* The bike starts with a speed of 0 m/s (i.e. before the first character of the sequence).
* The down-/uphills accelerate/decelerate the bike by 1 m/s.
* On the flat bits the driver must either speed up or slow down manually, again, by 1 m/s. They mustn't do nothing.
* If the bike has a speed of 0 m/s at the finish line (i.e. after the last character of the sequence), the parcours was driven correctly.
* The finish line must be reached.
* The speed must remain \>= 0 at all times. If it is/becomes 0 at any point, the next piece of the parcours must accelerate the bike, either through a downhill `\` or through a flat bit `_` where the driver accelerates.

## The task

Given such a parcours, take it as the input for a first program and output whether it's possible or not to drive the parcours correctly according to the rules above. If yes, take the sequence as an input for a second program and output a sequence of instructions for the driver on what to do on the flat bits. In the examples, `+` and `-` are used to signalize acceleration and deceleration respectively.

## The rules

* This is . The shortest answer wins.
* Submit one or two program/s that validate the parcours (validator) and generate the instructions for the driver if valid (generator). If two programs are submitted, they are scored seperately and independently from the one program submissions.
* The I/O format may be freely chosen. All characters may be substituted freely.
* The generator program only needs to work on parcours that can be driven correctly.
* The input length is not bounded.

## The examples

Input is taken

```
Input:
  \_///

Formatted for clarity:
      /
     /
  \_/

Validator output:
  Falsy (The driver will come to a stop before the last uphill)

```

```
Input:
  \_\__/

Formatted:
  \_
    \__/

Validator output:
  Truthy

Generator output:
  --+

```

```
Input:
  \_\_\

Formatted:
  \_
    \_
      \

Validator output:
  Falsy (The driver will finish the parcours with at least 1 m/s)

```

# More examples:

**Invalid:**

```
/_/\       (Driver can't go uphill with a speed of 0 at the start)

\/_\\/

/\_\//_\

_\/\///_\\

/__//\/_//_\

/_\\\_\/_/__/\_/_\\\\\_\\/\_\//\\\\/\_///\/__\_\_\/_\\\_\//__//_\__/\\___/_\/_/\_\_/\\\\_\_\_\__\_\\

_/_//_\\//\\\/\/_\/\__\\__//\//_\/_\\\___/\\___\_/\_//\\_\\__\/\\_/_//_/__\/_\\/\\___\_\\\\//_/_\\_\\\_\/\___\_//\\/\\\_/_\///__\//\\\/\\/_\\__\_/\\\/_/_/_//_/_/\\//_\/\/_/\\_\\///_/_\\__/_______\/_///_//_/__//__\_//\\/\\\\\_\\\_\//\_\__/\\\/_\\_\/\_\/_\\_/_\_____/\\_\_/_\/_/\/_/\_\/_\_//_\\//__//\//\//\______\//\_//\/_/\\\/_\__\\/__//\\/\\_\\//_/\\_/_//_\\/\\_/\\/\__/\_\_\\_\_\//__\__\\/_\///___\//\\/\__\/\\\\//__//_/_//\__/\\/___/\\\__\/_\__/_/_/\/\//_\\\/\_/_/_\/__\\_\//___///_/_\//__/\___/_\_/_/\_/_\_/\\\\//\\\\_/_\\/\/__\\/_\_/\//\\_\_\_\_\/_\_//\__\\////////\//_//\//\/\\_/_/___/\/\_\/____/____\\\_///_\_\/\__/\//\_/\\/_/_/\\__\\/\\\\///\//__/\_____\__/\__/\\\__/\\_\/\_\__\/_\\/\_\/\/\\\/_\_\__//_\\/\_\/\\\//\//__\_\_\__\__/\/_\_\_\_/_//\\\\_//\/__\\\\\\___/\/\_\\\\___\\_\\\/\_\__/\_/_/__/__/__\\//_____//_//\___\/\/\/\_\__\__\/_/_/\_//__/\\___/_/_\\/\__\\__\__/\_/_/////\\//\//_\\\\\_\\\\_/\/\_/_//\_/////_///_/\/__\\/_/_\_\/_/\_\__\/\\\_\__/__/_//__\\___/\/\//_\/_\\/\/////__\//_\/__////__\\_//_/\__\/_/__\___//\/\/_/\/\//_\___\/\//\///\/__\_/_/___\/\\_\//__\\\__\/\__//_\\__/\_\/\//\/\__//__/_____\\//__/\\\\\\//_/\_///\/_\\\__/_/\__/\\\//\_\\/\\_\///\_\/\__/\//__\\_\/\\__\__\_/__//\/___\\__/_/_/\__//_//_/\/\_//\//__\\__//\/_///\\\/\__/_\_/__/\__\_/\_/_\\//_/\\/__///\_\/_//\_\\____\_\_\/////_\/_/\\\_//_\_\\\\___/____\/\/_\/_////_\__/_/\/\//_/_\_\__\////\///\_/\/_\____\\//\\__\/\/_\_\_\/\/\\\\/\\__\/_\///\__/\/\\_/_//_//\/\/_////\\\__\\/_/\_/\_\//\/_/_/__\//_\/_\//\\\/\/\_/__\\_\_\//__\_\/_/\/\\\\/__\_/\///\__/____\//\///\_\/\_\/__/\\\__\/\\/\/\_//_/_\_\\__/\/\\_/_\__/\/\/\___\\//_/_\\//__\_\\\\/\_\___/__\\//\\/\_\_\/_/\//\/\/__\_/_______/\_\\__\/_/_/_/\_//__\////\/__//__\/\/\///\_//\/\_//\_//\\_///_/_/__\___\/\/__\\\//__/_\_\_\///_\\_\/_/\\__/_/\\/__/_\/_/_\//\\_\\/__\\\\\/__\______\/_//_/\\\/\/\//_\_//\/\\_\\////\_/\_\\\\/__///_/\\___\/\_\//__//_\__\__/\/\\\/\_/\/_\/_/\__\\/_/\__\/\\/_\\_/\/_\/\_\/\\\\_\_/__\/_/\\\_\/\//\_//\//_/\_/////\\\/__///___/\__//_\\_\\\/\\\___/\/\/\___\____/__////\__\______/__/_//_\\\___//_\_\\\/\\/_/\\_\_/__\__//\/_//_///\//__/\//_/_/_/_/\_\____/_//_____///_\___///_\/__\\/\\//\\_\_\_\_//__//\\__\\_\_/_\//\//\/_\_/_\_//\/\_/_\_/\//_///_/_/\\/_/_/_/_\_\//\_\/\/\/////_/__//\/__\//_\_/__\__\_\_/\\_/_//___/__/_/\///\_\/\/\\__\\\__\/\\/\\/\__//\\\/_/\\/\_\/_//___\\_\/////_\/_\_\__/_//\\\/__/_\\\/\/\_\/__\/\_//\/___/_\\/__\\/_/\\\\/\_//_\/_\/\/\__\\_\\\__\\_/_\///_//_\__/_\_/__///_\__\\_/_\/\___\//_\\_/\\/_/\__/\/_/_\\\\\//_//_\\_///\\\/_\\/\\__\\/__/\_\__\/\//\/_\/\/_\\\/\__\___/_/\/_\\////\\_\___\/\_/__/\/\\__//\//_/_/\\\_/\//\//\/\/_/_\\_/\/\//__/\\/\/_/_\//\/\\_/\//__/\/\////\//__/_/\\\_//_///____//_//\_\/_\_\_\\/\\//__///_\__\/_/_\\/\\\\_\_/\\/_\\_//\\/\\/\\/\_\//_\\//__/_\__/\\_\/\/_/__/\\_\\\_/__/\\\_\_/\___\/_\\//__//_//___\/\/___//_\\___\\/_/_\\_/_\__\/_\_//\_\__/_\//___\\\__//_/__\\\\_/\/\__///____\_/\//_/_\_/___//__\\//\/_/\_\_\\_\//_\_/\_/___\___/\/_//\/_\\\\/\\_____/\/_\/_\_\///_\_/\\//__\__//_/\/\\//___///\\///__\__\////_\\/_/_/_\\\__/\_\/_/_//\_\//_//___/\_/_\\_\_\_///___\/_\__/_/\\/\/_/_\__/_\_/_\__///\\\_/\//_\\_/_\\/\///_\/\__\/_///_\____\/_/\\_//\\_\\_\_\\_\/\\\\\\_\///__\/__\_//\\\/\//__\_\\\_/\/_\_\/\/__/_/\_/\/_\_\__\/_\_//_/\/__\_/_/_//_\/\_\\/_\\\//_\_/\\\\\\_\_/\\/_//_/\_/_/\/\\__/_\/\\\\__/\/_/\//////\\\//\___/_\_//__\__/_/_/_//_\_//\///_\\_\//\\/\//_\_\/\_/_///\\\\_\_\\/_/_\\//\/\/_//\//\_/\_/\\_____/_/\/\/\_\__\///\__\/_/_\\\_\_\___//\__/\_/__//\____/\\\_/\\/__\/_///_//\\_//\__\\_/\/_\_/_\_\\///___/_///\//_/___\///\\\\/\/\\/\___/_/__/\/__/_\_/\/_/\__//_//____\/\\\//_\__/__\_///___///_\//_//__////_\//_//\\___/\/\//_\/_\/\\\\_\//_\\___\_\/_\\\//_\\\/\/\//__\\_\\\_\\\\/___/\/_\____/___//_\\\_/\_\_//_/\_\\_/_\\\__\/_//\\/_/\_/\//_/__////______/\/\/\/_//_\\/\______\__/\/__\__////__/\\__\\_\//__//\_\\\/_//\\_\__\\_/\\/_//\\___/_\///_/\__/_/\///\\//__/_/_/_/////\//\_\\__\_\/\//_/_\\//___/__\/\\___\/\_\__/_/____\__\\____/____/\_/\\///\/\_\\/\\\\//__\//\_//\_/\\_\_/_\/\//\\__\\_//\/_\_/\/_\__/\//\__\/___\__\//\/_\__\__\\//_\_/___/\\_/_//\\\/\/__/_//\/_\_/\/_\/_\/_\\\_//\\__/_//\\/\\_\_\\__/\\\//\__\/\//_\_\/_/_/\___\\\/\\_/\/__\_\_\/\\//_\/\//\_/___/_\\\\\\___/\\_\///\/\_///_//_\_/\\__\__\/_//_\_\\\\/_/__\/\/____/\\\\_\\_/\/_\//_\_\//\_////\/_\___///__\/__/_\/\_//_\\_//_\_\///\/_/\__/__\\_\___//_\____/\///_\/_____\/___/\\\///\/_\/_//__/__/\___\/__//\_///\__///_/_\/_/\_/\_\/\/\\/\///_/_/\\__\_\_\\/\//\\\/\\___//__/_\__/_\\\_\//_/_///\/_///_\//\/\_/\\__\/_\/\_\_\\_\_/__\\_\_\_\__\\__/_\//\_//\_\\//\/___\//__\\/__\\\\//_\_\/_/_/_//_\\_//____\\\_/\\_/_\\\/\\\\\___///\/\__\___\__/_/____/\/_/_\_//\_/\_\___/_/\\_/_\\\\___\/\/\\\/\/\_/___\\_\\\\\\_//////_/_\\\\/\\\\/_\\///\/\/\/\/_\_______/_/\/\/\/_\____\\_\_//\_//__\\\\/\\\\//_\\_/__///_____//\\/_/\\____/__//_\_/__\_\/___\\_\\_/___\////_\__\_\_/_\\\/_\_\/\\_\\/_///\\_//_\_\__/_\/_//_\\///_/\\/\/_\/\_/_//\/\\//\///\\///__/\\//_/\/\_/\_/_\/____/\_\_\//_//_\/\____\_/\\__//\____\\\\__//_\_/_/_/_//\_\\\___\\/\\/\\_///\__\\__\_/_/\/\\__\//\/__/\//_\\__\\__\\\\__\/_\/_/___/\_\\/_\/_\\___///\\_/\_/\__/////_/\\_\_\_//\//\_\__\_\__/__\\//\\_/\\/_\/_/_\/_\/__\\_\\__//\_\__/_/\_\/\_/\////////_///__\_/_\/_/\\\_/\/\\\\/_\\//\////___/_\/\/_\/_/_//___/\/_\__//\///_\//\\//\\//\\___/\\_\\/_/_/\\\/\//\\_\///\__//_\\//\\\_/\/\/\//_///__\_/\\\\\/\\/\\\\\__\\\\\__\_/\\__////\_/\_\/___//_/_/\//\_/\_\\\\/_/_\\/\\/_//\_/\/_\\__//_/_//\/\_/\_\\/_\///_//_///_\/\__\__\_/\\\\/__\_///\\\//_\_\_//__\///__/\/_/\_/\___\//_/\/_\/__\_/_\///_\\/\//\/_/\//\/\///\/\__\__/\\_\__\/\_\//_/_/____//\_//_\\\_\/\\/_/\/\\_/\\\_//__\___\//\_\_\/\//\\/\_/\//_\_/\____///\//\/_/\/\_/_/\///___\_\_\//__\_\__\///\\\_\//_\\/_\\\__/\/\___\\/__//_\\_\_\/_\/__/_\_/_\///____\/\_/\\___\/_\_\_/\_/\\_\//\\\_/\/\/__/\/\__/\__/\//\_\\__/_\///_/__\__\\\/_\\_\___////__\____/\_///\/\_\/___\/\\/\/__\____\/__\__\_/\/////___\\/\\//__/\_\_/_\_\_\____\\/\__\\\/\___\\__\__//\\/\//_\/____\\_//_\_\\\\__//_\/\\/_/_/\_\\\____\\__\//_/\_/___\\\____\_\\\/\\//\_//_\_\\___\\//\/__///_\/_///\/_/_/_/_\____/_\_\___/_\\/\____/\\_/_\\/_/\//\_//___/_____/__/\_\_\_///___/\___\\_/\/\\___\__\/\\\\/\\///_/\\/\\\_\\__\_/\/_\_\\\\_///////\/_/\\\\/\/_//\/__/\_/////\_/\\_/\/_/\///\/\\_//\\_\_\/\\\__\\/_\\_\\\__\/_\_/_/\_/\_\_\\\/_\\\_\_\\___\__///___/\__/_///_\_\__/_\__//\_//\_\_\_\_\/_//_/\\\\////_/___\\_____\\___/\/\\_/___\\\/_\____/\__//////\\\/\_\\__\/_/_/\\\/\/\\_\\\/_//\///______\/_\_/__\\\_\\\____\///____\\\\/_/__//__\/\\/_/_\_\_\_\///_\\__/\\_\/_____/\//__\_///_/\\/_\\/\_/\_//\/\////_/\\\\/\/\\\_\/\_//\/\__/\__//_\/\_//\_\\\\\//\\_\\/\_\\/_//\//__/_\\\\\\_/\____\\\__\\_//\/\___/\/\__/____/\/_\/_/_\_/\__\/\/_\//\_\/_\_\\\__\\/_\///___\/\/\__/__////\__/_\//\\\_\/\//\\_\_/\\__\\///_///\\\_\//__\/\_/\///__\\__\_/_//_\_\___///__/\\\\\\_//__\\_//\___/\//_\\_\\/\\/_/\_\\/\/\\/_\\_\_\/\_/\//\__//////__\_\/_\/\\//_\\\\\\\/_\\\/_//\_/\\/\///_\_\_\\/\____/_/\_\\__/\//___/\//\__///_\/____/_//_\///__/_\/_\\_/__/\/__\\\__/_\_/_/\_\\\_/\_\___//_\/_/\__//////\//\_\\\_/__/_/\\/__\\__//\/_/_//_/\/\_\/_/\__/////_/\\\/\\_\_//\\_/___/\\///__\\/\__\/_\\/_\__\/__\_\/\\_/\__\/\___\\__\__//__\//\//_//_\//_\/_/\\_\\_\_/__//\\\//_/\__///\_\/\\////\\__/_/_///\_\/\_/\_//_\///_/____\\_/\/___\/_\\_\//_\_\//\_//__\_/_/__\_\/_/__\\///\\/\\/\/////_/_/_/_///////__//\__/__//\////\_/__\__\//\_\\//\\_/\__\\/\/\/_\\\\/\_\\\/\/___//\/___\__/\\_\\\\_\\_/\/\_\/\////_//_\_/\//\__//__\\\\\//\\\\\__\_\/\_\//\///\/\\_/_/\/_/___/__\___\/_/_/_\_/\_\//\/\____\\_/\\/_\/\__/_______\\_\//____\__//__/___\\//\\////\/\__\__\\___\\_/____\_/_\/\/_\\__////\\\\___/\\/\//_///_/\___/_////\//__/\__\_/_//\//_/\_\\__//\//_////_\_/\_///___//_\//_/\//__/\_/\\_///\\/\\_/_/_\/__/_\\\__\_/\//\\/_\___\_///_/\/____/_\____///\__//__///\_/\\___\_\_/\/\\/\//\_\/_\\/\\_\\/_//\/\_\__\//_\__//\/__/\/\___/\/_\\_/\_/\_\_/\__/_/\\__/_\__\__\_/\\\__\_/_/\\_\\/_//\_/_\/__\__\_\\__//_\\__/_/\/__///_/_\_/\\\__/_\_____\\/_\\\_\\\/_/_/\/___\\_//\_\_//__\\__/\_/////\___\__\/_/_\/_\/\/\\___//_/_\\__/\/\\///\/\___/__/__/\/__\\//_/_\_/_\/___/__//\\__\\\//\/\\\__/_/\/\\_/_\/\/__/\\/__//_/_/\/\///__//\_/\\\__/___\__\/\\/\_/_\\/_\_\/\\////_//\_\_//__\\/\_\\/\\_\/_\_\/__\\__\\\_/_\\/\/_\\\\//\_\_\\///\\/\/\_\\\\__\//_\/__/\/\___\___\\//\\__\__/\/_/\//__\/\/\\\////____///\_\_\\///\/__/_///_\\/__\__/\/__\\\\_\\_\/___\\_///\\_\_\\\\__\_\___///_\/_/\\\\__\\\_/\//\/_//\\\//\\//\/\__\//__\_/__\\\_/__\//__\//_\_/\/\_\/_\/\__/\_/_/_\/\/_\\\/\/_\/____\_\\__\\\\\_///\\\_/\_\//__\__\__//\/_/_/__\_\\\/\__/__\/_\__/\//\/\\\///_\//\/_/\\_____//\\/\\_____/\/_/_/__\\\__/\\_\//\_\_\_/\/\///_\__/\_//_\//_/\\\___\_\_\/_/_/_\_\//\///_\\\/\_\/\/\_/\_/\\/_//_/__//\/\/_\//_//_/_/_////__/_/__//\/\//_//\/_\\\\/\\__\\_\\___/_/__\\_\/__///\/\_/\/_\//__\/_\\/\__/__/_\/\///_/_\\_\_//___/\/_\_/\//_/\_\_\_\/_///_///\\_\//_/\\\/\\_/\/_\//_\__\_\___\_\\\\\/\\//_/\_/\//_\/_\_///_\/\\/___\\_\_\___\/\/\\////_\__/__\_\\/_/__\_\\\/\////\\___\/_\\\\\_/_/_\__\__//_/_\/_\\\__\__\/_\\\_\_\\/_///_/\/\/__///\\_//__\__/____\_//\/\\\\\_/\\/__\\__/\\\\_\/_\\_/_/_//\/\\///\//_/_\///_\/_/\\//\__///\\\_\/////_\\\/_///_/\\/\/_/_/\__\\/_/\_/\\\_\/\//_/\_/\_/\\\\/\/_/\\/////_/_\\\/\\/_\/\\__\_/__//\\_/_\_//_/_\_/\/_\\_\/\//\_/_\___/__\///////_\_/___\\/_\\\\\//_\\__\\/_/_//\__\_/\///_\///\\/_/\\___/\\\\\\///\\/\_\/\_\_/\\\/\//_/\\_///_/_/\_\/\//_//__//////__/\_/___\___/\\___\\/_/\//\\\\\\/\\_/\/\\/_////_\/___\/__\__/\\___\\_//\_\__\\__//\\\/\/___/\//\/\\\\//\//___//\\\///\/_\\_/\_\\\/\/_/__\\\_\_//\__/__\\___\/_///\\\/_/\//\//___/\/\__\\__\////\__/_/_\\_/\/\_/___/\_\\//_/_//\\\_\\\/\_\/\\//\_/__\\_/_\_\\\/_/__\/_\\\\\/__//\_/\//\//\/\/\///_\__\_\/_///__//\/\/_/\//_\\/\//_///___/_\_/\\/__/\\//__\_\__//_//_/_\\//__/_\_\_/_\/_/_//__/___\\\___\______/_/\//\_/_\\\__//\/_//\\\__/\/////_//\_\\/\_/__\/\/__/\\\\\/_\//_\\\__/_\\_\\/\__\\\/_/__/_\//__///\/\_/\_/_//\\_///\_\/_//\/_\\\\\\\\__\_/\///\/_\_\\\//_/\/\\\/__///\_/___\/\\_\/\/_/\/_///___\__/\/___/\///\///_/\\\/_/\_/\\/\_/\_///_/\\\\/_/__/\/\/_//\/\_//\//__\__/__//\\\/\__/\\\_\__/__/_\//_\\_\_\_\\/_\\/\_/\_/__\

```

**Valid:**

```
_\_/
Generator: +-

\\\_//
Generator: -

\/\_\_
Generator: --

_\\__/\/
Generator: +--

\\_\__\/\/
Generator: ---

\\\__\____\/
Generator: +-----

__\\_/\______/\\\_\/\/_///\\_\//\_\/_\_/__/___/__\\_\_//__\\_/___\_______//\/_//__\/\\\__\/__\__/_\/
Generator: ++++++++++++++++++++++-------------------------

_/\_//\_\\//___\\//\/\/_\\_\/\\/\_/__\_//\/\__\/\//\\/\/\\\/\\\_//_\/\_\\\/__/\__/\_/_\\__/___/\__\_////\___\/\\\_//\\_\__/\_/\//\/_\/__\//\\_//\\/\/_/\\/_/\_\/\_/__//__/\//_/\_\__\_\_/\////__///__/////_\/__/\\/\_\\/////_\//_/\\\/\//\\/\_\_////\\_\/\_\//_/_/_\\__\\\\\_//\\_/__//\_/\_\/\_//__//__\_\//\_///_/////__\\/\\/\//_______//_\//_/_/__/\/\/_\/__/\///_\_/\/////\/\__///__////_/\\\_\/\___\\\//\/\_\/\////\_/\___\\_\_/_\\__\\___/_\_///\____/\\\/\_/\/\\\\/_\/\/\\\/\\__///___/___\\_///\_/\///__/_/____\\/___\___\\/\__//_\/\\//\_//\_____/____/\/\_\/_\__/\\\/__/_/_/\__/_/_\\/_///__\\\\/_\//_/__\//\_\//_\/_\\_\/__/_\_\\_\\//_//_\_/_\/\\\\/__/\/___//__/_/\/_\/\//___\/_//\/___\__/\/_\//__\\_\///\\/_\_/_\\//\\_//\\\\\_///_\_/__/\_/_/_\\_\_/\/_//_\\/__\\/\\__//__\__\\\\_/\____\___\//\_\_//_/_/__//_\_/_///__/_/__\/\///\_\/_\_/_\\//\//\//\_/\\/\/\///\/\/\\_\//\__\\//__\_\_\\_\_//_\/_/__/__\_\\\_//\\/__\_\\_/\\_/\_////\/_\_\\__\/_\//_\_\/_/__\\//__\_\\\\/__/_\_\/_\\__///\/\_\/\_/\\_\\/\/_\\\//\/\//\_\/_/_/\//\\\/\\/\\_/__/_///__\\/\_\_//_//\//___/___\_/\/\__/\/_/\\\_\\/__\//\/__\_\//\__\/\__\//__\_/_\\_/____/\/_\/__\_\\_//_\\_\\__/_\/_/\\/\\__\\/__//_\/\/\_\/_/__/\/_\_////\\/_\_/\\\_///___\_/__/\/\__/\\_//_\_\_/\/\_\_/\\\/___//__///___\/_\\/_\\\\/__\//\__\\_\\//\/\____\/__///___//\__/_\__\__\\\\\/_\\\//\/\\//__/__\\//\\/\\\__\\\_\_//__/_/\__\_\_/\/\\\_\\//___\_/\/\___/_/\/_\\_\____/\///\/\\\\_/\/_\\_\//\/\/_/_\_//__\\\_\____\/\\_//\\\\\//_/_\_/\\_\/___\/__\_\_\\\\//__\\__\_/_/_\_\\__\_/\///__\/\/__/\__\_\\\/_//\_\//__\/\\/\\/__/\/\\\/____/_\__\\_/_\\\//__//_/_\\//\/\/\_/\_/\\_\//\__/\\/\\_\_/_/\_/_/_/\\_\_//__\/\__\\/_\////____/\_/\//\\//\_/\/_/////_\_\/\/\\////\/\\_/////_\___\\\\\/___\///__//\\__//_\\/\/_//\\__\\//\\/__\\/_\/_/_\_/\__//\__\\\\_/\/\__//_\//_\\___/_/_/___\/_/_\\\\__\_____///__//_//_//\///\//_//\\_\_\_/\/__/\\/\_\/\_///__//_//_\\///_/_/_/\\_\__\\/\____\__//////__\//_/_\\/__/\////\_/\__///\\/\//__\/__/_/_//\//_/\/__/\_/_//\\/\\___/_\\_/\/\_/_\__\__\/\/_/\__\///__////\__/\__/_\\_////////__\/_/____\/_\\\\/\__\\\_\///__\/////_\//\//_\__\/\\__\\_/\/\\//__\_/_\/\//\_\/\\/\\/\\_\\///\\\__//_\\_\//\__//_\/\_///\\/\/\_\//\/____\\____/_/\/_/\/__\\\_/__\\/_/_/\/\\___////__\\/////\___\\/_\_//_\\/_/\//_/\__\/___\__\/\//\/__\_\\\_\/_\//\/\//\/\\///\///\/\_\\//\_\\/\\\____\\\/__/////_\_\///_\\\\_\__\_____\\_///\//\_//\/\_\\_\\/\__/\\/\\_//_\//\\/\_\\_/__/_\/\\/\_///\/\\/\/__/\_\/\\_/\////___\\//\\_\/\//\//\___//\/_/_/_/__\//_/\\_\_\/_/__///\_\\_\\\\_/______\/\\__\/__/_\_/__\/\\___\_/__//\_\/_/_\\_//\/\_/\__/\\\_\\///\_/\\_/_\/\\/_\/_\\\/_\\\_/_\///\\/__//_\\\__/___\\_/\\_\__\\\//\_/_///\_//\/\/\_\\/\\/__\_____//\\_/\/\/\///\_\__\______\//_\\\\/_/\\/\\//_\\_/\\__/__\\\/\\\_/_/\__\_\//____\\\\//\\_/\\/\\\_\///_//\_//\\\/\__//////_/_\//\\\\__/___///_/_///\\_/_/\_\_\//\/__\__//\//\/\/\__\__\\/_\_\//\_//\\\///\\\/_\\____\\\/__\\_/\//\/\\\/\_//_/_\\\_\///__//\_/_/\__//___//_\//\/_\//\\///\__\__//\//\/\/\___///_//_\/\\_/_/_\//__//_\_\\//\/\_//_/_\/\/__/////\_/__\//\/_/\__/\_\\\/_\_/__\\_/_/\///_/\_/\/__/_/\/\/\\//\///\/\\/__\\_\\/_/_\_/\\//\_\\_\______\\_\_\////_\_/\\__/_/\\\\//_\/\_\\_/\_\__\_\\\\///_/__/\__\_\/\____\__/_//\/_\\/_//\/_//\/_/_\_//_/_///_\\\_//\_\_/__///_/\_/___\___/\_\_/\\//_\/_\/////\\_\//_//_/___\/\\/_//\__\__/___//\___/_\\\/\\_/_/_\\//\/_\\_//_//_/\__/_/_/\_\/_\\\/__\\___\___/_//\/_///\_/__/__\__\\\__/_//\\/_/_/__\\\\_\\_\/_\_\\/_/_/\/\\__\/_/__/\//__//_\_/\\\\_\/_\_//\__/\\_///_/\\\/\\/\_/\_\/\\\//\_/_\\_\\//\//\\//___///\\\//\__\_//_//\/_/\/\/__\\\//\/____/___/\__/\\_\_///\//__/_//_\\\\_////\__\//\_/_/_/\\_/_/\\___/\\\\_\_\///\_//_\_\\\/\/\_/__\//_\\/_////_\\_/\___\/___/__/_//_\\/_\/__/\\/__///\\/\/_\\__\///\//\\\\_\\_\/_\_\//\\/\\/\\//\_\\\__/\\\__/\_\\\_/_\\_/\\__/\\/__\\/\\\/__/\//_\/__\___\//___/_//\_//_///__/_/\\\_/_/\_/\_/__///_/_\_\_/\__/\\__/\//\__\/////_/_\\\\\/__\\\___\/___//__\\/\\_\\\\/_/__\_/\/_//\/\_/\\/\_\\/\\_\\\\/\_/_/\/_//_/__/\\\_///_/\/_\\///_\/\/__\\_//\\/\__//_\\__/_\//\\_\_\__\\/\/\/__/\/_\\\\__////_\/_//\\//_/\\/\__/_\/\__/\//_/\__//_\_\//\_//____\\\\_\/\/___\/\/\/___/__\///\/_\___//\_/\__\\_/___///\//_/__/___//_\/__\\\_\/_\\//\__/\____/_/\\/__\///_/\__\\/_/_/___\/_\__\/_\\/\/\_/\_\/\__\\\//\\\/\_\____/\/_\_/\\/__\\///_\_\\//__\_/__\//\___/\_\_//_/___\_/\\\/\\_\///\/_\\/_\_/_\/_\\\_\___\_\//_//\_\_\_\/_\\/\//_\\/\\__////\\__\___\/_/\_/\___/_\_\_\__/__\//\/_\\___\/\\_/\\_\\/_\\__/__\_/\_\__/\//____\//_____\__/\//_\////\//\//\\//__/__/\\\/_//__/\\\_\//\_/\\\\/___\__//_/\\/__\_/\__\/_\//__\_/___/__/_\///\/__/\_\\__/__\/\_\/\/_/\/\_//_\_\/\__\/_\\/////__/_\_/\_/\_/_\/\\_\\\//\_\\\/\_//\//_\__//\//\\\/_\/\/\/\_/_/_/___/\\/\_\\/\\_/\__\/\//////\_/\////\\__/__\\\_//\_///_//\/\_/\/_/\/__\_\__\//_/_/_\\\/\/_/\\__/\_\_\_\_//\\\//___\__/\___\_____\_/\\/__\\\\\_\/__/\\/\____/\//___/_//\/__////\\//_\/\_/\/\\\/_/__\\/\////_\/\/_\/\___/__/\___//\////\\\_\\\_/\////___/\\\\/\_/_//_/\_/\_/\\/\/_//____///___\/\_\_\\//_/\\\/\___\/_\/_/__\//__/____\/\_/_\_\/\//\\_//\///\_\_\_/\\//\_\\_/_/_\__\_\__\//\\/_\_/\_\/__\\//\\//\///\\/\_/_\_\\_///\///_/\//_/\\//\_\_//_/\/\/\\\\/\/\_\_/\//\_\///__\/\\_\___///_\_\//\_\\/\\/\_\\\/_\/__/__/\/_\\_\/\__/\\\_\_//\/_\\/\_///_\//_\\__/__\_//\\\___\__/___///\/\_\\_/\/\/\\\\/\///\_///////\_/\/\\\_//\//\_//\_//\\///_//\/\_\_\/____/\\_\___\_\\//\/\_///_\\/_//_\/_\\\_\_/_\\//\_////\_\_/\\/_//__\\//\_\/_\///\//_\_/\/\_/___\\//__//__\__/_//__/_/_\\_/_\_//\\_\\\/__///\//_/_//\\/_//__\_\\/\_\_\///__/_\/_\\_/\_\\\/\\\__//_///_/\_///__\/\/\_\_/_\/\_/\/\\\\_\\_//\_\\\///\\\/\__\___\_/\/\_\/\/_//_/_\/\\/\_\/_/_\/_/\\___\/_/_/\____//\\\_/\_/_\/\_/__\\\/\/\\\///_\\\\\\/_\__/\_////_/\/_\///\//_\/_/_/\\\___\\\_\//\_\\\_/____/___/_\_\/____\__//\__//\/_\/__\\/\_\___\\//__////__///__\\\_\_\__//_//\_/_\__\_\_/_//_/\\\\_////////__/\__\/\//\//\\\_/\_/_/\_\\///___\\_////_\_\\__/___\_/\_\\\_/_////_//////\\__\\/_\///__///__\_/_/__/_\\/\\\/\\/__/_\_\\\\/\_/___\\_\//_\_\\/\_\/_\///_\__/\_//\/___\__/\_\__\_/_/\\//\/_//_\\\//////\///_//_/_\_//_/_\\_\/\\_/_\\////_\_____\\/\/\_///_\/_/\//_\/\_\\_//\\__\\_/\/___\/__/\/\___/_\\_///\/\/_/\_/\\\_/___\__//_\__//\\/\__/\\_\/\\_/\_\_/_/_/_\\\////_/_/_//__//\\\_/\//\_/\_/\_\/\\___///__\\\__\\_//_/\__/_\_\\/\_/_/\\\///\\//\____\/\_\/\/_\///_\\//___/___\\_\\//\_\\/_\///___\\//\/\\_/\_\\//\\/\_\_/\\\__/_\_\_/\\\\_\\///_//////___\/\\/\/_\\/\\/\/\\\_\\_//\\_\__/__//\/\//\_/\/_//\/\/\/_//___\_\____\/_/\\/__/__/__\\\_\____\_\/_____\_/_/\\_\\__/\___/\_\////_/_\/\__\////_\\//_///_//\____/\_____\\\//\__//\\\/__//_/\\\__/_//_\/___///_\___///_/__//\_/_\/____\_//_\///_//\\/_\//\___\//\\_\/\_/__\_//\/_/_////\\/_///__/\/\__/_\/\/\//\_//_/_///////_//_\_/_\//\_/\\\_\_\/\\\//\\/__/_\/_/\_\\_/_/_\\////\/\_///\_/\/\\\___\\_\/\\\/_\//\/___/\/\_\_\__\_/\\/____/\/___\/_\_\\_\_/\\\\\\/_\/\\/__\\_//\\\//\\__\_\__/_\_\\\_\__\_/_//\_//__//\//___\/__/_____/\\\_/__/\/\/_//\__\///_\/\_\\\//_//_//\/\_\_/\\\__\/\__//\__\\_/__//_//_/_\\__/__\//\_\/\__/\\\_//\_//_/__\///_///\//\\__///\__\/\//__//\_\\//\_\_\_/\///__\\\\//_/\_\\_//\///\___/___/\/___\\_\\/__/\\\///\_//___/_//\\_\\_/_\//\_//_\___/____\/__/__/_\__\/\/_/\///_///___\_//\_\\\/\\//____//_//\\\/_/\/_\/_\\\/\\\__//\_\\/\\//\/_/\\_/__/\_\\//_/\\\__\/\//\\//\_/__\/__/\_\_/\\_\_//\//_/_\\_/_/___/_\_\\\\\_\_\///_\_/_/\__/_\/\_\_\_/_/_//_/_\_\/_\/_\_//\_//_\//\_\/\_/__/___\\\/\\/_/__\_///_/_///\\\/_///_/\_____\__//\\\_/_\\__/\\\__//_\/_\/_\/__\_\//_\___\/\/\\\__\//_/\\//_//_///\_\\\_///__\\/__\\_/_\/\\\\_/\\\/\\/\_\//_/\/_\/_\/////\\\\//__\_/___\/\_//_\/\_//_\///\\\\_\_\_\_\__\_/__/\/__\\//_\/\_/\_\/\__/\_////\/\/\_/\__/\\//\/_/_/\_/__\_/\/\/\_/_/\_/\\\\_\/////___/_\//_/\/_/\______\_\/___/\\\/\/\/_____/__\_//_\\\\_\//_//_\_\\\_/\/\__//\_/\__/////\__/_/_\/\/\\/_/\_\_\\\/\/\\\\/____\/\\\/__\___/_\\//_///_/_/_\/\\\\\_/\_/\\_/\/\\/___/\___\_\/_\/__\/\///_/_\\_//\_///_\_//__/__\\\\_\__\__//\\/_\//\\\//__\/\____/_\//_/_\\/\\\\\_/\_\//\__/\\_/_\/\\_//\\__/__/___/\/\/___/\\/\/\_/\_\\\_//\_\/__\/\//___/_\/____/\_\_/\\/\/\/\__\_//_/_\//\__\\\//\\/\_\/_\////_////\_/_/__\\\\_\//_\\___\_/\///_/_\\\//\__\\_\_/\/_/_\///_/__\//__\/\\___/\\\\_//_\/_\\\\\_\/_\\//\_\\//___//\\_\_/\/_/\/\/\/__\\\\__/\/_//_////\_//_\___/\/\///\/__//_\\_//_///\\_\/_\\\/\/\\\/_/\_\///___/\\\\\/__\/_\/\__\____//\_\_/_\_\\_/__\\\/\_/\////__\_\/_/_/\__\_\__\/\\\/\\//__\\__\/\/\\__\\\_/\\_\/\___/__\\/\\___\////\\_____\\_/\/_\\//___//_\\\//\_\/_\/\______//__/_\_//__/__//___/\/_\_//\//_/_\//_/\//__\/__///\_\\___/_///\_/\///__/_//\/\_//////_/\\_\\_\/\//\\___\\_///\_\_\/__\_/\/\_/__\___\\/__/\_/\_\__\//\\_\\\/_/__\/_///\//____/_\___\///_//\///_/_/\/\\/\_____\__\\//////\\///__\_//\/_//\/\\////_/_____\\_/\///\\__\/\\_//\//_\//__\/_\____\___/__\/\/___/__\_\\__/\/\__\_\__///_\//\_/__///\/\_/\_/\///_/_/_\___/___/_\_/\_/\//\/\\/_//_\__/\\\_/_/__/\///\//\_\/\\/\_\\/\//_\/\\_/\\\\/\_//__/\/_\/\/_//\\//\//_\_\/\/_/_\//\//\__////\\_\\\_///////_/\/____\\\\/_\\/___/\\\//\\/_//__\//_/__\__\___\/\_/\/\//\__/_\__\_\\//\\_\__//\_/\_\\__\/_\\_\/_\/_/__/___\\//_\_\//_\//\\/\/_//\/\\/__\\\/\///_\_\\_////_/\\__/_\\__/__/_\////\//\___/\\/_\__\_\/_\_\\////_////\/_\_//\_\_\/\_/_/_//\_/\/__\/__\/_//_//\\\\__\//\_/\_\\\\//\\\\_\\\____\\/\_\_/\////\_///\___/___\\\\_\\\//\\\\\\/\_\_\_\/_/_//\\/\___\_____\___\/__\/\\__/\/_\\/__\_/\_\__/_/_/_\/\\____\__/\/_/___\/\____\//_\////\_/__/\_\//\//\_/_//\\/\__\_////_\/_/_\/\/__\__\\///\\\\_\\_\/__\\///_/__/_\\/\\\/\\/\_\_/_\\////\_/\_\/\//_/\/_/\\\\///\_/\\__/_\/\/_\/\_//_//\__\___/\_\/___\/___/_/__\//\_\_\__\\/\/_\_//_\_\\_/___//\//\/\\/\_\/\/_/\_\/__\_\/_\__\/\_\///_/_\\\\/\____/\/\_/_\_//\/\/\//_//\\_\\/_\/\_\\__////\_/__/\/\////_//___\/_\\/_/_\_//\_/\\___\///_\/\\_///__/_\/___////_\__\_\__\\/__\___/_/\\\\\\//\\\/\_\/___//_\\_//_/_/\/\_//_/\\\/_/_\_\/\__/\_/_\/\/\_/_/\/__/\_/\\/_\_/\_/\//___\_____/\/_/\/\_\/\_____\\/___/\\__//\_____\\/\_\//\//__\/_\___\\/\_/_/\/\///\__//__\__/\\__/_\_\/_/_//__\////__\_/_\/_\___/_\/\__/_\\_\\//\/\\/___\___/_/\\\\//\___\\\_/_\_\_/_/\_/\/\___\//__\\\\_/_\////\_/_\/__\\/////_\_\_////_\\///__/\/_\__/\___\//_/_/__//_/\\//_//__\/\__/_\///_/__//\_
Generator: ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

```

The generator output is just an example. It needn't be "ordered" as the one seen above (although I assume this to be more practical to implement).

That last test case may or may not be 10000 chars long and my computer may or may not be trying to find a valid parcours of length 500000 at the moment.

# Answer
> 5 votes
# sed `-E` \- Validator, ~~82~~ ~~61~~ ~~59~~ ~~55~~ 48 bytes

```
:a
s/D(_*)U/\1/
ta
s/_U|D_//
ta
s/__//g
/./cF
cT
```

Attempt This Online!

**Explanation:**

First following transformation is applied on the input: `\___/ -> ___`. This is done repeatedly, till the whole terrain is of following shape: `_/_/___\_\_` \- rising from start and then falling till end.

Then following substrings are removed: `_/` and `\_`. Now the terrain is of flat shape `____` and it is just checked if the number of `_` is even.

# sed `-E` \- Generator, ~~115~~ ~~107~~ ~~78~~ 72 bytes

```
:a
s/D(_*)U/\1/
ta
s/D([^_]*)_/\1M/
s/_([^_]*)U/P\1/
ta
s/_/P/
s/_/M/
ta
```

Attempt This Online!

# Answer
> 4 votes
# Python 3.8 - Validator, ~~92~~ 88 bytes

```
lambda c,d={1}:1in[d:={g+1-a*2for g in d if g for a in(f in'/_',f in'/')}for f in c][-1]

```

Try it online!

# Python 3.8 - Generator, ~~115~~ 113 bytes

```
lambda c,d={1:''}:[d:={g+1-a*2:d[g]+(f=='_')*'+-'[a]for g in d if g for a in(f in'/_',f in'/')}for f in c][-1][1]

```

Try it online!

Thanks to Kevin Cruijssen, Steffan, and xnor for -6 bytes.

# Answer
> 3 votes
# C++ (gcc), 107 bytes (generator and validator)

```
g(char*x,int s=0){return*x?*x-47&&g(x+1,s+1)&&(*x=*x-95?32:43)||*x-92&&s&&g(x+1,s-1)&&(*x=*x-95?32:45):!s;}

```

Try it online!

# C++ (gcc), 71 bytes (only validator)

```
v(char*x,int s=0){return*x?*x-47&&v(x+1,s+1)||*x-92&&s&&v(x+1,s-1):!s;}

```

Try it online!

Note: in both functions 4 bytes could be saved by replacing the boolean ands and or with bitwise ones, but it would be extremely slow. In the generator, the ands before `(*x=*x-95?32:43)` and before `(*x=*x-95?32:45)` must be boolean in any case (otherwise it does not output the correct instructions).

# C++ (gcc), 239 bytes (formatter, extra)

```
#include <cstring>
#include <cstdio>
f(char*x){int*a=new int[strlen(x)+1],i=a[0]=0,m=0,M=0;for(;x[i];++i)a[i+1]=(a[i]+=(x[i]==92))-(x[i]==47),m=a[i]<m?a[i]:m,M=a[i]>M?a[i]:M;for(;m<=M;++m,puts(""))for(i=0;x[i];++i)putchar(a[i]-m?32:x[i]);}

```

Try it online!

# Answer
> 1 votes
# 05AB1E, 32 bytes

```
®1‚„_\Ik©0¢ãʒ0®r.;ηO¤Ā(ªdP}ZÄ=i,

```

Combines the Validator and Generator programs into a single program to save bytes.

Input as a list of characters.
Outputs an empty string as falsey, or `1` as truthy. In addition, outputs all possible generator outputs as a list of lists of `-1`/`1` for deceleration/acceleration respectively.

Try it online or verify (almost) all test cases. (The larger test cases are omitted; the more `_` are in the input, the slower the program becomes because of the `ã`.)

**Explanation:**

```
®1‚          # Push pair [-1,1]
   „_\       # Push string "_\"
      I      # Push the input character-list
       k     # Get the 0-based index of each character in "_\",
             # or -1 if it isn't present (in case of "/")
        ©    # Store this list in variable `®` (without popping)
         0¢  # Count the amount of 0s
           ã # Get the cartesian product of the [-1,1] with this count
             # (resulting in all possible count-sized list of -1s/1s)
ʒ            # Filter this list by:
             #  (implicitly push the current list of -1s/1s
 0           #  Push a 0
  ®          #  Push list `®`
   r         #  Reverse the order of these three
    .;       #  Replace every 0 in list `®` with the -1s/1s of the current list in order
 ηO¤Ā(ªdP    #  Check two things:
             #    1. The sum results in exactly 0
             #    2. No prefix is negative (so we never have any negative m/s speeds)
 η           #   Get the prefixes of this list
  O          #   Sum each inner prefix-list
   ¤         #   Push the last sum (without popping), which is the sum of the full list
    Ā        #   Check if it's NOT 0 (0 if 0; 1 otherwise)
     (       #   Negate it (0 if 0; -1 otherwise)
      ª      #   Append it to the list
       d     #   Check for each inner integer if it's non-negative (>= 0)
        P    #   Check if this is truthy for all of them
}            # Close the filter
             # (we now have a list of all possible paths if truthy; or [] if falsey)
 Z           # Push the flattened maximum (without popping): 1/-1 for truthy; "" for falsey
  Ä          # Get its absolute value: 1 for truthy; "" for falsey
   =         # Output it with trailing newline (without popping)
    i        # And if it was 1:
     ,       #  Also output the list itself on another line

```

# Answer
> 1 votes
# x86-64 machine code, 45 bytes (validator and generator)

```
31 D2 6A 01 59 AC 88 C4 B0 2B 9E 7B 13 73 07 FF CA 79 05 AA FF C2 FF C2 9E 75 03 83 C1 02 E2 E5 D1 E9 B0 2D F3 AA 88 0F 19 CA 19 C0 C3

```

Try it online!

Following the standard calling convention for Unix-like systems (from the System V AMD64 ABI), this takes in RSI the address of the input, as a null-terminated byte string; takes in RDI an address at which to place a string, which will be the instructions for the driver if it's possible; and returns in EAX −1 if possible and 0 if impossible.

In assembly:

```
f:
    xor edx, edx

```

Set EDX to 0. EDX will keep track of the minimum possible speed at each point.

```
    push 1; pop rcx

```

Set ECX to 1. ECX will keep track of the maximum possible speed plus 1 at each point.

```
repeat:
    lodsb
    mov ah, al

```

Load a character from the string into AL, advancing the pointer, and then move it into AH.

```
    mov al, '+'

```

Set AL to the ASCII code of '+'.

```
    sahf

```

Set flags based on the character in AH. Here are the possibilities, with the important bits bolded:

```
    S**Z** A **P** **C**
NUL 0**0**100**0**0**0**
\   0**1**011**1**0**0**
_   0**1**011**1**1**1**
/   0**0**101**1**1**1**
```

```
    jnp done

```

Jump if PF=0, true here only for the null terminator.

```
    jnc must_accel

```

Jump if CF=0, true here only for `\`.

```
    dec edx
    jns second_part

```

(For `_` and `/`) Subtract 1 from EDX (the minimum speed). Jump if the result is nonnegative, in which case we are done with this part. Otherwise...

```
    stosb

```

Write `+` to the output string, advancing the pointer.

```
    inc edx

```

Add 1 to EDX. The next instruction adds 1 more, for a net +1.

```
must_accel:
    inc edx

```

(For `\`) Add 1 to EDX.

```
second_part:
    sahf

```

Set flags based on the character in AH again (as the `inc` or `dec` has overwritten them).

```
    jnz must_decel

```

Jump if ZF=0, true here only for `/`.

```
    add ecx, 2

```

(For `_` and `\`) Add 2 to ECX (the maximum speed plus 1); the next instruction will subtract 1, for a net +1.

```
must_decel:
    loop repeat

```

(`/` jumps here) Subtract 1 from ECX and jump back if the result is nonzero (if the maximum speed did not drop to −1).

```
done:

```

If the parcours is possible, the minimum speed is 0, and the maximum speed is 2 times the number of flat pieces that should be decelerated on (because the maximum speed is obtained by accelerating on all of them, and changing one acceleration to a deceleration reduces the final speed by 2).

If it's not possible, either the end of the string has been reached with a nonzero minimum speed, or the loop ended prematurely with the maximum speed becoming −1 from a `/`, in which case the minimum speed will have changed from 0 to 1 on that `/`, and thus will also be nonzero.

```
    shr ecx, 1

```

Shift ECX (the maximum speed plus 1) right by 1 bit. If the parcours is possible, this produces the number of flat pieces that should be decelerated on.

```
    mov al, '-'
    rep stosb

```

Put the character code of `-` in AL and write it to the output string ECX times, advancing the pointer and counting down ECX.

```
    mov [rdi], cl

```

Add the low byte of ECX, which is now 0, to the output string.

```
    sbb edx, ecx

```

Subtract ECX+CF from EDX. ECX is still 0. CF is the bit shifted out of ECX previously.

If the parcours is possible, CF will be 1 and EDX 0, so the result will wrap around to all 1s, and CF will be 1 afterwards.

If it's not possible, EDX will be nonzero and CF may be 0 or 1, but either way the result will not wrap around, so CF will be 0 afterwards.

```
    sbb eax, eax

```

Subtract EAX+CF from EAX, making it −CF: −1 if possible and 0 if impossible.

```
    ret

```

Return.

# Answer
> 1 votes
# brainfuck, 124 bytes (validator and generator)

```
,[------->-[<->---]+<[---[>->+>->>+<[->-]>[.->]<<<<<<[-]]>[->+>+<<]<[-]]>[->->+>+<<<]<,]--[>+<++++++]>>[--<.>]<++>>[--<<.>>]

```

If the parcour is valid, it just outputs the instructions; otherwise, it prints one or more bytes of value `0x01`, followed by some instructions (which are of course meaningless).

Try it online!

Note: it works only if the difference in height is always less or equal to `255`, counting from the start.

# brainfuck, 103 bytes (generator only)

```
,[------->-[<->---]+<[---[>->+>-<<<[-]]>[->+>+<<]<[-]]>[->->+<<]<,]--[>+<++++++]>>[--<.>]<++>>[--<<.>>]

```

Try it online!

Note: for both programs, the input must be zero terminated. Both programs works only if the total number of `+` and `-` of the output is less than `128`.

# Answer
> 1 votes
# Python, 62 (generator) + 68 (validator) bytes

## -1 @Steffan

```
(
lambda s:((l:=len(s)//2)-(c:=s.count)("A"))*"+"+(l-c("?"))*"-"
,
lambda s,i=1:[min(i:=i+ord(c)%z-1for c in"?"+s)for z in(7,9)]==[0,i]
)
```

Attempt This Online!

Takes "AH?" for "\\\_/" to save a few bytes

# Answer
> 0 votes
# Retina 0.8.2, 104 bytes

```
+`^(((?<-3>-|/)|(\+|\\))*)((?<8-3>)|((?<3>)))_(((?<-3>_|/)|(?<3>_|\\))*)$(?(3)^)
$1$#5$*+$#8$*-$6
[^-+]

```

Try it online! Link includes faster test cases. Outputs nothing if there are no flat bits or the input is invalid. Explanation:

```
+`

```

Repeat until all the instructions have been generated.

```
^(((?<-3>-|/)|(\+|\\))*)

```

Start by matching either `-` or `/` (removing from capture group `3` captured in a previous iteration), or either `+` or `\` (capturing into capture group `3`), repeating as much as possible, into capture group `1`.

```
((?<8-3>)|((?<3>)))

```

Either remove from capture group `3` and capture into group `8` or make another capture into capture group `3` and also capture group `5`. Then match the flat bit that we're going to create an instruction for, depending on which option was taken.

```
_(((?<-3>_|/)|(?<3>_|\\))*)

```

Match `_` or `/` (still removing from capture group 3) or `_` or `\` (still capturing into capture group 3) as much as possible into capture group `6`.

```
$(?(3)^)

```

The match needs to reach the end of the string and all of the captures in group 3 must eventually have been removed.

```
$1$#5$*+$#8$*-$6

```

Replace the flat bit with the desired instruction, leaving the prefix and suffix unchanged.

```
[^-+]

```

Remove anything that isn't an instruction.

Validator only for 29 bytes:

```
^((?<-2>_|/)|(_|\\))*$(?(2)^)

```

Try it online! Link includes faster test cases. Explanation: Basically just the last part of the expression from the full program above, treated as a logical match/fail result.

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


title: Seeing the queen's lasers

text:
# Question
Title: Seeing the queen's lasers
In chess, the queen piece can move arbitrarily far in each cardinal and intercardinal direction. What does this mean? Well, I'll show you with an ASCII drawing:

```
\..|../
.\.|./.
..\|/..
---Q---
../|\..
./.|.\.
/..|..\

```

It means the queen (notated as `Q`) can move along these lines (notated as `\`, `|`, `/`, and `-`), and cannot reach the other spaces (notated as `.`). The `|`s extend from the queen vertically, the `-`s horizontally, and the `\/`s diagonally.

However, I've quickly lost interest in chess and am more fixated on the diagram itself;

How many different symbols are contained within the 3x3 region centered on any given square? One way to visualize this would be to replace the symbols with this value, shown below:

```
2232322
2234322
3356533
2465642
3356533
2234322
2232322

```

Why? Well, for example:

The queen square has value 5 because the 3x3 region centered on the queen looks like this:

```
\|/
-Q-
/|\

```

Where we can see 5 distinct symbols: `\|/-Q`.

The top left square has value 2 because the 3x3 region around that square looks like this:

```

 \.
 .\

```

Where we can see 2 distinct symbols: `\.`. Anything beyond the board is not a symbol, so those space characters I've included for visualization purposes don't count.

## Challenge:

Given the queen's position on an MxN board, output the number of unique symbols contained within the 3x3 region around each square, based on the queen movement diagram which would be generated. This is , so shortest wins :)

## Rules:

* Standard I/O rules apply, any format to represent the grid size and the queen's position is fine in whatever order / format, and output can be plain text or a list of strings or whatever.
* Since any given cell can only see up to 6 different symbols, digits on a line do not need to be delimited in any way. Lines, however, must be clearly delimited, as the board is not necessarily square.
* 0 indexing is allowed.
* Input will always be valid; Board will always be at least 1 unit wide and at least 1 unit tall, and the queen's position will always be on the board.

## Examples:

Formatted as

```
(board width, board height) (queen x, queen y)
image of board

output

```

Queen x and queen y given as 1 indexed, x being leftmost and y being topmost, output being 1 indexed as well. Your I/O format may differ from this.

Note that your program does not need to use the symbols `Q\|/-.`, nor does it need to generate an image of the board at all. Only the number grid should be output.

```
(1, 1) (1, 1)
Q

1

(3, 3) (2, 2)
\|/
-Q-
/|\

454
555
454

(6, 3) (2, 2)
\|/...
-Q----
/|\...

455322
556422
455322

(2, 7) (1, 5)
|.
|.
|.
|/
Q-
|\
|.

22
22
33
55
55
55
33

(7, 2) (5, 1)
----Q--
.../|\.

2235553
2235553

(10, 10) (10, 10)
\........|
.\.......|
..\......|
...\.....|
....\....|
.....\...|
......\..|
.......\.|
........\|
---------Q

2221111122
2222111122
2222211122
1222221122
1122222122
1112222222
1111222232
1111122233
2222223355
2222222354

(7, 7) (4, 4)
\..|../
.\.|./.
..\|/..
---Q---
../|\..
./.|.\.
/..|..\

2232322
2234322
3356533
2465642
3356533
2234322
2232322

```

# Answer
# MATL, ~~52~~ ~~49~~ ~~48~~ 45 bytes

```
9,i:i-]!=E2M+~+4KGY(3HGZ(3M*+^4Y6Z+9_YA!gsIGe

```

Input order is: board width, queen x, board height, queen y.

Try it online! Or verify all test cases.

The code first generates the board using the numbers 1, 9, …, 59049 (first six powers of 9) instead of the symbols `.`, `/`, …, `Q`. Then 2-dimensional convolution with a 3×3 matrix containing ones is performed. This gives the sum of the 3×3 block centered in each cell. The desired result is the number of non-zero digits in the base-9 expansion of the sum for each cell.

Base 9 is sufficient (rather than base 10) because if the same character (`.`) appears 9 times in a 3×3 block the base-9 expansion will contain, due to carry, a digit 1 and the rest 0 (instead of a digit 9 and the rest 0 if base 10 were used), but the final result is 1 anyway.
> 10 votes

# Answer
# Charcoal, 61 bytes

```
ＮθＮηＵＯθη.ＪＮＮＰ*⁺θηQＪ⁰¦⁰ＴθηＦηＦθ«Ｊκι≔⊞ＯＫＭＫＫδ⊞υΣＥδ∧Ｌλ⁼μ⌕δλ»⎚⪪⪫υωθ

```

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

```
ＮθＮηＵＯθη.

```

Input the dimensions of the board and draw it.

```
ＪＮＮＰ*⁺θηQ

```

Draw the Queen's lasers and then the Queen herself.

```
Ｊ⁰¦⁰Ｔθη

```

Trim the lasers to size.

```
ＦηＦθ«

```

Loop over each square.

```
Ｊκι≔⊞ＯＫＭＫＫδ

```

Get the cell and its eight neighbours.

```
⊞υΣＥδ∧Ｌλ⁼μ⌕δλ

```

Save the count of distinct nontrivial neighbours.

```
»⎚⪪⪫υωθ

```

Clear the canvas and output the counts.
> 6 votes

# Answer
# APL(Dyalog Unicode), 52 bytes SBCS

```
{2 2↓{≢∪0~⍨,⍵}⌺3 3⊢(-2+⍵)↑2+(≠⍥|⊃×⍥×,2+,⍳=)/¨⍺∘-¨⍳⍵}

```

Try it on APLgolf!

Takes 0-indexed `qy qx` as left argument, and `height width` as the right argument.
Actually drawing the ascii art is a bit simpler (can be seen in the footer).
> 4 votes

# Answer
# Python 3, 149 bytes

```
lambda w,h,x,y:[[len({(I==J,I==-J,I==0,J==0)for I in[i-1,i,i+1]for J in[j-1,j,j+1]if~x<I<w-x>~y<J<h-y})for i in range(-x,w-x)]for j in range(-y,h-y)]

```

Try it online!

The position of queen is 0-indexed.

Maybe someone may golf many bytes from it, but I'm not sure how to do that.
> 3 votes

# Answer
# Python3, 468 bytes

```
R=range
U=lambda b,x,y:-1<x<len(b)>-1<y<len(b[0])
def V(b,m,x,y):
 if r:=U(b,x,y)==1>b[x][y]:b[x][y]=m
 return r
def l(x,y,Q):
 b=eval('[0]*y,'*x);b[Q[0]][Q[1]]=5;B=eval(str(b));q=[(6,*Q,1,0),(7,*Q,0,1),(8,*Q,-1,1),(9,*Q,1,1)]
 while q:m,x,y,X,Y=q.pop(0);q+=[(m,x+i*X,y+i*Y,X,Y)for i in[-1,1]if V(b,m,x+i*X,y+i*Y)]
 return b,B
def f(X,Y,Q):
 b,B=l(X,Y,Q)
 for x in R(X):
  for y in R(Y):B[x][y]=len({b[J][K]for J in R(x-1,x+2)for K in R(y-1,y+2)if U(B,J,K)})
 return B

```

Try it online!
> 2 votes

# Answer
# 05AB1E, ~~69~~ 68 bytes

```
θDI¹->©н‚ß®W.ý`D¹н‚ß¹н¹ß)vyN4%N8«.Λ}1A0.ΛS¶¡¶δ.ø¬g¶иšĆ2Fø€ü3}εε˜¶KÙg

```

Inputs as two loose pairs, in the order `[queen x,queen y]`, `[board width,board height]`.

Try it online or verify all test cases.

**Explanation:**

(let's call the inputs `[x,y]` and `[w,h]` in the explanation below)

*Step 1:* Use the Canvas builtin to draw the shape (with `0123a` instead of `|/-\Q`):

```
θ             # Push the last item of the first (implicit) input: y
D             # Duplicate it
 I            # Push the second input [w,h]
  ¹-          # Subtract the first input: [w-x,h-y]
    >         # Increase each by 1: [w-x+1,h-y+1]
     ©        # Store this in variable `®` (without popping)
      н       # Pop and push its first item: w-x+1
       ‚      # Pair it with the duplicated y
        ß     # Pop the pair, and push its minimum: min(y,w-x+1)
®             # Push pair `®` again: [w-x+1,h-y+1]
 W            # Push its minimum (without popping): min(w-x+1,h-y+1)
  .ý          # Add it to the middle of the pair: [w-x+1,min(w-x+1,h-y+1),h-y+1]
    `         # Pop the triplet and push all three separated to the stack
D             # Duplicate the top h-y+1
 ¹н           # Push the first item of the first input: x
   ‚          # Pair them together: [h-y+1,x]
    ß         # Pop and push the minimum: min(h-y+1,x)
¹н            # Push the first item of the first input: x
¹ß            # Push the minimum of the first input: min(x,y)
)             # Wrap all eight values on the stack into a list
v             # For-each over these values:
 y            #  Push the current value
  N           #  Push the 0-based loop-index
   4%         #  Modulo-4
     N        #  Push the 0-based loop-index again
      8«      #  Append an 8
        .Λ    #  Use the (modifiable) Canvas builtin with these three options
}             # Close the loop
    .Λ        # Use the (modifiable) Canvas builtin again with the options:
 1A0          #  1,"abcdefghijklmnopqrstuvwxyz",0

```

See this 05AB1E tip of mine for an in-depth explanation of the Canvas builtin. But in short, these are the steps it does:

1. Draw \\$y\\$ amount of `'0'` in direction ↑ (`0`), then reset back to the origin with 'direction' `8`.
2. Draw \\$\min(y,w-x+1)\\$ amount of `'1'` in direction ↗ (`1`), and reset back to the origin again with `8`.
3. Draw \\$w-x+1\\$ amount of `'2'` in direction → (`2`), and reset back to the origin again with `8`.
4. Draw \\$\min(w-x+1,h-y+1)\\$ amount of `'3'` in direction ↘ (`3`), and reset back to the origin again with `8`.
5. Draw \\$h-y+1\\$ amount of `'0'` in direction ↓ (`4`), and reset back to the origin again with `8`.
6. Draw \\$\min(h-y+1,x)\\$ amount of `'1'` in direction ↙ (`5`), and reset back to the origin again with `8`.
7. Draw \\$x\\$ amount of `'2'` in direction ← (`6`), and reset back to the origin again with `8`.
8. Draw \\$\min(x,y)\\$ amount of `'3'` in direction ↖ (`7`), and reset back to the origin again with `8`.
9. Draw \\$1\\$ character from string `"abcdefghijklmnopqrstuvwxyz"` (thus `'a'`) in direction ↑ (`0`).

Try just step 1 online.

*Step 2:* Add a no-op border (of newline characters) like a painting frame, and then get all overlapping 3x3 blocks:

```
S             # Convert it to a list of flattened characters
 ¶¡           # Split on newlines
    δ         # Map over each row of characters:
   ¶ .ø       #  Surround it with a leading/trailing newline character
       ¬      # Push the first line (without popping the matrix)
        g     # Pop and push its length
          и   # Create a list of that many
         ¶    # newline characters
           š  # Prepend it as first row
            Ć # Enclose; appending its own head
2F            # Loop 2 times:
  ø           #  Zip/transpose; swapping rows/columns
   €          #  Map over each row:
    ü3        #   Convert it to a list of overlapping triplets
}             # Close the loop

```

Try just the first two steps online.

*Step 3:* Remove all painting-frame newline characters, and count how many unique characters each 3x3 block contains, which is our resulting matrix:

```
εε            # Nested map over each 3x3 block:
  ˜           #   Flatten it to a list of characters
   ¶K         #   Remove all newline characters
     Ù        #   Uniquify it
      g       #   Pop and push its length
              # (after which the resulting matrix is output implicitly as result)

```
> 2 votes

# Answer
# JavaScript (ES10), 153 bytes

The position is 0-indexed. The method is similar to the one used by @tsh.

```
(w,h,x,y)=>(F=X=>Y<h?new Set([-!!X++,0,X<w].flatMap(p=>[-!!Y,0,Y<h-1].map(q=>[(H=X+~x+p)==(q+=Y-y),H==-q]+!H+!q))).size+[`
`[X-w]]+F(X<w?X:!++Y):'')(Y=0)

```

Try it online!
> 1 votes

# Answer
# PARI/GP, 109 bytes

```
f(w,h,x,y)=matrix(h,w,i,j,#Set([[k-y==s=l-x,s==t=y-k,!s,!t]|n<-[0..8],(k=i-n%3)>=0&&k<h&&(l=j-n\3)>=0&&l<w]))
```

Attempt This Online!

A port of @tsh's Python answer. The position is 0-indexed.
> 0 votes

---
Tags: code-golf, grid, chess
---


title: Rotatable numbers (Upside down)

text:
# Question
Title: Rotatable numbers (Upside down)
# Searching for *rotatable numbers*, like: *`68089`*

If you consider numbers upside-down,

* `6` looks like `9`,
* `8` looks like `8`,
* `9` looks like `6` and
* `0` looks like `0`.

The others digits (`1`, `2`, `3`, `4`, `5` and `7` ) look like nothing...

I wonder how many number could be *rotatable* between 0 and 1000! The answer is definitively **11**: `0`, `8`, `69`, `88`, `96`, `609`, `689`, `808`, `888`, `906` and `986`

Well I imagine a tool able to display all *rotatable numbers*, between two boundaries...

The tool may be run in any way you want, whith two boundaries as argument or standard input. Then must return all *rotatable numbers* between this two boundaries.

### About duplicate

If the other question: Numbers with Rotational Symmetry look something similar, they are **not!!**: **1)** Not same bunch of digits, **2)** not same behaviour and **3)** search in between two boundaries...

And as Jonathan Allan's comment pointed out. Not same question, not same ways for reaching answer. Here are other interesting way for doing this!!

### Sample:

Input:

```
0 1000

```

Output:

```
0 8 69 88 96 609 689 808 888 906 986

```

Or input:

```
8000 80000

```

Output:

```
8008 8698 8888 8968 9006 9696 9886 9966 60009 60809 66099 66899 68089 68889 69069 69869

```
* No matter on output format (on one or multiple lines).
* Only numbers must be accepted.
* Of course, except `0` himself, a number could not begin by `0`.
* This is , so shorter answer (in bytes) win!

#### Leaderboard

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

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

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

# Answer
> 5 votes
# Jelly, 15 bytes

Seems a little longer than I imagine is possible

```
rD‘×Ṛ$fƑʋƇ“¢FQ‘

```

A dyadic Link that accepts the two bounds and yields the rotatable numbers

**Try it online!**

### How?

Identifies rotatable mirrored pairs of digits by adding one to each and multiplying them together. The only results which are any of \\$1\\$, \\$70\\$, or \\$81\\$ are the valid pairs:

| (Digit+1)(Mirror+1) | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
| 0 | **1** | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
| 1 | 2 | 4 | 6 | 8 | 10 | 12 | 14 | 16 | 18 | 20 |
| 2 | 3 | 6 | 9 | 12 | 15 | 18 | 21 | 24 | 27 | 30 |
| 3 | 4 | 8 | 12 | 16 | 20 | 24 | 28 | 32 | 36 | 40 |
| 4 | 5 | 10 | 15 | 20 | 25 | 30 | 35 | 40 | 45 | 50 |
| 5 | 6 | 12 | 18 | 24 | 30 | 36 | 42 | 48 | 54 | 60 |
| 6 | 7 | 14 | 21 | 28 | 35 | 42 | 49 | 56 | 63 | **70** |
| 7 | 8 | 16 | 24 | 32 | 40 | 48 | 56 | 64 | 72 | 80 |
| 8 | 9 | 18 | 27 | 36 | 45 | 54 | 63 | 72 | **81** | 90 |
| 9 | 10 | 20 | 30 | 40 | 50 | 60 | **70** | 80 | 90 | 100 |

```
rD‘×Ṛ$fƑʋƇ“¢FQ‘ - Link: integer, A; integer B
r               - inclusive range -> [A..B]
          “¢FQ‘ - list of code page indices -> [1,70,81]
         Ƈ      - keep those of [A..B] for which:
        ʋ       -   last four links as a dyad - f(N, M=[1,70,81]):
 D              -     to decimal digits   e.g. N=6089 -> [ 6, 0, 8, 9]
  ‘             -     increment                          [ 7, 1, 9,10]
     $          -     last two links as a monad:
    Ṛ           -       reverse                          [10, 9, 1, 7]
   ×            -       multiply (vectorises)            [70, 9, 9,70]
       Ƒ        -     is invariant under?:
      f         -       filter keep if in M              [70, 70] -> nope

```

---

We could shift down by four instead of up by one before multiplying and then only the valid pairs will give \\$10\\$ or \\$16\\$ but I think it's the same byte count:

```
rD_4×Ṛ$fƑʋƇ“½Ñ‘

```

# Answer
> 4 votes
# Vyxal, 15 bytes

```
ṡ'»ƛ∪&»FS‛69*Ṙ=

```

Try it Online!

Takes `end boundary` then `start boundary`

## Explained

```
ṡ'»ƛ∪&»FS‛69*Ṙ=
ṡ'               # From the range(start, end + 1), keep only items where:
  »ƛ∪&»FS        #  Removing the numbers 1, 2, 3, 4, 5 and 7
         ‛69*    #  Ring translated by the string 69 (6 becomes 9 and 9 becomes 6)
             Ṙ=  #  And reversed equals the original item

```

# Answer
> 4 votes
# Factor \+ `flip-text`, 57 bytes

```
[ [a,b] [ unparse dup flip-text "5"""replace = ] filter ]

```

Attempt This Online!

Factor's ᵷuᴉddᴉʃɟ-ʇxǝʇ vocabulary considers 5 to be the same as itself when upside down, so I had to remove the 5's before checking for equality.

# Answer
> 3 votes
# Raku, 53 bytes

```
{grep {.trans(~6890123457=>~9860):d eq .flip},$^a..$^b}

```

Try it online!

Treats the number as a string, transliterates the rotatable numbers to their counterparts and deletes the rest, and tests that that string is equal to the reverse of the input string.

# Answer
> 3 votes
# Regex (ECMAScript or better) `m`, ~~165~~ ~~159~~ ~~164~~ 152 bytes

```
(?=((x{8}$|(?=.*?(?=(((x*)\5{8}(?=\5$))+x$))(x*)\6{99})(?=(\3x)(?:\7{5}(\7\7|\3{3}|xxx))(?!\3)(x*)\9{9}$)(?=(x*(?=\6|$))(|\6{6}x{9})\9$)\10)*$)
(?!x\1))

```

Try it online!

Takes its input in unary, as the lengths of two strings of `x`s delimited by a newline (high end of range first, then low end of range). Returns its result as the list of matches' `\1` captures (each is also a string of `x`s whose length is the value).

This is adapted from my solution to Numbers with Rotational Symmetry, which is a version of this, with `1` also treated as a rotationally-symmetric numeral. As described in that post, it's impossible for ECMAScript regex to match this sequence in decimal (it can't even match `a`n`b`n), but it's possible in unary.

The `m`ultiline flag is used so that `$`, which occurs many times in the regex, can be used instead of `\b` or `(?=¶)`, where  is the delimiter (which needs to be a newline to take advantage of this `m` flag trick, but could be any non-word-character otherwise).

The regex works by looping the following logic:

1. Carve away both the leading and trailing digit if they are an allowed pair, or (for single-digit values) an allowed single digit.
2. Prevent the value sent to the next iteration from having any leading zeroes, since the regex operates on numbers, not strings, so any leading zeroes would be stripped. If it has a leading zero, add \\$6\\$ to the leading digit and \\$9\\$ to the trailing digit. If both were zero, meaning that inward up to that point, the input is symmetric, the modified number will now have a \\$6\\$ on the left and a \\$9\\$ on the right, preserving the trait of symmetry. If the trailing digit was nonzero (meaning the input is not a rotationally symmetric number), adding one of \\$69, 609, 6009, ...\\$ is guaranteed not to change it to one that is symmetric, because for example \\$6009\\$ could only be added to any number in the range \\$0001\\$ to \\$0999\\$ with a nonzero last digit, which can only yield a number in the range \\$6010\\$ to \\$7008\\$ with a last digit other than \\$9\\$, none of which are rotationally symmetric. This allows us to golf off 13 bytes, due to not needing the trailing zero check `(?=(x{10})*$)`. (This would not work with adding one of \\$88, 808, 8008, ...\\$ even though `(\6x){8}` is shorter than `\6{6}x{9}`, because \\$88+8=96\\$, \\$808+098=906\\$, \\$8008+0998=9006\\$, etc.)

```
(?=                          # Wrap the entire test in a lookahead so that after
                             # matching, the position will only advance one
                             # character forward for the next test.
    (                        # \1 = tail = the number to be tested
        (
            x{8}$                # If tail==8, let tail=0 and end the loop
        |
            # Assert tail >= 10; find \3 = the largest power of 10 that is <= tail
            (?=
                .*?              # Decrease tail by the minimum necessary to satisfy
                                 # the following assertion:
                (?=
                    # Assert tail is a power of 10 >= 10; \3 = tail
                    (((x*)\5{8}(?=\5$))+x$)
                )
                (x*)\6{99}       # \6 = floor(tail / 100)
            )

            # Require tail is of the form 8.*8, 6.*9, or 9.*6
            (?=
                (\3x)            # \7 = \3 + 1
                (?:
                    \7{5}
                    (
                        \7\7     # 8.*8
                    |
                        \3{3}    # 9.*6
                    |
                        xxx      # 6.*9
                    )
                )
                (?!\3)
                (x*)\9{9}$       # Assert tail is divisible by 10;
                                 # \9 = tail / 10 == floor((N % \3) / 10)
            )

            # Set tail = \9, but if \9 is of the form 0.*0, the next iteration would
            # not be able to see its leading zero, so change it to the form 6.*9 in
            # that case, otherwise leave it unchanged. If \9 is of the form 0.*[1-9],
            # don't go to the next iteration.
            (?=
                (                # \10 = tool to make tail = \9 or \9 + \6*6 + 9
                    x*
                    # Assert that the leading digit of tail is not 0, unless tail==0
                    (?=
                        \6       # Assert that the leading digit of tail is not 0
                    |            # or
                        $        # Assert that tail==0
                    )
                )
                # Iff necessary to satisfy the above, tail += \6*6 + 9
                (
                |
                    \6{6}x{9}
                )
                \9$              # tail = \9
            )
            \10                  # tail = \9 or \9 + \6*6 + 9
        )*                       # Execute the above loop as many times as possible,
                                 # with a minimum of zero iterations.
        $                        # Assert tail==0
    )
    ¶                        # tail = low end of range
    (?!x\1)                  # Assert \1 ≥ tail
)

```

# Regex (ECMAScript 2018 or better), ~~173~~ ~~167~~ ~~172~~ 160 bytes

`(?=((x{8}$|(?=.*?(?=(((x*)\5{8}(?=\5$))+x$))(x*)\6{99})(?=(\3x)(?:\7{5}(\7\7|\3{3}|xxx))(?!\3)(x*)\9{9}$)(?=(x*(?=\6|$))(|\6{6}x{9})\9$)\10)*$)(?<=(?<!x\1),.*))`

Attempt This Online!

Takes its input in order of {low end of range, high end of range}, with a comma delimiter. Otherwise the same as the above.

("ECMAScript 2018 or better" includes just two other engines: .NET and Python`regex`, but I haven't made test harnesses in them for this type of regex yet.)

The part of this regex that differs from the one above:

```
(?=
    (                        # \1 = tail = the number to be tested

```

```
    )
    (?<=
        (?<!x\1)             # Assert \1 ≥ head
        ,.*                  # head = low end of range; assert \1 was captured
                             # from inside high end of range
    )
)

```

---
Tags: code-golf, number, palindrome
---


title: Tips for golfing in Knight

text:
# Question
Title: Tips for golfing in Knight
Knight is the Language of the Month for August 2022, and I noticed that it didn't have a page, so here it is!

I'm looking for ideas which can be applied to problems and which are also at least somewhat specific to Knight (e.g. "remove comments" is not an answer).

Please post only one tip per answer.

# Answer
> 4 votes
Variables in Knight consist of a lowercase letter followed by additional lowercase letters or numbers, but not uppercase letters. This means that you don't need a space between a variable and a function call -- e.g.

```
Oa Ob
OaOb

```

But you can't do

```
O+a1

```

because the `1` will be parsed as part of the variable name. To get around this, swap the argument order:

```
O+1a

```

# Answer
> 3 votes
The `ASCII` function in Knight, if given a string, returns the ASCII value of just the first character of a string; if given a number, it returns the ASCII character with that code point. This means that `ASCII (ASCII s)` will return the first character of string `s`. You can use this along with `GET` to iterate through a string:

```
;=pP;=i~1W<=i+1iLpO Gp i 1
;=pP Wp;O A Ap=pGp 1Lp

```

Here's the code snippets written out in easier to understand format, with basically equivalent Python code on the side:

```
;= p PROMPT                         # p = input()
;= i ~1                             # i = -1
 WHILE (< (= i (+1 i)) (LENGTH p)   # while (i = i+1) < len(p):
   OUTPUT (GET p i 1)               #   print(p[i:i+1])

;= p PROMPT                         # p = input()
 WHILE p                            # while p != "":
 ;OUTPUT (ASCII (ASCII p))          #   print(p[0])
  = p (GET p 1 (LENGTH p))          #   p = p[1:len(p)+1]

```

Technically, the call to `Gp 1Lp` is undefined since `+ 1 LENGTH p` is outside of the bounds of the string `p`. In order to make it fully spec-compliant, it would have to be

```
;=pP Wp;O A Ap=pGp 1-Lp 1

```

However, the first version works within the C TIO.

*Edit:* Using @Sampersand's suggestions, you could alternatively do

```
;=pP Wp;O GpF1=pSpF1""

```

Which is the same number of characters but spec-compliant. In this case, we can additionally use the fact that `OUTPUT` returns a falsy value to shorten it to

```
;=pP Wp=pSpO GpF1T""

```

Which saves two bytes.

# Answer
> 3 votes
# Use coercion

For example, in the case that `+` receives a string as the first and a number as the second arg, it will coerce the second one to a string and concatenate them. However, if you do it vice versa, with a number as the first and a string as the second, it will convert the second to a number and add the two. This means that you can use `+0` to convert a string to a number, and `+""` to convert a number to a string.

However, sometimes, `+0` can be one byte shorter! `E`, the evaluate function, will evaluate its argument as Knight code. So given a number-string, it will convert to a number. Often, however, this will cost 1 or 2 bytes due to whitespace being needed.

With `*`, if the first argument is a string and the second a number, it will repeat the string n times instead of multiplying. In the case of num+str, it will coerce the string to a number. And with str+str, it will coerce the second to a number and repeat the first string that many times.

However, with `-`, `/`, `^`, and `%`, if the first is a number, the second will be converted to a number. But if the first is a string, it's undefined behavior.

Some other operators like `<` and `>` will also coerce - see the spec.

# Answer
> 3 votes
# Using `&` and `|` instead of `IF`

Unless you need both the if true and if false clauses of `IF`, you can simply use `&` or `|`.

Instead of `Ifoo bar <whatever>`, you can do `&foo bar`. Likewise, instead of `Ifoo <whatever> bar` (or `I!foo bar <whatever>`), you can do `|foo bar`.

# Answer
> 2 votes
Since the assignment operator in Knight returns the assigned value, you can chain together definitions if, for example, you want to create multiple variables with the same value:

```
;=a 0;=b 0=c 0
=a=b=c 0

```

# Answer
> 2 votes
At the risk of stating the obvious, all functions can be abbreviated to a single uppercase character. For example:

```
OUTPUT 1
O 1

```

You also can remove the space between the function and the parameter:

```
O1

```

But if you want to nest function calls, you need to put a space between them:

```
OP   # Parsed as a single function "OP", which is equivalent to "OUTPUT"
O P  # Parsed as "OUTPUT PROMPT"

```

# Answer
> 2 votes
# Use `T` or `F` instead of `1` or `0` to save a character

Examples:

### Save a byte when initializing to 0

Instead of `;=n 0` you can do `;=nF`, but this will require you to ensure that you're coercing `a` later on. But, if you're using `n` as a counter, you can simply do `W>100=n+1n`, which'll coerce the initial `F` to `0`.

### Getting the first character of a string

Instead of `Gs 0 1`, you can do `GsF1`—since all arguments to `G` are coerced to the appropriate types, this'll always work.

### Getting the rest of a string

Instead of `Ss 0 1 ""` (set the range `0..0+1` to an empty string), you can do `SsF1""`. This works in a similar fashion to `G`

---
Tags: code-golf, tips
---


title: How many partitions do I have?

text:
# Question
Title: How many partitions do I have?
The partition number of a positive integer is defined as the number of ways it can be expressed as a sum of positive integers. In other words, the number of integer partitions it has. For example, the number `4` has the following partitons:

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

```

Hence, it has `5` partitions. This is OEIS A000041.

---

# Task

Given a positive integer **N** determine its partition number.

* All standard rules apply.
* The input and output may be handled through any reasonable mean.
* This is , so the shortest code in bytes wins.

---

# Test Cases

```
Input | Output

1  |  1
2  |  2
3  |  3
4  |  5
5  |  7
6  |  11
7  |  15
8  |  22
9  |  30
10 |  42

```

# Answer
> 13 votes
# Pyth, 3 bytes

```
l./

```

**Try it here!** or **Try a test Suite.**

The answer took much longer to format than writing the code itself :P.

---

# How?

Pyth is the right tool for the job.

```
l./   Full program with implicit input.

 ./   Integer partitions. Return all sorted lists of positive integers that add to the input.
l     Length.
      Implicitly output the result.

```

# Answer
> 35 votes
## Mathematica, 11 bytes

```
PartitionsP

```

## Explanation

```
¯\_(ツ)_/¯

```

# Answer
> 10 votes
# Emojicode 0.5, ~~204~~ 201 bytes

```
➡⬅11s 0k⏩0t➖kr ti⏩1 tt i 0➕r i➕s✖rk➗s

```

Try it online!

-3 bytes by using "less than or equal to 1" instead of "less than 2" because the "less than" emoji has a quite long UTF-8 encoding. Also made `t` a frozen to silence a warning without affecting the byte count.

Extends the (integer) class with a method named . You can write a simple program that takes a number from the input, calls  on the number and prints the result like this:

```

 strPlease enter a number
 numstr 10
  num 10

  Learn what a number is, you moron!

```

This part could be golfed a lot by omitting the messages and error handling, but it's not included in the score, so I prefer to show more features of Emojicode instead, while improving readability along the way.

### Ungolfed

```

 ➡
  ◀2
   1

  sum 0
  k⏩0
   nmk➖k
   sig nmk
   i⏩1 nmk
    nmk i 0
     ➕sig i

   ➕sum✖sigk

  ➗sum

```

### Explanation

**Note:** a lot of emoji choice doesn't make much sense in emojicode 0.5. It's 0.x, after all. 0.6 will fix this.

Emojicode is an object-oriented programming language featuring generics, protocols, optionals and closures, but this program uses no closures and all generics and protocols can be considered implicit, while the only optional appears in the I/O stub.

The program operates on only a few types: is the integer type, is the string type and ⏩ is the range type. A few booleans () appear too, but they are only used in conditions. Booleans can take a value of or , which correspond to true and false, respectively.

There are currently no operators in Emojicode, so addition, comparsions and other operations that are normally operators are implemented as functions, effectively making the expressions use prefix notation. Operators are also planned in 0.6.

Let's tackle the test program first.

```

```

This is the block, which can be compared to main from other languages.

```
 ...

```

Grapes and watermelons declare code blocks in emojicode.

```
strPlease enter a number

```

This declares a "frozen" named `str` and sets it value to a new string created using the initializer (constructor) , which takes a prompt as a string and then inputs a line from the user. Why use a frozen instead of a variable? It won't change, so a variable would emit a warning.

```
numstr 10

```

Let's break it down. `str 10` calls the method on the `str` frozen with the argument 10. By convention, methods named with the name of a type convert the object to that type. 10 is the base to use for integer conversion. This method returns an optional, . Optionals can contain a value of the base type or nothingness, ⚡. When the string doesn't contain a number, ⚡ is returned. To use the value, one has to unwrap the optional using , which raises a runtime error if the value is ⚡. Therefore, it is good practice to check for nothingness before unwrapping an optional. It is so common, in fact, that Emojicode has a shorthand for that. Normally,  is an "if".  `variable expression` means: evaluate the expression. If the optional contains nothingness, the condition evaluates to (false). Otherwise, a frozen named `variable` is created with the unwrapped value of the optional, and the condition evaluates to , (true). Therefore, in normal usage, the  `...`  block following the conditional is entered.

```
num 10

```

 is the method the main code adds to using that calculates the number of partitions. This calls  on the `num` frozen we declared in the conditional and converts the result to a string using base 10 by the method. Then, prints the result.

```
 ...

```

means "else", so this block is entered when the user did not enter a number correctly.

```
Learn what a number is, you moron!

```

Prints the string literal.

Now, let's look at the main program. I'll explain the ungolfed version; the golfed version just had the whitespace removed and variables renamed to single letter names.

```
 ...

```

Extend the class. This is a feature that is not commonly found in programming languages. Instead of creating a new class with as the superclass, modifies directly.

```
➡ ...

```

Creates a new method named  that returns a . It returns the number of partitions calculated using the formula `a(n) = (1/n) * Sum_{k=0..n-1} sigma(n-k)*a(k)`

```
⬅1
 1

```

is similar to `this` or `self` from other languages and refers to the object the method was called on. This implementation is recursive, so this is the terminating condition: if the number the method was called on is less than or equal 1, return 1.

```
sum 0

```

Create a new variable `sum` and set it to 0. Implicitly assumes type .

```
k⏩0

```

iterates over anything that implements the ⚪ protocol, while ⏩ is a range literal that happens to implement . A range has a start value, a stop value and a step value, which is assumed to be 1 if `start < stop`, or -1 otherwise. One can also specify the step value by using the ⏭ to create the range literal. The start value is inclusive, while the stop value is exclusive, so this is equivalent to `for k in range(n)` or the `Sum_{k=0..n-1}` in the formula.

```
nmk➖k

```

We need to calculate sigma(n - k), or the sum of divisors of `n - k` in other words, and the argument is needed a few times, so this stores `n - k` in the variable `nmk` to save some bytes.

```
sig nmk
i⏩1 nmk

```

This sets the `sig` variable to the argument of sigma and iterates over all numbers from 1 to `nmk - 1`. I could initialize the variable to 0 and iterate over 1..nmk but doing it this way is shorter.

```
nmk i 0

```

calculates the remainder, or modulus and checks for equality, so the condition will be if `i` is a divider of `nmk`.

```
➕sig i

```

This is an assignment by call, similar to the `+= -= >>=` operator family in some of the inferior, emoji-free languages. This line can be also written as  `sig ➕ sig i`. Therefore, after the inner loop finishes, `sig` will contain the sum of divisors of `n - k`, or `sigma(n - k)`

```
➕sum✖sigk

```

Another assignment by call, so this adds `sigma(n - k) * A(k)` to the total, just as in the formula.

```
➗sum

```

Finally, the sum is divided by n and the quotient is returned. This explanation probably took thrice as much time as writing the code itself...

# Answer
> 9 votes
# Python 2, 85 83 bytes

-2 bytes thanks to @notjagan

```
lambda n:n<1or sum(sum(i*((n-k)%i<1)for i in range(1,n+1))*p(k)for k in range(n))/n

```

Try it online!

Using recursive formula from OEIS A000041.

# Answer
> 7 votes
# Python 2, ~~54~~ 53 bytes

```
f=lambda n,k=1:1+sum(f(n-j,j)for j in range(k,n/2+1))

```

Try it online!

### How it works

Each partition of **n** can be represented as a list **x = \[x1, ⋯, xm\]** such that **x1 \+ ⋯ + xm = n**. This representation becomes unique if we require that **x1 ≤ ⋯ ≤ xm**.

We define an auxiliary function **f(n, k)** that counts the partitions with lower bound **k**, i. e., the lists **x** such that **x1 \+ ⋯ + xm = n** and **k ≤ x1 ≤ ⋯ ≤ xm**. For input **n**, the challenge thus asks for the output of **f(n, 1)**.

For positive integers **n** and **k** such that **k ≤ n**, there is at least one partition with lower bound **k**: the singleton list **\[n\]**. If **n = k** (in particular, if **n = 1**), this is the *only* eligible partition. On the other hand, if **k \> n**, there are no solutions at all.

If **k \< n**, we can recursively count the remaining partitions by building them from left to right, as follows. For each **j** such that **k ≤ j ≤ n/2**, we can build partitions **\[x1, ⋯, xm\] = \[j, y1, ⋯, ym-1\]**. We have that **x1 \+ ⋯ + xm = n** if and only if **y1 \+ ⋯ + ym-1 = n - j**. Furthermore, **x1 ≤ ⋯ ≤ xm** if and only if **j ≤ y1 ≤ ⋯ ≤ ym-1**.

Therefore, the partitions **x** of **n** that begin with **j** can be calculated as **f(n - j, j)**, which counts the valid partitions **y**. By requiring that **j ≤ n/2**, we assure that **j ≤ n - j**, so there is at least one **y**. We can thus count *all* partitions of **n** by summing **1** (for **\[n\]**) and **f(n - j, j)** for all valid values of **j**.

The code is a straightforward implementation of the mathematical function **f**. In addition, it makes **k** default to **1**, so `f(n)` computes the value of **f(n, 1)** for input **n**.

# Answer
> 5 votes
# Pari/GP, 8 bytes

```
numbpart

```

Try it online!

# Answer
> 5 votes
## Retina, 34 bytes

```
.+
$*
+%1`\B
;$'¶$`,
,

%O`1+
@`.+

```

Try it online!

### Explanation

```
.+
$*

```

Convert the input to unary.

```
+%1`\B
;$'¶$`,

```

This computes all **2n-1** partitions of the unary digit list. We do this by repeatedly (`+`) matching the first (`1`) non-word boundary (`\B`, i.e. a position between two `1`s) in each line (`%`) and replacing it with `;`, everything after it (`$'`), a linefeed (), everything in front of it (`$``) and `,`. Example:

```
1;1,111

```

Becomes

```
      vv
1;1,1;11
1;1,1,11
^^^^^

```

Where `v` marks the result of `$'` and `^` marks the result `$``. This is a common idiom to get the result of two different replacements at once (we basically insert both the `;` and the `,` replacement, as well as the missing "halves" of the string to complete two full substitutions).

We will treat `;` as actual partitions and `,` just as placeholders that prevent subsequent `\B` from matching there. So next...

```
,

```

... we remove those commas. That gives us all the partitions. For example for input `4` we get:

```
1;1;1;1
1;1;11
1;11;1
1;111
11;1;1
11;11
111;1
1111

```

We don't care about the order though:

```
%O`1+

```

This sorts the runs of `1`s in each line so we get unordered partitions.

```
@`.+

```

Finally, we count the unique (`@`) matches of `.+`, i.e. how many distinct lines/partitions we've obtained. I added this `@` option ages ago, then completely forgot about it and only recently rediscovered it. In this case, it saves a byte over first deduplication the lines with `D``.

# Answer
> 3 votes
# Python 2, 89 bytes

-9 bytes by Mr.Xcoder -1 byte by notjagan

```
lambda n:len(p(n))
p=lambda n,I=1:{(n,)}|{y+(x,)for x in range(I,n/2+1)for y in p(n-x,x)}

```

Try it online!

# Answer
> 3 votes
# , ~~37~~ 35 bytes

```
0{]1&((#.]*>:@#.~/.~&.q:@#\%#),])1:

```

Try it online!

## Explanation

```
0{]1&((#.]*>:@#.~/.~&.q:@#\%#),])1:  Input: n
                                 1:  Constant 1
  ]                                  Get n
   1&(                          )    Repeat n times on x = [1]
                          \            For each prefix
                         #               Length
                      q:@                Prime factors
                 /.~&                    Group equal factors
              #.~                        Compute p+p^2+...+p^k for each group
           >:@                           Increment
                    &.q:                 Product
                           %           Divide
                            #          Length
         ]                             Get x
          *                            Times
   1   #.                              Sum
                              ,        Joim
                               ]       Get x
                                       Set this as next value of x
0{                                   Select value at index 0

```

# Answer
> 3 votes
# Octave, 18 bytes

```
partcnt(input(''))

```

Uses the built-in function partcnt.

Can't get it right by using an anonymous function using @, some help would be appreciated.

# Answer
> 3 votes
# Regex  (RME / Perl / PCRE2 v10.35+), ~~13~~ 12 bytes

```
((\1|^)x*)+$

```

Try it on replit.com \- RegexMathEngine
Try it online! \- Perl v5.28.2 / Attempt This Online! \- Perl v5.36+
Attempt This Online! \- PCRE2 v10.40+

Takes its input in unary, as the length of a string of `x`s. Returns its output as the number of ways the regex can match. (The rabbit emoji indicates this output method.)

This simply enumerates all the partitions. In order to count unordered partitions, it enforces that partitions occur in strictly nondecreasing order. This is accomplished by starting with an arbitrary-sized partition on the first iteration, and adding an arbitrary nonnegative integer to the partition size on each iteration. At the end, `$` asserts that the cumulative sum is equal to the input number.

```
                    # tail = N = input number; no need to anchor, because the
                    # following loop is forced to do at least one iteration,
                    # and its first iteration has an anchor.
(                   # \1 = sum of the following:
    (
        \1          # Previous value of \1, if set
    |           # or
        ^           # 0, if this is the first iteration
    )
    x*              # Any arbitrary nonnegative integer
)+                  # Iterate the above any positive number of times
$                   # Assert tail == 0

```

Alternative 12 bytes:

```
(\1x*|^x*)+$

```

Try it online! \- Perl v5.28.2 / Attempt This Online! \- Perl v5.36+
Try it online! \- PCRE2 v10.40+

# Regex  (Raku`:P5`), 13 bytes

```
^(\1x*|^x+)*$

```

Try it online!

```
^                   # tail = N = input number
(                   # \1
    # If on an iteration after the first:
    \1x*            # \1 += {any arbitrary nonnegative integer}; tail -= \1
|
    ^               # Anchor to start, to assert this is the first iteration.
    x+              # \1 = {any arbitrary positive integer}; tail -= \1
)*
$                   # Assert tail == 0

```

Raku's Perl 5 compatibility mode is rather inaccurate, and prevents the 12 byte regex from working, apparently because there is nothing preventing a zero-width match from looping infinitely.

# Regex  (RME / Perl / PCRE), ~~29~~ 20 bytes

```
((?=(\3|^))(\2x*))+$

```

Try it on replit.com \- RegexMathEngine
Try it online! \- Perl v5.28.2 / Attempt This Online! \- Perl v5.36+
**Try it online! \- PCRE1
Try it online! \- PCRE2 v10.33** / Attempt This Online! \- PCRE2 v10.40+

PCRE1, and PCRE2 up to v10.34, automatically makes any capture group atomic if it contains a nested backreference. To work around this, the capture is copied between `\2` and `\3` using only forward-declared backreferences.

This would also make the regex compatible with Python`regex` and Ruby, but they have no way of doing  output without source code modifications.

```
                      # tail = N = input number; no need to anchor, because the
                      # following loop is forced to do at least one iteration,
                      # and its first iteration has an anchor.
(
    (?=
        (             # \2 = the following:
            \3        # Previous value of \3, if \3 is set
        |         # or
            ^         # 0, if on the first iteration
        )
    )
    (                 # \3 = the following, which is also subtracted from tail:
        \2x*          # \2 plus any arbitrary nonnegative integer
    )
)+                    # Iterate the above as many times as possible, minimum 1
$                     # Assert tail == 0

```

# Perl, ~~37~~ 36 bytes (full program)

```
1x<>~~/((\1|^).*)+$(??{++$i})/;say$i

```

Try it online!

Alternative 36 bytes:

```
1x<>~~/((\1|^).*)+$(??{++$\})/;print

```

Try it online!

# Perl `-p`, ~~33~~ 32 bytes (full program)

```
1x$_~~/((\1|^).*)+$(??{++$\})/}{

```

Try it online!

Can only take one input (followed by EOF) per run. See Fibonacci function or sequence for an explanation.

# Raku, 29 bytesSBCS (anonymous function)

```
{+m:ex:P5/^(\1.*|^.+)*$/}o¹x*

```

Try it online!

# Answer
> 2 votes
# JavaScript, ~~125~~ 121 bytes

```
n=>(z=(a,b)=>[...Array(a)].map(b))(++n**n,(_,a)=>z[F=z(n,_=>a%(a/=n,n)|0).sort().join`+`]=b+=eval(F)==n-1&!z[F],b=0)|b||1

```

Try it online!

Warning: time and space complexity is exponential. Works very slow for large numbers.

# Answer
> 2 votes
# JavaScript ES7, 69 Bytes

```
n=>(f=(i,s)=>i?[for(c of Array(1+n))f(i-1,s,s-=i)]:c+=!s)(n,n,c=0)&&c

```

Try it online!

# JavaScript ES6, 71 Bytes

```
n=>(f=(i,s)=>i?[...Array(1+n)].map(_=>f(i-1,s,s-=i)):c+=!s)(n,n,c=0)&&c

```

Try it online!

Time complexity O(n^n), so be careful (an obvious delay appears on my computer for `F(6)`)

# Answer
> 2 votes
# Desmos, 64 bytes

```
p(n)=1+∑_{i=1}^{n^n}0^{(n-∑_{j=1}^njmod(floor(ni/n^j),n))^2}

```

Try it on Desmos!

This is `O(n^(n+1))`

## How it works

The value of `i` in base `n` encodes a partition by counting the multiplicity of each part.

For `n=8`, `i=81` encodes `[mod(81,8), mod(81//8,8), mod(81//8^2,8), ...] = [1,2,1]`, so that's 1 one, 2 twos, and 1 three, which gives the partition `1 + 2 + 2 + 3`

`mod(floor(ni/n^j),n)` is the number of parts of size `j`.

`∑_{j=1}^njmod(floor(ni/n^j),n)` is the sum of the parts

`0^{(n-sum)^2}` is an indicator for if `i` encodes a partition of `n`: it is 1 if the sum is n, otherwise 0

Summing `0^{(n-sum)^2}` over all valid `i` gives the number of partitions, excluding the n-ones partition `1+1+1....+1` because `i=n` encodes one 2, not n 1s, so we add 1 to the count.

# DesModder Text Mode Beta 1, 73 bytes

```
p(n)=1+sum i=(1...n^n)({n=sum j=(1...n)(j*mod(floor(n*i/n^j),n)),else:0})

```

DesModder Text Mode avoids the pains of golfing Desmos LaTeX, but it's still a bit buggy, and the syntax is in flux. So some more development might end up with the following syntax for 64 bytes:

```
p(n)=1+sum(i=1...n^n,{n=sum(j=1...n,j*mod(floor(n*i/n^j),n)),0})

```

# Answer
> 1 votes
# Jelly, 13 bytes

```
JÆsæ.:L;
1Ç¡Ḣ

```

Try it online!

Takes 5 seconds to solve n = 1000 on TIO.

# Answer
> 1 votes
# Jelly, 3 bytes

The `Œṗ` atom has recently been added, and it means "Integer partitions".

```
ŒṗL

```

Try it online!

```
ŒṗL   - Full program.

Œṗ    - Integer partitions.
  L   - Length.
      - Output implicitly.

```

# Answer
> 1 votes
# Pyt, 2 bytes

```
←ᵱ

```

Try it online!

Explanation:

```
←          Get input
 ᵱ         Number of partitions

```

# Answer
> 1 votes
# 05AB1E, 3 bytes

```
Åœg

```

Try it online or verify all test cases.

**Explanation:**

```
Åœ   # Get all lists of positive integers that sum to the (implicit) input
  g  # Pop and push the length to get the amount lists
     # (which is output implicitly as result)

```

# Answer
> 1 votes
# Vyxal `l`, 1 byte

Try it Online!

# Vyxal, 2 bytes

```
ṄL

```

Try it Online!

# Answer
> 1 votes
# Jelly, 5 bytes

```
ŻṗḋRċ

```

Try it online!

Non-builtin solution using Henry Bottomley's comment at the top of the OEIS page. Although this obviously doesn't beat the builtin, I wouldn't be surprised if the same approach might be the shortest in some other array languages.

```
 ṗ       Generate every combination of n elements with replacement from
Ż        [0 .. n],
  ḋ      dot product each with
   R     [1 .. n],
    ċ    and count the occurrences of n.

```

This can also be thought of as encoding each unordered partition as an ordered list of the multiplicity of each integer.

# Answer
> 0 votes
# Java 8 (229 bytes)

```
import java.util.function.*;class A{static int j=0;static BiConsumer<Integer,Integer>f=(n,m)->{if(n==0)j++;else for(int i=Math.min(m,n);i>=1;i--)A.f.accept(n-i,i);};static Function<Integer,Integer>g=n->{f.accept(n,n);return j;};}

```

Ungolfed:

```
import java.util.function.*;

class A {
    static int j = 0;
    static BiConsumer<Integer, Integer> f = (n, m) -> {
        if (n == 0)
            j++;
        else
            for (int i = Math.min(m, n); i >= 1; i--)
                A.f.accept(n - i, i);
    };
    static Function<Integer, Integer> g = n -> {
        f.accept(n, n);
        return j;
    };
}

```

---
Tags: code-golf, math, number-theory, combinatorics, integer-partitions
---