title: Number Chaining Predicate

text:
# Question
Title: Number Chaining Predicate
# Problem:

Your task is to decide if in a sequence of numbers, every number contains at least one of the digits of the number that preceded it.

For example, the following should return truthy:

```
[1, 12, 203, 0, 30]
             ^   ^ Contains a 0
        ^ Contains a 2
    ^ Contains a 1

```

The following should return falsey:

```
[1, 32, 23, 34]
    ^ Doesn't contain a 1, therefore false

```

Your submission can be a function or full program.

# Input:

Input can be any reasonable type of sequence. An array of numbers, an array of strings, a delimited string of numbers, etc.

Order matters however, so whatever structure you choose to accept as input obviously must have a definite ordering.

Input can be taken via the stdin or as an argument.

You can assume:

* all numbers will be non-negative integers
* input will always contain at least 2 numbers
* input numbers will not start with a 0

# Output:

Output will be a truthy or falsey value (as defined by your language), representing whether or not the above specification is met.

Truthy/falsey values don't need to be consistent between tests.

It can either be output to the stdout or returned.

# Test Cases:

```
True cases:
[1, 1, 1, 11, 111, 11, 1]
[12, 23, 34, 45, 56]
[65, 54, 43, 32, 21]
[123, 29, 9, 59, 55, 52, 2017, 2]
[1234567890, 19, 95, 5012, 23]

False cases:
[1, 2, 3, 4, 5, 1, 11] (2 doesn't contain a 1)
[12, 23, 33, 45] (45 doesn't contain a 3)
[98, 87, 76, 11, 12, 23] (11 doesn't contain a 7 or 6)

```

This is code-golf, so the least number of bytes wins.

# Answer
# Jelly, ~~5~~ 4 bytes

```
f2\Ạ

```

Input is an array of strings.

Try it online!

### How it works

```
f2\Ạ  Main link. Argument: A (array of strings)

 2\   Pairwise reduce by:
f       Filter, yielding all chars in the left string that appear in the right one.
   Ạ  All; yield 1 if all strings are non-empty, 0 if not.

```
> 7 votes

# Answer
# Python 2, 48 bytes

```
lambda x:reduce(lambda a,b:set(a)&set(b)and b,x)

```

Try it online!

Print a empty set for `False` and the last element for `True`
> 13 votes

# Answer
# Retina, ~~25~~ 20 bytes

```
(.).*¶(?=.*\1)

^.+$

```

Try it online!

Whenever we find a digit that also occurs in the next number, we remove the separator between those numbers (along with the digits in the former number, starting from the shared one, but that's irrelevant). The input is valid, if all separators have been remove in the process, which we check by making sure that the string can be matched as a single line.
> 12 votes

# Answer
# Brachylog, 9 bytes

```
{⊇ᵐ=∧?t}ˡ

```

Try it online!

Note that this not only works with a list of integers, but also with a list of strings or a list of lists.

### Explanation

```
{      }ˡ       Left fold on the input:
 ⊇ᵐ=              It is possible to find a number which is a subset of both input numbers
    ∧             (and)
     ?t           The output is the second number (to continue the fold)

```
> 11 votes

# Answer
# JavaScript (ES6), ~~47~~ ~~44*~~ 43 bytes

*Saved a byte thanks to @Neil*

```
x=>x.every(y=>y.match(`[${p}]`,p=y),p=1/19)

```

Takes input as a list of strings.

### Test snippet

```
let f =
x=>x.every(y=>y.match(`[${p}]`,p=y),p=1/19)

let g = x => console.log("f([%s]): %s", x.join(", "), f(x.map(String)))

g([1, 1, 1, 11, 111, 11, 1])
g([12, 23, 34, 45, 56])
g([65, 54, 43, 32, 21])
g([123, 29, 9, 59, 55, 52, 2017, 2])
g([123456789, 19, 95, 5012, 23])

g([1, 2, 3, 4, 5, 1, 11])
g([12, 23, 33, 45])
g([98, 87, 76, 11, 12, 23])
```

**(crossed out 44 is still regular 44)*
> 8 votes

# Answer
# 05AB1E, 10 bytes

```
ü‚vy`Så1åP

```

Try it online! or as a Test suite

**Explanation**

```
ü‚          # map pairing over each pair in input
  v         # for each pair
   y`       # push as 2 separate elements on stack
     Så     # check each digit in 2nd number for membership in first
       1å   # check if any 1 exists in the resulting list
         P  # product of stack

```
> 6 votes

# Answer
# CJam, ~~18~~ ~~15~~ 14 bytes

*Saved 4 bytes thanks to Martin Ender*

```
l~Afb_1>.&:,:*

```

Try it online!

**Explanation**

```
l~              e# Read and eval the input
  Afb           e# Convert each number to a list of digits
     _          e# Duplicate the array
      1>        e# Slice it after the first element
        .&      e# Vectorized set intersection; take the set intersection of corresponding
                e#  elements of the two arrays
          :,    e# Get the length of each intersection
            :*  e# Take the product of the whole array.
                e#  Will be 0 if any intersection was empty.

```
> 6 votes

# Answer
# Haskell, ~~51~~ ~~48~~ 35 Bytes

-3 bytes thanks to @NickHansen! I really need to get better with those monad operators

-4 and -9 bytes thanks to @Laikoni and @nimi respectively!

```
and.(zipWith(any.flip elem)=<<tail)

```

This version takes the input as an array of strings, eliminating the need for `show`, but as far as I can see it works in largely the same way as the older version:

```
all(\(x,y)->any(`elem`x)y).(zip=<<tail).map show

```

(I'm fairly certain I'm allowed to submit an anonymous function like this, but I'll fix it if necessary)

First the numbers are converted to strings. Then the monad magic `zip=<<tail` creates a function that zips the list with itself which pairs each entry with its neighbor(s). Then `all` maps a lambda to each pair that checks whether one string contains any chars from the other and finally checks that they all come out `True`.

Old version that works basically the same way:

```
f a=and$zipWith(\b->any(`elem`show b).show)a$tail a

```
> 6 votes

# Answer
# Ruby, ~~49~~ 48 bytes

```
->x{x.each_cons(2){|z|x&&=z*' '=~/(.).* .*\1/};x}

```

Output is `nil` for false and a "random" integer for true.
> 5 votes

# Answer
# Mathematica ~~62 47~~ 35 bytes

With 12 bytes saved thanks to MartinE.

```
FreeQ[#⋂#2&@@@Partition[#,2,1],{}]&

```

---

```
FreeQ[#⋂#2&@@@Partition[#,2,1],{}]&[{{1},{1,2},{2,0,3},{0},{3,1}}]

```

> False

```
FreeQ[#⋂#2&@@@Partition[#,2,1],{}]&[{{1},{1,2},{2,0,3},{0},{3,0}}]

```

> True
> 5 votes

# Answer
# Java 8, ~~94~~ ~~90~~ 87 bytes

Input is an array of strings representing the numbers. Starting with the second string, it performs a regular expression comparison against each previous string to see if it contains any of its characters: `.*[previous string].*`.

Golfed:

```
a->{int r=1,i=0;while(++i<a.length)r*=a[i].matches(".*["+a[i-1]+"].*")?1:0;return r>0;}

```

Ungolfed:

```
public class NumberChainingPredicate {

  public static void main(String[] args) {
    System.out.println("Expect true:");
    for (String[] input : new String[][] { { "1", "1", "1", "11", "111", "11", "1" }, { "12", "23", "34", "45", "56" },
        { "65", "54", "43", "32", "21" }, { "123", "29", "9", "59", "55", "52", "2017", "2" },
        { "1234567890", "19", "95", "5012", "23" } }) {
      System.out.println(java.util.Arrays.toString(input) + " = " + exec(f(), input));
    }

    System.out.println();
    System.out.println("Expect false:");
    for (String[] input : new String[][] { { "1", "2", "3", "4", "5", "1", "11" }, { "12", "23", "33", "45" },
        { "98", "87", "76", "11", "12", "23" } }) {
      System.out.println(java.util.Arrays.toString(input) + " = " + exec(f(), input));
    }
  }

  private static java.util.function.Function<String[], Boolean> f() {
    return a -> {
      int r = 1, i = 0;
      while (++i < a.length) {
        r *= a[i].matches(".*[" + a[i - 1] + "].*") ? 1 : 0;
      }
      return r > 0;
    };
  }

  private static boolean exec(java.util.function.Function<String[], Boolean> function, String[] input) {
    return function.apply(input);
  }

}

```
> 4 votes

# Answer
# Jelly, 6 bytes

```
Dµf"ḊẠ

```

Try it online!

## Explanation

```
Dµf"ḊẠ
Dµ        Treat the first (i.e. only) input as a list of decimal digits
   "      For each pair of corresponding elements in {the input digits} and
    Ḋ     {the input digits} with the first element removed
  f       take all elements common to both sides
     Ạ    then return true if the result has no empty lists, false otherwise

```

It's most obvious to try to use `2/` here, but that runs a unary function on all slices of size 2. `"Ḋ` effectively runs a *binary* function on all pairs of adjacent elements, which means we can use `f` directly (rather than needing to convert it to a unary function as `f/`). This does end up leaving the last element of the input in place, but luckily not even an input of 0 becomes an empty list when converted to decimal, so it has no effect on the .
> 4 votes

# Answer
# Python 3, 48 bytes

```
f=lambda x:x==x[:1]or{*x[0]}&{*x[1]}and f(x[1:])

```

Try it online!
> 4 votes

# Answer
# Jelly, 8 bytes

```
Dœ&L¥2\Ạ

```

**Try it online!**

### How?

```
Dœ&L¥2\Ạ - Main link: the list of integers            e.g. [3, 13, 351, 73, 82]
D        - convert all the integers to decimal lists       [[3],[1,3],[3,5,1],[7,3],[8,2]]
     2\  - 2-slice cumulative reduce with:
    ¥    -     last two links as a dyad:
 œ&      -         multiset intersection                   [[3],[1,3],[3],[]]
         -         length                                  [1,2,1,0]
       Ạ - all truthy?                                     0

```
> 3 votes

# Answer
# 05AB1E, 5 bytes

Code:

```
üÃõå_

```

Uses the **CP-1252** encoding. Try it online! or Verify all test cases!.

Explanation:

```
üÃ         # Intersection on each pair
  õå       # Check if the empty string exists
    _      # Boolean negate

```
> 3 votes

# Answer
# PowerShell, 87 bytes

```
param($n)(1..($a=$n.length-1)|?{[char[]]$n[($i=$_)-1]|?{$n[$i]-like"*$_*"}}).count-eq$a

```

Try it online!

Not the shortest by any measure, but a slightly different approach than others are using, and shows off the nifty `|?{}` functionality.

This takes the input as an array of strings into `$n`, then loops from `1` up to the `length-1`. We use `Where-Object` (the `|?{...}`) to pull out those indices that are truthy for a particular condition. You can think of this like a combination `for` loop with an `if` clause.

The clause here is `[char[]]$n[($i=$_)-1]|?{$n[$i]-like"*$_*"}`. That is, we're taking the current index `$_`, setting it to `$i`, and subtracting `1`, and using that to index into `$n` (i.e., so we get the previous element in our input array). That is then cast as a `char`-array and sent through another `Where-Object` procedure.

The inner clause `$n[$i]-like"*$_*"` specifies that the string at the current index `$i` is `-like` the current character `$_` from the previous index. This will therefore output any characters that are in common between the two array elements. Thus, the outer clause will only be truthy if there is a character in common (since an empty array is falsey in PowerShell), and so the index will only be selected if there are characters in common.

Then, we gather up all of the indices that matched the criteria, and verify that the `.count` thereof is `-eq`ual to the length of the input array. That Boolean result is left on the pipeline, and output is implicit.
> 2 votes

# Answer
# Perl 5, 31 bytes

A port of Martin Ender's beautiful answer.

30 bytes of code + `-p` flag.

```
s/(\S)\S* (?=\S*\1)//g;$_=!/ /

```

Try it online!
> 2 votes

# Answer
# PHP, 65 68

```
for(;null!==$a=$argv[++$i+1];)$r+=$a==strtr($a,$argv[$i],_);echo!$r;

```

iterate over all numbers and remove all digits that appeared in the previous. Count how often it equals the number itself (no digit removed). If at least one equaled we didn't have a match in one of the pairs.

---

Fixed a mistake using `trim` insted of `strtr`. Thanks to @JörgHülsermann
> 2 votes

# Answer
# APL (Dyalog APL), 9 bytes

```
∧/×≢¨2∩/⎕

```

Try it online!

`∧/` are all ones in the list of

`×` the signs

of the tally of

`¨` each of

`2∩/` the pair-wise intersections of

the input?
> 2 votes

# Answer
# PHP, 75 bytes

```
for($b=3**39;--$argc;)preg_replace("#[$b]#","",$b=$argv[$argc])<$b?:die(1);

```

takes numbers from command line arguments; exits with `1` for falsy, with `0` for truthy.
Run with `-r` or test it online.

* start with `$b` = a number containing all digits
* loop down through the arguments
    + remove all digits of `$b` from the argument
    + copy argument to `$b`
    + if no digit was removed, exit with `1`
* implicit: exit with `0`
> 2 votes

# Answer
# PHP, 77 Bytes

```
for($i=$t=1;++$i<$argc;)$t*=preg_match("#[{$argv[$i-1]}]#",$argv[$i]);echo$t;

```
> 1 votes

# Answer
# MATL, 14 bytes

```
1&)"V@VX&nv@]x

```

Try it online!

Thanks @LuisMendo for saving a byte. Explanation:

```
1&)            % 'Pop' the first item from the input and push it on the stack.
   "       ]   % Main 'for' loop, to loop over the rest of the input.
    V            % Stringify previous (or first) iten from the input.
     @V          % Push current number, convert to string
       X&        % Intersect with stringified number already on the stack.
         nv      % Count the size of the intersection, and add it to the existing list of sizes.
           @     % Push the current number again for the intersection in the next loop.
             x % Remove the number pushed by the last loop.
               % Else the program would end with the result on the second instead of the first position in the stack

```
> 1 votes

# Answer
# Röda, ~~45~~ 35 bytes

```
{[_=~`(\S*(\S)\S* (?=\S*\2))+\S+`]}

```

Try it online!

This is similar to the Perl 5 solution, which is a port of the Retina solution by Martin Ender. -10 bytes thanks to @Neil.

Here's a different solution (~~73~~ 72 bytes):

```
{[_/""]|{|x|{x|[0]()unless[not(_ in y)]else[1]}if tryPeek y}_|sum|[_=0]}

```

It's an anonymous function that pulls strings from the stream and checks that the consecutive strings contain same characters. Explanation:

```
{
    [_/""]|    /* split strings -> creates arrays of characters */
    {|x|       /* begin for loop over character arrays */
        {      /* begin if tryPeek(y) -> peeks the second item from the stream */
               /* x and y are now two consecutive character arrays */
            x| /* push characters in x to the stream */
            [0]()unless[not(_ in y)]else[1] /* pushes 0 to the stream */
                                            /* if y contains the character */
                                            /* in the stream, otherwise 1 */
        }if tryPeek y
    }_|        /* end for loop */
    sum|       /* sum all numbers in the stream */
    [_=0]      /* return true if the sum is zero */
}

```

It could possibly be golfed more...
> 1 votes

# Answer
# Clojure, 71 bytes

```
(fn[n](every?(fn[[q w]](some q w))(partition 2 1(map #(set(str %))n))))

```

An anonymous function that accepts a sequence of numbers. Returns `true`/`false`.

I like how it reads. There's definitely a few areas that can be improved upon here. My function being passed to `map` can't easily be changed so that it doesn't require the function macro, which means the entire function can't make use of the macro, which likely added some bytes. It would also be nice if I could figure out a better way of unpacking the values in the `every?` predicate.

```
(defn number-chain? [nums]
  (let [; Turn each number into a set of characters
        set-nums (map #(set (str %)) nums)

        ; Partition the sets into lists of neighbors
        ; [1 2 3 4] -> [[1 2] [2 3] [3 4]]
        partitioned (partition 2 1 set-nums)]

    ; Does every second neighbor contain some element of the first?
    (every?
      (fn [[l1 l2]]
        (some l1 l2))
      partitioned)))

```
> 1 votes

# Answer
# SimpleTemplate, 124 bytes

Wow, this was a workout!

```
{@eachargv asA keyK}{@ifK}{@setR"/[",O,"]/"}{@calljoin intoR"",R}{@ifA is notmatchesR}{@return}{@/}{@/}{@setO A}{@/}{@echo1}

```

This "simply" makes a regex using the old element, showing `1` as a truthy value, or nothing otherwise.

---

**Ungolfed:**

```
{@each argv as number key K}
    {@if K}
        {@set regex "/[", old, "]/"}
        {@call join into regex "", regex}
        {@if number is not matches regex}
            {@return false}
        {@/}
    {@/}
    {@set old number}
{@/}
{@echo 1}

```
> 1 votes

# Answer
## JavaScript (ES6), 37 bytes

```
s=>/^(.*(.).*\n(?=.*\2))+.+$/.test(s)

```

Accepts input as a string of newline-separated numbers. Based on @MartinEnder♦'s excellent Retina answer, but doing the entire test in a single regexp because it's shorter in JavaScript that way.
> 1 votes

# Answer
# Bash \+ Unix utilities, ~~71~~ 69 bytes

```
sed "s/\(.*\)/<<<\1 \&\&grepx[\1]/;1s/.*g/g/;\$s/ .*//"|tr 'x
' \ |sh

```

Try it online!

Input is on stdin, one number per line.

Output is in the exit code: 0 for truthy, 1 for falsey.

This can probably be golfed more.

For the code above to work, there cannot be any file in the current directory whose name is a single digit. If this isn't acceptable, replace `[\1]` in the program with `'[\1]'` (at a cost of 2 additional bytes).

Sample run (the last test case provided in the challenge):

```
$ echo '98
> 87
> 76
> 11
> 12
> 23' | ./digittest > /dev/null; echo $?
1

```

(1 here is falsey.)

---

How it works:

I'll demonstrate on the sample run above.

The sed command converts the input into:

```
grepx[98]
<<<87 &&grepx[87]
<<<76 &&grepx[76]
<<<11 &&grepx[11]
<<<12 &&grepx[12]
<<<23

```

The tr command then converts this to the string:

```
grep [98] <<<87 &&grep [87] <<<76 &&grep [76] <<<11 &&grep [11] <<<12 &&grep [12] <<<23

```

This string is a shell command for doing the desired operation, so I pipe that into sh and I'm done.
> 1 votes

# Answer
# Pip, ~~12~~ 10 bytes

```
$&B@X^_MPg

```

Takes input as a series of command-line arguments. Output is a nonempty list for truthy and an empty list for falsey. Try it online or verify all test cases.

### Explanation

```
         g  List of all cmdline args
       MP   Map this function to consecutive pairs of items from that list:
     ^_      Split 1st item of pair into list of characters
    X        Convert to regex that matches any of those characters
  B@         Find all matches in 2nd item of pair
$&          Fold on logical AND--truthy if all items are truthy, falsey if one is falsey
            Print (implicit)

```
> 1 votes

# Answer
## Q, 57 bytes

```
{r::();({r,::any(last x)in y;x,enlist y}\)($)0,x;all 1_r}

```
1. Initialises global r.
2. Converts input to array of strings.
3. Scans array checking that some character in last string is in current string.
4. Appends each result to r.
5. Returns 1 if all strings satisfy step 3 else returns 0.

Note: 0 appended to start of input array within function. This was done so that the comparison of the first element would be done enlisted. Otherwise, the last character of the first element is grabbed for comparison. Could do a type check however that adds 7 bytes over the current count.
> 1 votes

---
Tags: code-golf
---


title: Flip a coin for me!

text:
# Question
Title: Flip a coin for me!
> ***Note**: There was not a vanilla challenge to actually flip a coin, even though there were mentions about flipping coins a lot of places. Even though there is a challenge to generate a random number from 1 to N, I suspect this is not a dupe. These questions ask for random numbers from 1 to N, while this ask for just truthy/falsy.*

Flipping a coin is widely used in selecting decisions. But, I do not have a coin (only bills and credit/debit cards).

So, your program has to flip a coin for me!

---

# I/O

## Input:

None.

## Output:

A truthy/falsy value depending on the coin's state(heads/tails). It does not have to be uniform, seeding by timestamp is allowed. Also, we do not count neither-heads-nor-tails, and assume the coin only has two sides.

# Answer
# Python 2, ~~18~~ ~~17~~ ~~15~~ 14 bytes

```
0/(id(0)&4096)

```

Try it online! Output is via exit code, so check the *Debug* drawer.

If 50/50 chance isn't required, these shorter versions will work as well.

```
0/(id(0)%3)   # 11 bytes, awfully biased
0/(id(0)>>25) # 13 bytes, even more biased
0/(id(0)%6<3) # 13 bytes, fair enough for most practical purposes

```

### How it works

In CPython 2.7.12, `id(1)` yields the memory location of the constant **1** as a 32-bit integer with the following pattern.1

```
000000yxxxxxxxxxxxxx000110100000

```

**y** isn't constant, but it's biased towards **0**. All **x** bit seem to occur with the same probability. I ran the program 100,000 times and these were the distributions.

```
Bit  Zeroes  Ones
  0  100000       0
  1  100000       0
  2  100000       0
  3  100000       0
  4  100000       0
  5       0  100000
  6  100000       0
  7       0  100000
  8       0  100000
  9  100000       0
 10  100000       0
 11  100000       0
 12   50125   49875
 13   50319   49681
 14   50001   49999
 15   50164   49836
 16   50095   49905
 17   50072   49928
 18   49780   50220
 19   50056   49944
 20   49910   50090
 21   50038   49962
 22   50103   49897
 23   49811   50189
 24   50106   49894
 25   80950   19050
 26  100000       0
 27  100000       0
 28  100000       0
 29  100000       0
 30  100000       0
 31  100000       0

```

If the twelfth least significant bit is set, `id(0)&4096` yields **1** and the program exits with status code **1**. However, if it is *not* set, `id(0)&4096` yields **0**, a *ZeroDivisionError* is raised, and the program exits with status code **1**.

---

1 I've verified anything I couldn't find in the docs empirically. Other implementations may behave differently.
> 7 votes

# Answer
# MATL, 3 bytes

```
rEk

```

This outputs `0` or `1` with the same probability.

Try it online!

### Explanation

```
r     % Random number uniformly distributed on the interval (0,1)
E     % Multiply by 2
k     % Round down

```
> 2 votes

# Answer
# Pyth, 2 bytes

```
O2

```

Outputs 0 for heads, 1 for tails.

Similarity to any real-world company only incidental.

Try it!
> 2 votes

# Answer
## JavaScript (ES6), 13 bytes

```
_=>new Date%2

```

### Test snippet

```
let f =
_=>new Date%2
```

```
<button onclick="console.log(f())">Flip</button>
```
> 2 votes

# Answer
# Powershell, 8 Bytes

```
random 2

```

outputs either 0 or 1 randomly.
> 2 votes

# Answer
# Perl 6, 11 bytes

```
{Bool.pick}

```

Try it

## Explanation:

* `Bool` is an enum of `True` and `False`
* `.pick` picks an element at random from a list
* `{…}` in this case makes it a lambda
> 2 votes

# Answer
# Japt, 3 bytes

```
K%2

```

Try it online! (Output cache disabled for obvious reasons)

Outputs `0` or `1` with equal probability. `K` is equivalent to `new Date()` in JavaScript, and `%2` takes the timestamp mod 2.

---

Alternatively:

```
½>Mr

```

This one generates a random float `x` between 0 and 1, and outputs `.5>x`. Try it online!
> 2 votes

# Answer
# CJam, 3 bytes

```
2mr

```

Try it online!

**Explanation**

```
2    e# Push 2
 mr  e# Random integer from 0 to n-1

```
> 1 votes

# Answer
# PHP, 13 bytes

```
<?=rand(0,1);

```

Outputs a pseudo-random `0` or `1` value.

Test online
> 1 votes

# Answer
# Octave, 10 bytes

```
@()rand<.5

```

Anonymous fuction that takes no inputs and returns `0` or `1`.

Try it online!
> 1 votes

# Answer
# Jelly, 3 bytes

```
2ḶX

```

Try it online!
> 1 votes

# Answer
# \>\<\>, ~~14~~ 11 bytes

```
x0n;n0
>1n;

```

Try it online!

Outputs either `0` or `1`
> 1 votes

# Answer
# Cubix, 7 bytes

```
w>O@D1.

```

Outputs `0` with 1/3 probability, `1` with 2/3 probability. Try it online!

I think this is the first time I've had to pad the source code with no-ops to make the cube the correct size...

### Explanation

Cubix is a 2D stack-based esolang wrapped around a cube. The source code won't fit onto a size-1 cube, and so it gets wrapped around a size-2 cube, with the following cube net:

```
    w >
    O @
D 1 . . . . . .
. . . . . . . .
    . .
    . .

```

The IP (instruction pointer) is then sent into action, starting at the top-left corner of the left-most face, and facing east. The first instruction it hits is `D`, which points the IP in a random direction. This isn't the best possible source of randomness for this challenge, but it's the only one Cubix has.

If the IP is pointed north, it wraps onto the `w` on the top face, which moves the IP one position to the right (south at this point). `O` outputs the top item on the stack as a number (`0` if the stack is empty), and `@` ends the program.

If the IP is pointed south, it wraps around various faces before hitting the `>` on the top face. It's going west at this point, and `>` points the cursor east, sending it back to the `D`, which starts the whole process over.

If the IP is pointed east or west, it simply wraps around the third row of the above diagram, hitting the `1` at some point in the middle. When it gets back to the `D`, the process is started again as before, but when the IP eventually gets sent north, `O` outputs `1` instead of `0`.

So each time `D` is hit, there's a 2/4 chance that the output will be `1`, and a 1/4 chance that it will be `0`. The other 1/4 is simply the chance of the process starting over, and so if we sum the infinitely shrinking chances of each output, we get 2/3 for `1` and 1/3 for `0`.
> 1 votes

# Answer
# 05AB1E, ~~4~~ 3 bytes

```
T.R

```

Try it online!

Explanation:

```
T   10
 .R Random choice (breaks into individual digits)

```
> 1 votes

# Answer
# Röda, 13 bytes

```
randomBoolean

```

Try it online!

This is a boring builtin.
> 1 votes

# Answer
# \*\>\<\>, 6 bytes

```
x0n;n1

```

Online interpreter
> 1 votes

# Answer
# Gol\>\<\>, 3 bytes

```
xh1

```

Online interpreter
> 0 votes

# Answer
# Befunge-98, 6 bytes

```
#1?0>q

```

Try it online!

Exits with exit code 0 or 1.

## Explanation

Program flow in Befunge is a bit difficult to follow. The Instruction Pointer (IP) starts on the left, moving towards the right. The first instruction `#` tells it to ignore the next instruction, so it jumps to `?`. This randomly sets the IP moving either up, down, left, or right. If it moves up or down, it "wraps around" and hits the `?` again. If it moves right, 0 is pushed onto the stack and then `q` exits with the topmost value of the stack (0) as the exit code. If the IP moves left, 1 is pushed onto the stack, `q` is jumped over, `>` sets the IP moving to the right again, and then `q` exits the program with the topmost value of the stack (1) as the exit code.

I believe that this code also works in Unefunge-98, Trefunge-98, and possibly all members of the Funge-98 family. I have not tested any of these claims though.
> 0 votes

---
Tags: code-golf, random
---


title: Grade My Scan-tron!

text:
# Question
Title: Grade My Scan-tron!
Standardized testing usually comes with a scan-tron or some type of answer document that records your answer. A computer or human(s) would then check your answers and determine your grade. So here, given a scan-tron and the answer key, determine the score and questions missed if any. A scan-tron is just a document with multiple lines with answers in which the user fills in (in this case, circled). Example:

```
   ---
1. |a| b c d
   ---

```

As you can see, this is question 1 with answer choice `a` selected since it has a box around it. For the challenge, you will be given a scan-tron with `n` questions ( `1 <= n <= 10`) with only four answers denoted as `a`, `b`, `c`, or `d`. The answer key will be given as a string with no spaces and with all lowercase. Example scan-tron with answer key:

```
Scan-tron
   ---
1. |a| b c d
   ---
     ---
2. a |b| c d
     ---
       ---
3. a b |c| d
       ---

Answer Key
abb

```

You can take in the answer key and scan-tron as separate inputs or in a chosen order as long they can be identified (i.e the answer key is separated from the scan-tron). Scores will be rounded to the nearest tenth of a point. Example output for the above:

```
Score: 66.7
Missed #: 3

```

Other acceptable answer would be:

```
66.7
3

```

or if multiple questions are missed

```
66.7
3 4 5

```

as long the question numbers for those missed are separated from the by spaces and not on the same line as the score.

**Rules and Specs**

* The scan-tron can be inputted as a multi-line string or one question at a time (as a string with newlines is acceptable)
* Given a scan-tron and answer key, you must output the score on one line and the question(s) missed on another, with the numbers separated by spaces. If no questions are missed, no question numbers should be outputted
* Scores are rounded to the nearest tenth
* Selected answers are surrounded by this box:

```
---
| |
---

```
* On the scan-tron, every question takes three spaces (the top and bottom of the box takes two extra lines)
* Must work for the above example
* Assume that there will always be only one answer boxed

**Winning Criteria**

Shortest code wins!

# Answer
# 05AB1E, 43 bytes

```
U|3ôø`\vyy'|k>èXNèQˆ}¯OXg/3°*2z+ïT/XgL¯_Ï‚»

```

Try it online!

**Explanation**

```
U                                            # store the answer key in X
 |3ô                                         # split the question-rows in chunks of 3
    ø`                                       # zip and flatten
      \                                      # discard top of stack, leaving the list of
                                             # answer rows on top
       v                                     # for each answer row
         y'|k                                # get the index of the first "|"
        y    >è                              # get the character after that from the row
               XNèQ                          # compare it to the corresponding entry in
                                             # the answer key
                   ˆ                         # add it to the global list
                    }                        # end loop
                     ¯O                      # calculate the number of correct answers
                       Xg/                   # divide by the length of the answer key
                          3°*                # multiply by 1000
                             2z+             # add 0.5
                                ï            # convert to integer
                                 T/          # divide by 10
                                   XgL       # push range [1 ... len(answer key)]
                                      ¯_Ï    # keep only numbers corresponding to
                                             # wrong answers
                                          ‚» # format output

```
> 2 votes

# Answer
# Stacked, 68 + 1 = 69 bytes

```
'|'split[#'1-]NO neq::size:@z~>*[]YES' '#`out is0 sum z/100*1 nround

```

Try it online! +1 for `-p` flag (this script can be executed as `stacked -pe "..."`)

Takes two inputs from the top of the stack.

Some interesting features:

```
[#'1-]NO
[    ]NO   do not keep members where
 #'          its length
   1-          -1
             is truthy (in this case, not equal to zero).

```

This yields all letters surrounded by pipes.

```
:size:@z~>*[]YES
:                 duplicate indices of incorrect answers
 size             length of incorrect answers
     :@z          (stored into z)
        ~>        range from 1 to this length
          *       and multiply by this range
           []YES  keep truthy elements

```

This gives us all incorrect question numbers.
> 4 votes

# Answer
# Python 2, ~~94~~ 93 bytes

<sup>-1 byte thanks to L3viathan</sup>

```
s,a=input()
l=len(s)
w=[i+1for i in range(l)if"|%s|"%a[i]not in s[i]]
print(l-len(w))*1e2/l,w

```

Try it online!
> 3 votes

# Answer
# Pip, ~~49~~ ~~46~~ ~~44~~ ~~48~~ 45 bytes

Ugh, that rounding takes so many bytes... 44 bytes of code, +1 for `-s` flag.

```
(/2+m-m/#b*#P_FI{++nbNa?un}MZa@`\|..`b)//1/t

```

Takes input as command-line arguments (the scan-tron page will need quoting and escaping of newlines if you run it from an actual command line). Outputs the missed questions first, then the score. Try it online!

### Explanation

I'm gonna do this in two parts: the incorrect questions list and the score.

```
P_FI{++nbNa?un}MZa@`\|..`b
                            a,b are cmdline args, u is nil, n is newline (implicit)
                            Note that a string like n, in math contexts, is equivalent to 0
                 a@`\|..`   Find all occurrences in a of | followed by 2 chars
                            Because regex matches don't overlap, this does what we need
    {         }MZ        b  Zip with b and map this function to each pair of items:
     ++n                     Increment n (so the first time through, it's 1)
        bNa                  Is 2nd arg a substring of 1st?
           ?un               If so, return nil; if not, return n
                            Now we have a list containing nil for correct questions
                            and the question number for incorrect questions
 _FI                        Filter on identity function (keep only truthy values)
P                           Print, joining on spaces (-s flag)

(/2+m-m/#b*#...)//1/t
                       a,b are cmdline args, m is 1000 (implicit)
            ...        The code from the first part
           #           Length of that list (i.e. number of incorrect questions)
      m/#b*            Times 1000/(number of questions)
    m-                 Subtracted from 1000
 /2+                   Plus 1/2 (= 0.5)
                       We now have a number like 667.1666666666667
(              )//1    Int-divide by 1 to truncate
                   /t  and divide that by 10
                       Print (implicit)

```
> 3 votes

# Answer
## JavaScript (ES6), 88 bytes

```
x=>y=>x.replace(/\w(?=\|)/g,c=>c==y[i++]?t++:a+=i+" ",a=i=t="")&&(t/i*1e3+.5|0)/10+`
`+a

```

I could save 5 bytes by using commas and returning everything one one line:

```
x=>y=>x.replace(/\w(?=\|)/g,c=>c==y[i++]?t++:a+=[,i],a=i=t="")&&(t/i*1e3+.5|0)/10+a

```
> 1 votes

# Answer
## Batch, 242 bytes

```
@echo off
set/as=c=0
set m=
set/pk=
:l
set/ac+=1
set/pt=
set/pl=
set/pt=
set "l=%l:*|=%
if %l:~,1%==%k:~,1% (set/as+=1)else set m=%m% %c%
set k=%k:~1%
if not "%k%"=="" goto l
set/as=(s*2000/c+1)/2
echo(%s:~,-1%.%s:~-1%
echo(%m%

```

Reads in the answer key on STDIN first, then `n*3` question rows. Note: Score is printed without a leading zero if it is less than `1.0`. Missed answers are printed with a leading space.
> 1 votes

# Answer
# CJam, ~~47~~ 45 bytes

```
lqN/(;3%_'|f#:).=.=__:+\,d/e2XmOn:!_,,:).*0-p

```

Try it online!

**Explanation**

The program is in three main parts:

```
Right/wrong list

l                    e# Read the first line of input (answer key)
 qN/                 e# Read the rest of the input and split it on newlines
    (;3%             e# Delete the first line, then select every 3rd line
        _            e# Duplicate the array
         '|f#        e# Find the index of the first | in each answer
             :)      e# Increment each, gives the index of the selected letter for each answer
               .=    e# Vectorized get-element-at with the answer strings
                 .=  e# Vectorized equality check with the answer key

```

After this section, we have an array of `0`s and `1`s, where `0` indicates a wrong answer and `1` a right answer.

```
Score

__              e# Duplicate the right/wrong list twice
  :+            e# Take the sum of it (number of right answers)
    \,          e# Swap top elements and take the length (total number of questions)
      d/        e# Divide (casting to double so it's not integer division)
        e2      e# Multiply by 10^2
          XmO   e# Round to 1 decimal place
             n  e# Pop and print with a newline

```

After this section, the stack contains only the right/wrong list, and the percentage score has been output.

```
Wrong answers

:!            e# Logically negate each element of the right/wrong list
  _,,:)       e# Generate the inclusive range 1...length(list)
       .*     e# Vectorized multiplication of the two lists
         0-   e# Remove any 0s from the result
           p  e# Print it

```
> 0 votes

# Answer
# Jolf, 46 bytes

I can't seem to break 46 bytes. I have two solutions of this length. Try one here!

```
ΆRγψ~mΖ mi«\|..»d?=€H.xSEhSdHήSmX*~1/-lζlγlζ_1

```

(Replace  with `0x7f` in the next one)

```
ΆRγψΜΖψGi'|d=1lHd?□=H.xShSEdHήSmX*~1/-lζlγlζ_1

```

In either case, 15 bytes for rounding: `mX*~1/-lζlγlζ_1`. They are, for the most part, the same, except one uses a regex match to get the results, and the other splits on pipes.
> 0 votes

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


title: Good Vibrations

text:
# Question
Title: Good Vibrations
The sound of the theremin has been immortalized in The Beach Boys song *Good Vibrations*. Many also associate its sound with the theme for the original series of *Star Trek*, though apparently it was a soprano's emulation.

This challenge requires you to implement a theremin.

# Input

* Take 2 dimensional input from a mouse or other input device (e.g. you could use a joystick), which will produce a tone from an audio output device as follows:
    + increasing x will increase the frequency of the tone. Note that frequency increases exponentially with musical note, so you must implement a linear relationship between mouse x position and the musical note, and
    + increasing y will increase the volume of the tone.
* There appears to be confusion regarding the waveform produced by a real theremin, so for simplicity, a sine wave (or close approximation thereof) must be used.

# Rules

* The tone produced must have at least a 2-octave range. More range is acceptable. A-440 must lie within the range.
* In order to create the audible appearance of continuously variable frequency and amplitude, the range of values considered in both dimensions from the input device must be at least 500 Implementations may open a window (at least 500x500 pixels) to read input from mouse cursor position. Or without opening a window, coordinates may be read directly from the mouse or other input device.
* There must be a simple means to stop the program - key-combination, mouse-click or other common input device. CTRL-c is sufficient.
* Any standard libraries may be used, as long as they do not totally implement the solution with no other work required.
* Standard rules for Code Golf and I/O
* You may stop by having the mouse or input device lose focus on the input box.

## Notes

* Because the output tone is dynamically-generated, care must be take to ensure the tone is a continuous waveform; that is there are no audible clicks or pops caused by sudden changes of phase or amplitude.
* You may limit the input size zone to 500 by 500 but it may be bigger.

This is , so the shortest answer in any language wins.

## Special thanks

Special thanks to Digital Trauma for making this challenge and posting it in the Secret Santa's Sandbox. I have made a few edits and here is the original post.

# Answer
> 10 votes
# JavaScript ES6, ~~215~~ 188 bytes

This seems to work well in Chrome and Edge. Firefox and Safari not so much.

```
with(new AudioContext)o=createOscillator(onmousemove=e=>{o.frequency.value=9/innerWidth*e.x**2,v.gain.value=1-e.y/innerHeight}),v=createGain(),v.connect(destination),o.start(),o.connect(v)

```

Saved 27 bytes thanks to @darrylyeo

### Try it online!

```
with(new AudioContext)o=createOscillator(onmousemove=e=>{o.frequency.value=9/innerWidth*e.x**2,v.gain.value=1-e.y/innerHeight}),v=createGain(),v.connect(destination),o.start(),o.connect(v)
```

```
<button onClick="o.stop()">Stop</button>
```

---
Tags: code-golf, music
---


title: Make Some Snow!

text:
# Question
Title: Make Some Snow!
Your task: generate a Koch snowflake to the nth depth. You do not need to make a complete Koch snowflake, just one side of the starting triangle. Wikipedia on Koch flakes: https://en.wikipedia.org/wiki/Koch\_snowflake.

**Rules:**

* The program must generate one side of the Koch snowflake to the nth depth.
* Output must be ASCII.
* You **may** generate the whole snowflake; this is not required.
* Standard rules for input/output and loopholes and stuff apply.
* Whitespace does not matter, as long as it all characters are in the right place relative to each other.
* Shortest code wins!

**Test cases:**

n=0:

```
__

```

n=1:

```
__/\__

```

n=2:

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

```

n=3:

```
                        __/\__
                        \    /
                  __/\__/    \__/\__
                  \                /
                  /_              _\
                    \            /
      __/\__      __/            \__      __/\__
      \    /      \                /      \    /
__/\__/    \__/\__/                \__/\__/    \__/\__

```

I hope this makes sense. Notice that in each test case, the fractal can be divided into three parts equal in length. Also notice that the width of each snowflake is three times the width of the previous generation of the snowflake.

# Answer
# Haskell, ~~308~~ ~~300~~ 299 bytes

Edits:

* -4 bytes: Changing `zipWith(+)` to `zipWith(-)` and adjusting encodings and offsets got rid of every negation sign.
* -1 byte: Further tweaking the encoding allowed several variable names in `#` to be dropped by using `r=reverse` instead of direct pattern matching.
* -2 bytes: Using an operator instead of alphanum for `zipWith(-)`.
* -1 byte: Defining `o=[0,0]` to shorten list constants.
* -1 byte: Merging two branches of `?`.

```
import Data.List
k n=0?sort(o#(f=<<scanl1(+)(iterate(>>=(:[1,4,1]))[6]!!n)))
x?l@(([_,w],c):r)|x>w='\n':0?l|0<1=([2..w-x]>>" ")++[c|w>x]++w?r
_?_=""
w#((c,l):m)=(l&w,c):r l&(l&w)#m
_#_=[]
f x=zip"_/\\_/\\"([id,r]<*>[0:1:o,[0,1,0,1],o++[1,1]])!!mod x 6<$[1,3..gcd 3x]
(&)=zipWith(-)
r=reverse
o=[0,0]

```

Try it online! (Sadly, anything bigger than n=3 gets horribly wrapped and unreadable, but you can copy it to another program to see it.)

**Variations**

* If you change `[6]` into `[6,4,4]`, you get a whole snowflake. Try it online!
* If you remove `,3..gcd 3x`, you get a curve in the style that this question was originally given with. Try it online!
* Or both at once: Try it online!

# How it works

* `k` is the main function, it takes an `Int` `n` and returns a `String`.
* `iterate(>>=(:[1,4,1]))[6]` generates an infinite list containing, for each n, the *turns* between consecutive lines in that curve iteration, turtle graphics style, as numbers nominally between `0` and `5`. Each iteration is just the previous one with the turns `1,4,1` interleaved. The only reason the sublists start out with `6` instead of `0` is to make the `gcd` trick in `f` work by avoiding `f 0`.
* `scanl1(+)` converts the turns into "absolute" directions, up to modulo 6. A `0` means rightwards, then each higher number is 60 degrees counterclockwise from the previous. (Well, it would be 60 degrees if this was a proper drawing rather than ASCII.)
* `f` converts an absolute direction into a list of (character, offset encoding) pairs that encodes which characters to add to the curve (for horizontal directions it generates two pairs, otherwise one), and how the relative position changes.
* The `#` operator iterates through the previous list of (character, offset encoding) pairs, generating actual (coordinate,character) pairs.
* Encoding principles:
    + A character from `_/\` nominally represents a line drawn from a starting corner through a rectangular cell to a different ending corner.
    + Cell coordinates are of the form `[y,x]`, top to bottom, left to right, so that they sort in the order we want to print them. Columns are 1-based. Lists are used instead of tuples for shorter vector arithmetic with `(&)=zipWith(-)`.
    + A corner is denoted with the same coordinates `[y,x]` as the cell to its upper left. This ensures that all offsets from a corner to its neighboring cells are nonnegative, avoiding negative constants.
    + However, *corner* coordinates are passed around negated to allow all vector operations to be subtractions instead of additions, which avoids all other explicit signs.
    + An offset encoding list is `[y1,x1,x2,y2]` where `[y1,x1]` is the coordinate offset from the starting corner to the character cell and `[y2,x2]` is the offset from the end corner to the character cell. This means:
        - The encoding lists for the directions `3`..`5` are just the reverse of the lists for `0`..`2`, allowing them to be generated with `[id,r]<*>`.
        - All necessary vector arithmetic can be done by using `(&)=zipWith(-)` with either an encoding list or its reverse.
* After sorting the list of (coordinate, character) pairs, they are passed to `?`, which generates the final `String` from them.
    + In `x?l@(([_,w],c):r)` `x` is the x-coordinate of the previous character shown on this line, or `0` if at the start of a line; `l` is the whole current list, `w` is the x-coordinate of the next character to be added, `c` is the character, and `r` is the remaining list.
    + At this stage the y-coordinates are no longer needed. Because every line contains characters, and every line's first character is well to the left of the end of the previous one, the start of new lines is detected by checking if the x-coordinate has decreased.
    + Underscore has a larger ASCII value than `\` and `/`, so it gets sorted last if it overlaps with another character in the same position. Thus a redundant underscore is detected by checking that an x-coordinate has been repeated.
> 10 votes

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


title: Ruby on Rails (or Trackety Track)

text:
# Question
Title: Ruby on Rails (or Trackety Track)
You are Ruby, a railway engineer. Your task is to lay track in any given valley such that it visits every station (`M`). The amount of track laid is not important, but it must be laid in one continuous path which starts and ends at the valley entrance/exit point (`>`) and does not, at any point cross itself. There are a few other constraints: mountains(`^`) are impassable so you must go around them, rivers(`~`) must be crossed using a bridge(`X`), and the edge of the valley (`#`) is also impassable.

**The Rules of the Track**

If track is not laid properly there will be derailments and nobody wants that, so here are the rules over track placement.

There are four kinds of track: `-` `|` `/` `\`.
Here's how each one may be combined with the others:

Allowed combinations from `-` (in the centre of each example):

```
#####  #####  #####  #####  #####  #####  #####
#   #  #   #  #\  #  #   #  #  /#  #\ /#  #   #
#---#  # --#  # --#  #-- #  #-- #  # - #  # - #
#   #  #/  #  #   #  #  \#  #   #  #   #  #/ \#
#####  #####  #####  #####  #####  #####  #####

```

`-` may never be combined with `|`. This is too sharp a turn for the trains to make safely.

Allowed combinations from `/` (in the centre of each example):

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

```

`\` may never be combined with `/`. This is too sharp a turn for the trains to make safely.

Allowed combinations from `\` (in the centre of each example):

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

```

Allowed combinations from `|` (in the centre of each example):

```
#####  #####  #####  #####  #####  #####  #####
# | #  #\  #  #  /#  # | #  # | #  #  /#  #\  #
# | #  # | #  # | #  # | #  # | #  # | #  # | #
# | #  # | #  # | #  #/  #  #  \#  #  \#  #/  #
#####  #####  #####  #####  #####  #####  #####

```

Tracks may combine with the stations, bridges and valley entrance/exit in the following ways:

```
#####  #####  #####
#\|/#  #\|/#  #/  #
#-M-#  #-X-#  >-  #
#/|\#  #/|\#  #\  #
#####  #####  #####

```

Stations have turn-tables, so it's permissible to leave a station at a sharp angle (though not back the way you came - you wouldn't want to crash into the next scheduled train coming the other way!).
Bridges are for crossing rivers so you must exit the bridge on the opposite side of the river that you entered it.

## Input

Input will be via STDIN for programs or a function argument for functions. If your function needs a name in order for me to run it on my input then that name declaration should be included in the byte count.

The input will be a **single** string with line-breaks. Each line within your input will always be the same length as the others, giving you a rectangular input. The edge of the input will always be solid and impassable (`#`) except for the point of entry. Any given input will have at least one valid answer.

## Output

Your output should be returned as a **single** string with line-breaks from a function, or printed/echoed to the screen for full programs.

The output should be the same as the input but with the track characters added.

## Scoring

Winner will be the shortest code in bytes.

## Test cases

```
###########
#    M    #
#   ^     #
>  ^^  M  #
#    ^    #
#~~~~~~~~~#
# M       #
#     ^^  #
#        M#
###########

#################
#               #
#   M         M #
#       ^       #
#        ^ M    #
#~~~~~~~^       #
#               #
#   ^           #
#   M^          #
#    ^          #
> ^^^          M#
#               #
#        M      #
#################

###############
# M   ~       #
#     ~       #
>     ~    M  #
#     ~       #
#     ~       #
#     ~       #
###############

```

## Possible solutions to test cases

```
###########
# ---M    #
#/  ^ \   #
>  ^^  M  #
#\   ^ |  #
#~X~~~~X~~#
# M     \ #
#  \  ^^ |#
#   -----M#
###########

#################
#               #
#   M---------M #
#   |   ^    /  #
#  /     ^ M-   #
#~X~~~~~^  |    #
# |         \   #
#  \^        \  #
# --M^        \ #
#/   ^         |#
> ^^^          M#
#\            / #
# -------M----  #
#################

###############
# M   ~       #
#/ \  ~       #
>   --X----M  #
#\    ~    |  #
# \   ~   /   #
#  ---X---    #
###############

```

# Answer
> 25 votes
# Python 2, ~~3990~~ ~~3430~~ ~~4412~~ 4313 bytes

This is a basically an A\* with a ugly heuristic and an ugly `getChildren` method. To run the 3 test cases consecutively takes `6.5s` on my machine. The function `f` is the solution here. It takes the map as a string and returns the solved map as a string.

```
from itertools import*
import sys
from Queue import*
A,B,C,D,E,F,G=">|\\/-MX";H=range;I=permutations;J=set;K=abs;L=len
class M:
	@staticmethod
	def T(a):return a in">|\\/-MX"
	@staticmethod
	def C(a,b,c,d,x,y,e):
		if not M.T(d)or not M.T(e):return 0
		if e in"MX"and d in"MX"and e!=d:return 1
		if d==A:return x>0 and(e==D and y==-1 or e==E and y==0 or e==C and y==1)
		if d==F:return e==C and K(x+y)==2 or e==D and x+y==0 or e==B and x==0 or e==E and y==0
		if d==G:
			if b!=0!=c and K(b-x)+K(c-y)==1:return 0
			return e==C and K(x+y)==2 or e==D and x+y==0 or e==B and x==0 or e==E and y==0
		if e!=""and e in"MX>"and a!=""and a in"MX>":return M.C("",0,0,a,-b,-c,d)and M.C("",0,0,e,-x,-y,d)
		elif e!=""and e in"MX>"and a!="":return M.C("",0,0,d,b,c,a)and M.C("",0,0,e,-x,-y,d)
		elif e!=""and e in"MX>"and a=="":return M.C("",0,0,e,-x,-y,d)
		elif a!=""and a in"MX>":return M.C("",0,0,a,-b,-c,d)and M.C("",0,0,d,x,y,e)
		f=[[E,-1,0,E,1,0,E],[D,-1,1,E,1,0,E],[C,-1,-1,E,1,0,E],[E,-1,0,E,1,1,C],[E,-1,0,E,1,-1,D],[C,-1,-1,E,1,-1,D],[D,-1,1,E,1,1,C],[D,-1,1,D,1,-1,D],[D,-1,1,D,1,-1,E],[D,-1,1,D,1,-1,B],[B,-1,1,D,1,-1,D],[E,-1,1,D,1,-1,D],[B,-1,1,D,1,-1,E],[E,-1,1,D,1,-1,B],[C,-1,-1,C,1,1,C],[C,-1,-1,C,1,1,E],[C,-1,-1,C,1,1,B],[B,-1,-1,C,1,1,C],[E,-1,-1,C,1,1,C],[B,-1,-1,C,1,1,E],[E,-1,-1,C,1,1,B],[B,0,-1,B,0,1,B],[C,-1,-1,B,0,1,B],[D,1,-1,B,0,1,B],[B,0,-1,B,-1,1,D],[B,0,-1,B,1,1,C],[D,1,-1,B,1,1,C],[C,-1,-1,B,-1,1,D]];g=0;h=[a,b,c,d,x,y,e];j=[0,3][a==""]
		for k in f:
			l=1;m=1;n=[k[6],k[4],k[5],k[3],k[1],k[2],k[0]]
			for i in H(j,L(k)):
				if k[i]!=h[i]:l=0
				if n[i]!=h[i]:m=0
			if l or m:g=1
		return g
	def __init__(s,a):s.m=[list(x)for x in a.split("\n")]
	def __str__(s):return"\n".join(["".join(x)for x in s.m])
	def A(s):return str(s)
	def B(s):return L(s.m[0])
	def D(s):return L(s.m)
	def E(s):
		a=[]
		for y in H(1,s.D()-1):
			for x in H(1,s.B()-1):
				if s.J(x,y)==F and L(s.H(x,y, F))==0:a+=[(x,y)]
		return a
	def F(s):
		for y in H(s.D()):
			for x in H(s.B()):
				if s.J(x,y)==A:return(x,y)
	def G(s):
		a=0
		for y in H(0,s.D()-1):
			for x in H(0,s.B()-1):
				b=s.J(x,y)
				c=L(s.H(x,y,b))
				if b==A:
					if c==0:a=(x,y)
					c=0
				if c==1:return(x,y)
		if a!=0:
			return a
		raise ValueError()
	def J(s,x,y):return s.m[y][x]
	def K(s,x,y,b):
		a=[[i for i in row]for row in s.m];a[y][x]=b
		return"\n".join("".join(x)for x in a)
	def H(s,x,y,c):
		d=[];e=[]
		for a,b in J(I([-1,-1,0,1,1],2)):
			g=s.J(x+a,y+b)
			if M.T(g)and M.C("",0,0,c,a,b,g):e+=[[g,a,b]]
		if L(e)==1:return[e[0][0]]
		if L(e)==0:return[]
		for g,h in I(e,2):
			i,j,k=g;l,m,n=h;o=x + m;p=y + n
			if M.C(i,j,k,c,m,n,l):
				if l==F:
					if L(s.H(o,p,l))>=1:d+=[l]
				else:d+=[l]
		return d
	def I(s,x,y,a,b):
		if a==0 or b==0:return 0
		a=s.J(x+a,y);b=s.J(x,y+b)
		return(M.T(a)or a==F)and(M.T(b)or b==F)
class P:
	@staticmethod
	def A(x0,y0,x1,y1):return K(x0-x1)+4*K(y0-y1)
	def __init__(s,a,p,t=0,g=0):
		s.a=[];s.b=p;s.c=a;s.d=[a];s.e=t;s.f=g
		if p:s.d=p.d[:];s.d+=[a];s.e=p.e;s.f=p.f
		s.g=M(a);s.h=s.B()
	def __str__(s):return s.g.A()
	def B(s):
		a=0;b=1;c=0
		try:c=s.g.G()
		except:a=1
		d=s.g.E();e=s.g.F();g=[]
		if L(d)==0 and not a:g=P.A(c[0],c[1],e[0],e[1])+b
		elif L(d)==0 and a:return 0
		elif c:
			h,i=c
			for j in combinations(d,L(d)):
				k=0
				for x,y in j:k+=P.A(h,i,x,y);h,i=x,y
				g+=[k]
			g=min(g);g+=s.g.B()+s.g.D()+b
		else:return sys.maxint
		if g<1:return 0
		return g
	def C(s):
		try:a=s.g.G()
		except:s.a=[];return
		b=s.g.J(a[0],a[1]);c=("",0,0);e=(0,0)
		for x,y in J(I([-1,-1,0,1,1],2)):
			g,h=a[0]+x,a[1]+y;i=s.g.J(g,h)
			if M.T(i)and M.C("",0,0,i,x,y,b):c=(i,x,y)
			if i=="~":e=(x,y)
		for x,y in J(I([-1,-1,0,1,1],2)):
			g,h=a[0]+x,a[1]+y;i=s.g.J(g,h)
			if not(i in"^#"or M.T(i)):
				for j in"-|\\/":
					if i=="~":
						j=G
						if c[0]==G:continue
					if c[0]==G and K(e[0])==1 and y==c[1]:continue
					if c[0]==G and K(e[1])==1 and x==c[0]:continue
					k=s.g.H(g,h,j);l=L(k)
					if(l==1 or l==2 and A in k)and M.C(c[0],c[1],c[2],b,x,y,j)and not s.g.I(a[0],a[1],x,y):
						try:s.a+=[P(s.g.K(g,h,j),s)]
						except:pass
def f(x):
	d=[];a=[];b=PriorityQueue();b.put((0,P(x,0)))
	while not d and b.qsize():
		c=b.get()[1];c.C();a+=[c.c]
		for e in c.a:
			if e.c not in a:
				if not e.h:d=e.d
				b.put((e.h,e))
	return d[-1]

```

Try it online!

## Test Cases

### Test 1

```
###########
# ---M    #
#/  ^ \   #
>  ^^  M  #
#\   ^ |  #
#~X~~~~X~~#
# M    |  #
#  \  ^^\ #
#   -----M#
###########

```

---

### Test 2

```
#################
#               #
#   M---------M #
#  /    ^    /  #
# |      ^ M-   #
#~X~~~~~^   \   #
# |          |  #
#  \^        |  #
# --M^       |  #
#/   ^-       \ #
> ^^^/ \       M#
#\  /   \     / #
# --     M----  #
#################

```

---

### Test 3

```
###############
# M   ~       #
#/ \  ~       #
>   --X----M  #
#\    ~   /   #
# ----X---    #
#     ~       #
###############

```

---

## Source Code

### A\* State + A\* Solver Class

I actually golfed these out of my solution. But they exist in my *'readable'* version. The State class is generic and meant to be implemented. The Solver class takes a start state and then follows that states heuristic `getDist`.

```
from Queue import PriorityQueue

# A* State
class State(object):
    # The type of value should be a primative
    def __init__(self, value, parent, start=0, goal=0):
        self.children = []
        self.parent = parent
        self.value = value
        self.dist = 0
        if parent:
            self.path = parent.path[:]
            self.path.append(value)
            self.start = parent.start
            self.goal = parent.goal
        else:
            self.path = [value]
            self.start = start
            self.goal = goal

    # Implement a heuristic for calculating the distance from this state to the goal
    def getDist(self):
        pass

    # Implement a way to create children for this state
    def createChildren(self):
        pass

# A* Solver
# Note: if maxmin = 1: Solver tries to minimize the distance
#       if maxmin = -1: Solver tries to maximize the distance
class AStar_Solver:
    def __init__(self,startState,maxmin=1):
        self.path = []
        self.visitedQueue = []
        self.priorityQueue = PriorityQueue()
        self.priorityQueue.put((0,startState))
        self.startState = startState
        self.maxmin = maxmin
        self.count = 0

    # Create a png of the string 'qPop'
    def imager(self,qPop):
        # Imager(qPop,str(self.count).rjust(5,"0")+".png")
        # print str(qPop)+"\n"
        self.count += 1

    # Solve the puzzle
    def solve(self):
        while(not self.path and self.priorityQueue.qsize()):
            closestChild = self.priorityQueue.get()[1]
            self.imager(str(closestChild))
            closestChild.createChildren()
            self.visitedQueue.append(closestChild.value)
            for child in closestChild.children:
                if child.value not in self.visitedQueue:
                    if not child.dist:
                        self.imager(str(child))
                        self.path = child.path
                        break
                    self.priorityQueue.put((self.maxmin*child.dist,child))
        if not self.path:
            print "Goal was not reachable"
        return self.path

```

### State Class

This is the implementation of the A\* state class. The most important method here is `getDist`, it is the heuristic for determining how close `self` is to the goal. It is basically the minimum distance to visit all the remaining destinations and get back to start.

```
from A_Star import State,AStar_Solver
from Ruby_Map import Map
from itertools import combinations, permutations
import sys

# A state class designed to work with A*
class State_Pathfinder(State):

    # This is deprecated
    @staticmethod
    def toValue(location):
        return str(location[0])+","+str(location[1])

    # Calculate the weighted distance between 2 points.
    # Not sure why the deltaY is more weighted. My theory
    # is that it is because the starting point is always
    # on a side. So vertical space is most precious?
    @staticmethod
    def distance(x0,y0,x1,y1):
        # return (abs(x0-x1)**2+abs(y0-y1)**2)**.5
        return 1*abs(x0-x1)+4*abs(y0-y1)

    def __init__(self, maps, parent, value=0, start=0, goal=0):
        super(State_Pathfinder,self).__init__(maps,parent,start,goal)
        self.map = Map(maps)
        self.dist = self.getDist()
        if not value:
            location = self.map.getLocation()
            self.value = maps
            self.path = [self.value]

    def __str__(self):
        return self.map.getDisplay()

    # The heuristic function that tells us
    # how far we are from the goal
    def getDist(self):
        blownup = False
        WEIGHT = 1
        location = None
        try:
            location = self.map.getLocation()
        except ValueError as e:
            blownup = True
        destinations = self.map.getDestinations()
        goal = self.map.getGoal()
        dist = []
        if len(destinations) == 0 and not blownup:
            dist = State_Pathfinder.distance(location[0],location[1],goal[0],goal[1])+WEIGHT
        elif len(destinations) == 0 and blownup:
            return 0
        elif location:
            oldX,oldY = location
            for path in combinations(destinations,len(destinations)):
                length = 0
                for pair in path:
                    x,y = pair
                    length += State_Pathfinder.distance(oldX,oldY,x,y)
                    oldX,oldY = x,y
                dist.append(length)
            dist = min(dist)
            dist += self.map.getWidth()+self.map.getHeight()+WEIGHT
        else:
            return sys.maxint
        if dist<1:
            return 0
        return dist

    # Creates all possible (legal) child states of this state
    def createChildren(self):
        if not self.children:
            try:
                location = self.map.getLocation()
            except:
                self.children = []
                return
            track = self.map.get(location[0],location[1])
            intrack = ("",0,0)
            river = (0,0)
            for x,y in set(permutations([-1,-1,0,1,1],2)):
                realX,realY = location[0]+x,location[1]+y
                adjacent = self.map.get(realX,realY)
                if Map.isTrack(adjacent) and Map.isConnected("",0,0,adjacent,x,y,track):
                    intrack = (adjacent,x,y)
                if adjacent=="~":
                    river = (x,y)
            for x,y in set(permutations([-1,-1,0,1,1],2)):
                realX,realY = location[0]+x,location[1]+y
                adjacent = self.map.get(realX,realY)
                if not Map.isBlocking(adjacent) and not adjacent in "M":
                    for outtrack in "-|\\/":
                        if adjacent=="~":
                            outtrack="X"
                            if intrack[0]=="X":continue
                        if intrack[0]=="X" and abs(river[0])==1 and y==intrack[1]:continue
                        if intrack[0]=="X" and abs(river[1])==1 and x==intrack[0]:continue
                        connections = self.map.getConnections(realX,realY,outtrack)
                        hoppin = len(connections)
                        connected = Map.isConnected(intrack[0],intrack[1],intrack[2],track,x,y,outtrack)
                        blocked = self.map.isBlocked(location[0],location[1],x,y)
                        if (hoppin==1 or hoppin==2 and ">" in connections) and connected and not blocked:
                            try:
                                maps = self.map.set(realX,realY,outtrack)
                                value = State_Pathfinder.toValue((realX,realY))
                                child = State_Pathfinder(maps,self,value)
                                self.children.append(child)
                            except ValueError as e:
                                print "Bad kid"
                                print e

# The solution function. Takes a map string
# and returns a map string.
def f(mapX):
    a = AStar_Solver(State_Pathfinder(mapX,0))
    a.solve()
    print a.path[-1]

if __name__ == "__main__":

    map1 = """###########
#    M    #
#   ^     #
>  ^^  M  #
#    ^    #
#~~~~~~~~~#
# M       #
#     ^^  #
#        M#
###########"""

    map2 = """#################
#               #
#   M         M #
#       ^       #
#        ^ M    #
#~~~~~~~^       #
#               #
#   ^           #
#   M^          #
#    ^          #
> ^^^          M#
#               #
#        M      #
#################"""

    map3 = """###############
# M   ~       #
#     ~       #
>     ~    M  #
#     ~       #
#     ~       #
#     ~       #
###############"""

    f(map3)
    f(map2)
    f(map1)

```

### Map Class

This class stores and processes the map. The `isConnected` method is probably the most important piece. It tests to see if 2 pieces of track are connected.

```
from itertools import permutations,combinations

# A map class designed to hold string map
# the specification is found here:
# http://codegolf.stackexchange.com/questions/104965/ruby-on-rails-or-trackety-track
class Map(object):

    # Is 'track' part of the railroad?
    @staticmethod
    def isTrack(track):
        return track in ">|\\/-MX"

    # Can I not build on this terrian?
    @staticmethod
    def isBlocking(terrian):
        return terrian in "^#" or (Map.isTrack(terrian) and not terrian=="M")

    # Are these 3 consecuative tracks connected in a legal fashion?
    @staticmethod
    def isConnected(inTerrian,relativeXin,relativeYin,centerTerrian,relativeXout,relativeYout,outTerrian):
        tin = inTerrian
        xin = relativeXin
        yin = relativeYin
        x = relativeXout
        y = relativeYout
        tout = outTerrian
        center = centerTerrian

        if not Map.isTrack(center) or not Map.isTrack(tout):
            return False

        if tout in "MX" and center in "MX" and tout!=center:
            return True

        if center == ">":
            return x>0 and (\
                tout == "/" and y == -1 or \
                tout == "-" and y == 0 or \
                tout == "\\" and y == 1 \
                )

        if center == "M":
            return tout == "\\" and abs(x+y) == 2 or \
                tout == "/" and x+y == 0 or \
                tout == "|" and x == 0 or \
                tout == "-" and y == 0

        if center == "X":
            if xin!=0!=yin and abs(xin-x)+abs(yin-y) == 1:
                return False
            return tout == "\\" and abs(x+y) == 2 or \
                tout == "/" and x+y == 0 or \
                tout == "|" and x == 0 or \
                tout == "-" and y == 0

        if tout!="" and tout in "MX>" and tin!="" and tin in "MX>":
            return Map.isConnected("",0,0,tin,-xin,-yin,center) and Map.isConnected("",0,0,tout,-x,-y,center)
        elif tout!="" and tout in "MX>" and tin!="":
            return Map.isConnected("",0,0,center,xin,yin,tin) and Map.isConnected("",0,0,tout,-x,-y,center)
        elif tout!="" and tout in "MX>" and tin=="":
            return Map.isConnected("",0,0,tout,-x,-y,center)
        elif tin!="" and tin in "MX>":
            return Map.isConnected("",0,0,tin,-xin,-yin,center) and Map.isConnected("",0,0,center,x,y,tout)

        allowed = [ \
            ["-",-1,0,"-",1,0,"-"], \
            ["/",-1,1,"-",1,0,"-"], \
            ["\\",-1,-1,"-",1,0,"-"], \
            ["-",-1,0,"-",1,1,"\\"], \
            ["-",-1,0,"-",1,-1,"/"], \
            ["\\",-1,-1,"-",1,-1,"/"], \
            ["/",-1,1,"-",1,1,"\\"], \

            ["/",-1,1,"/",1,-1,"/"], \
            ["/",-1,1,"/",1,-1,"-"], \
            ["/",-1,1,"/",1,-1,"|"], \
            ["|",-1,1,"/",1,-1,"/"], \
            ["-",-1,1,"/",1,-1,"/"], \
            ["|",-1,1,"/",1,-1,"-"], \
            ["-",-1,1,"/",1,-1,"|"], \

            ["\\",-1,-1,"\\",1,1,"\\"], \
            ["\\",-1,-1,"\\",1,1,"-"], \
            ["\\",-1,-1,"\\",1,1,"|"], \
            ["|",-1,-1,"\\",1,1,"\\"], \
            ["-",-1,-1,"\\",1,1,"\\"], \
            ["|",-1,-1,"\\",1,1,"-"], \
            ["-",-1,-1,"\\",1,1,"|"], \

            ["|",0,-1,"|",0,1,"|"], \
            ["\\",-1,-1,"|",0,1,"|"], \
            ["/",1,-1,"|",0,1,"|"], \
            ["|",0,-1,"|",-1,1,"/"], \
            ["|",0,-1,"|",1,1,"\\"], \
            ["/",1,-1,"|",1,1,"\\"], \
            ["\\",-1,-1,"|",-1,1,"/"] \
        ]

        passing = False
        forward = [tin,xin,yin,center,x,y,tout]
        start = [0,3][tin==""]

        for allow in allowed:
            maybeF = True
            maybeB = True
            backallowed = [allow[6],allow[4],allow[5],allow[3],allow[1],allow[2],allow[0]]
            for i in range(start,len(allow)):
                if allow[i]!=forward[i] and str(forward[i])not in"*":
                    maybeF = False
                if backallowed[i]!=forward[i] and str(forward[i])not in"*":
                    maybeB = False
            if maybeF or maybeB:
                passing = True
        return passing

    def __init__(self,mapString):
        self.indexableMap = [list(x) for x in mapString.split("\n")]

    def __str__(self):
         return "\n".join(["".join(x) for x in self.indexableMap])

    # Get the string representation of this map
    def getDisplay(self):
        return self.__str__()

    # Get map width
    def getWidth(self):
        return len(self.indexableMap[0])

    # Get map height
    def getHeight(self):
        return len(self.indexableMap)

    # Get unvisited destinations
    def getDestinations(self):
        destinations = []
        for y in xrange(1,self.getHeight()-1):
            for x in xrange(1,self.getWidth()-1):
                sigma = 2
                if self.get(x,y)=="M":
                    sigma = len(self.getConnections(x,y,"M"))
                    if sigma==0:
                        destinations.append((x,y))
        return destinations

    # Get the x,y of the goal (endpoint)
    def getGoal(self):
        for y in xrange(self.getHeight()):
            for x in xrange(self.getWidth()):
                if self.get(x,y)==">":
                    return (x,y)

    # Get the x,y of the current location
    def getLocation(self):
        location = None
        for y in xrange(0,self.getHeight()-1):
            for x in xrange(0,self.getWidth()-1):
                track = self.get(x,y)
                sigma = len(self.getConnections(x,y,track))
                if track == ">":
                    if sigma==0:
                        location = (x,y)
                    sigma = 0
                if sigma == 1:
                    return (x,y)
        if location != None:
            return location
        raise ValueError('No location found in map\n'+self.getDisplay())

    # Get the terrian at x,y
    def get(self,x,y):
        return self.indexableMap[y][x]

    # Set the terrain at x,y
    # (non-destructive)
    def set(self,x,y,value):
        newMap = [[i for i in row] for row in self.indexableMap]
        newMap[y][x] = value
        return "\n".join(["".join(x) for x in newMap])

    # Get the track connectioning to a piece of track at x,y
    def getConnections(self,x,y,track):
        connections = []
        tracks = []
        for a,b in set(permutations([-1,-1,0,1,1],2)):
            outtrack = self.get(x+a,y+b)
            if Map.isTrack(outtrack) and Map.isConnected("",0,0,track,a,b,outtrack):
                tracks+=[[outtrack,a,b]]
        if len(tracks)==1:return [tracks[0][0]]
        if len(tracks)==0:return []

        for inner,outer in permutations(tracks,2):
            intrack,relXin,relYin = inner
            other,relX,relY = outer
            ex = x + relX
            ey = y + relY
            if Map.isConnected(intrack,relXin,relYin,track,relX,relY,other):
                if other == "M":
                    if len(self.getConnections(ex,ey,other))>=1:
                        connections.append(other)
                else:
                    connections.append(other)
        return connections

    # Is could a piece of track at x,y build in
    # the direct of relX,relY?
    def isBlocked(self,x,y,relX,relY):
        if relX==0 or relY==0:
            return False
        side1 = self.get(x+relX,y)
        side2 = self.get(x,y+relY)
        return (Map.isTrack(side1) or side1=="M")  and (Map.isTrack(side2) or side2=="M")

```

---

## Updates

* **-560** \[17-03-31\] A bunch of basic regex golfing
* **+982** \[17-03-31\] Fixed illegal track laying. Thanks *@fəˈnɛtɪk*!
* **-99** \[17-03-31\] Utilized `;`s

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


title: Find the polynomial

text:
# Question
Title: Find the polynomial
We know that *f* is a polynomial with non-negative integer coefficients.

Given *f(1)* and *f(1+f(1))* return *f*. You may output *f* as a list of coefficients, an ASCII formatted polynomial, or similar.

Examples:

```
f(1)  f(1+f(1))  f
0     0          0
1     1          1
5     75         2x^2 + 3
30    3904800    4x^4 + 7x^3 + 2x^2 + 8x + 9
1     1073741824 x^30

```

# Answer
> 27 votes
# Jelly, 3 bytes

```
‘b@

```

Try it online!

Returns the polynomial as a list of coefficients.

Since we know the polynomial has non-negative integer coefficients, *f(b)* can be interpreted as "the coefficients of the polynomial, taken as base *b* digits," by the definition of a base. This is subject to the condition that none of the coefficients exceeds or is equal to *b*, but we know that, because *b* is one greater than the sum of the coefficients (which is *f(1)*).

The program simply increments the first argument () to get *1+f(1)*, then calls the base convertion atom (`b`) with the first argument as the base and the second argument as the number (using `@` to swap the order of the arguments, since `b` usually takes the number first and base second).

This was quite the clever challenge; thanks orlp!

# Answer
> 7 votes
# Mathematica, ~~29~~ 28 bytes

*Thanks to JungHwan Min for saving 1 byte! (ironically, with a `Max`)*

```
#2~IntegerDigits~Max[#+1,2]&

```

Pure function taking two nonnegative integers and returning a list of (nonnegative integer) coefficients. `#2~IntegerDigits~(#+1)` would be the same algorithm as in Doorknob's Jelly answer; unfortunately, Mathematica's `IntegerDigits` chokes when the base equals 1, hence the need for extra bytes `Max[...,2]`.

# Answer
> 4 votes
# Python 2, 38 bytes

```
a,b=input()
while b:print b%-~a;b/=a+1

```

Try it online!

---

outputs newline separated coefficients

Example output for `30, 3904800`:

```
9
8
2
7
4

```

=\> `9*x^0 + 8*x^1 + 2*x^2 + 7*x^3 + 4*x^4`

# Answer
> 3 votes
# VBA, 75 bytes

```
Sub f(b,n)
b=b+1
Do While n>0
s=n Mod b &" " &s
n=n\b
Loop
Debug.?s
End Sub

```

When it automatically formats, it looks like this:

```
Sub f(b, n)
    b = b + 1
    Do While n > 0
        s = n Mod b & " " & s
        n = n \ b
    Loop
    Debug.Print s
End Sub

```

The `\` operator is a floor divide

# Answer
> 2 votes
# Common Lisp, 87 bytes

```
(defun p(x y)(multiple-value-bind(q m)(floor y (1+ x))(if(= 0 q)`(,m)`(,m ,@(p x q)))))

```

Ungolfed:

```
(defun find-polynomial (f<1> f<1+f<1>>)
  (multiple-value-bind (q m)
      (floor f<1+f<1>> (1+ f<1>))
    (if (zerop q) `(,m)
      (cons m (find-polynomial f<1> q)))))

```

# Answer
> 1 votes
# AHK, 63 bytes

```
a=%1%
b=%2%
a+=1
While b>0
{s:=Mod(b,a) " "s
b:=b//a
}
Send,%s%

```

AutoHotkey assigns numbers 1-n as variable names for the incoming parameters. It causes some problems when you try to use those in functions because it thinks you mean the literal number 1 instead of the variable *named* 1. The best workaround I can find is to assign them to different variables.

# Answer
> 1 votes
# Java, 53 bytes

```
a->b->{while(b>0){System.out.println(b%-~a);b/=a+1;}}

```

Outputs a list of coefficients. Thanks to ovs for the maths.

The expression must be assigned to a `Function<Integer, IntConsumer>` and called by first `apply`ing the function, then `accept`ing the `int`. No imports are needed with Java 9's `jshell`:

```
C:\Users\daico>jshell
|  Welcome to JShell -- Version 9-ea
|  For an introduction type: /help intro

jshell> Function<Integer, IntConsumer> golf =
        a->b->{while(b>0){System.out.println(b%-~a);b/=a+1;}}
golf ==> $Lambda$14/13326370@4b9e13df

jshell> golf.apply(30).accept(3904800)
9
8
2
7
4

```

# Answer
> 0 votes
# C#, 62 bytes

```
(a,b)=>{var r="";a++;while(b>0){r+=(b%a)+" ";b/=a;}return r;};

```

---
Tags: code-golf, base-conversion, polynomials
---


title: Let's Play Hide and Seek!

text:
# Question
Title: Let's Play Hide and Seek!
The user will hide, and the computer will try to find them.

First, the program will take an input, for the size of the grid. Like 5x5, 10x10, 15x15, etc. The grid won't always be a perfect square.

The grid is sort of like a chessboard:

```
_______________________________
|     |     |     |     |     |
| A1  |     |     |     |     | A
|_____|_____|_____|_____|_____|
|     |     |     |     |     |
|     | B2  |     |     |     | B
|_____|_____|_____|_____|_____|
|     |     |     |     |     |
|     |     | C3  |     |     | C
|_____|_____|_____|_____|_____|
|     |     |     |     |     |
|     |     |     | D4  |     | D
|_____|_____|_____|_____|_____|
|     |     |     |     |     |
|     |     |     |     | E5  | E
|_____|_____|_____|_____|_____|
   1     2     3     4     5

```

Now, the user will pick a square, such as `B2` (without telling the computer)

The computer will start guessing squares. If it picks the correct square, the user will respond with `y`. If not, they will input the direction their tile is from the one picked (N, NE, E, SE, S, SW, W).

So if the user picked `B2`, and the computer guessed `C3`, the user would input `NW`.

Here is an example of the outputs and inputs:

```
Grid?
5x5

C3?
NW

C2?
N

B2?
y

```

# Scoring:

This will be scored a little differently than a normal challenge.

The winner is the program that takes lowest number of guesses (on average) it takes to guess the correct square. The test cases to be averaged will be all of the possible squares in a 5x5 and then in a 10x10.

However, it must also work with every pattern of grid up to 26 rows (i.e. 5x8, 6x2, 20x5, etc.).

Please include a way for it to be tested, such as a JSFiddle.

And lastly, in case of a tie, the shortest program wins.

# Answer
> 3 votes
# Python 3.6, ~~466~~ ~~398~~ 392 bytes, minimax

```
x, y = 1, 1
w, h = [int(x) for x in input('Grid?\n').split('x')]

def split_factor(a, b):
    N = b-y
    W = a-x
    S = h+~N
    E = w+~W
    return max(1, N, W, S, E, N*W, S*W, S*E, N*E)

def move(a, b):
    *Z, = zip([a, x, a, a+1, x, x, a+1, a+1],
              [y, b, b+1, b, y, b+1, b+1, y],
              [1, a-x, 1, w+x+~a, a-x, a-x, w+x+~a, w+x+~a],
              [b-y, 1, h+y+~b, 1, b-y, h+y+~b, h+y+~b, b-y])
    return Z[['N', 'W', 'S', 'E', 'NW', 'SW', 'SE', 'NE'].index(d)]

d = ''
while d != 'y':
    print()
    splits = {(a, b): split_factor(a, b) for a in range(x, x+w) for b in range(y, y+h)}
    a, b = min(splits, key=splits.get)
    d = input(f'{a}{"ABCDEFGHIJKLMNOPQRSTUVWXYZ"[b]}?\n')
    x, y, w, h = move(a, b)

```

Input and output should be in the form shown in the example. This finds the square with the minimal "split factor"--which is the largest remaining area that can result from the player's answer (i.e. NW, E, y, etc.)--and guesses that. Yes, that's always the center of the remaining area in this game, but this technique of minimizing the worst-case will work more generally in similar games with different rules.

Unreadable version:

```
x=y=d=1
w,h=map(int,input('Grid?\n').split('x'))
while d!='y':print();s={(a,b):max(b-y,h+y+~b)*max(w+x+~a,a-x)for a in range(x,x+w)for b in range(y,y+h)};a,b=min(s,key=s.get);d=input(f'{a}{chr(64+b)}?\n');*z,=zip([a+1,x,a+1,x,a,a,a+1,x],[b+1,b+1,y,y,b+1,y,b,b],[w+x+~a,a-x,w+x+~a,a-x,1,1,w+x+~a,a-x],[h+y+~b,h+y+~b,b-y,b-y,h+y+~b,b-y,1,1]);x,y,w,h=z[~'WENS'.find(d)or-'NWNESWSE'.find(d)//2-5]

```

# Answer
> 2 votes
# Mathematica, optimal behavior on test cases, 260 bytes

```
For[a=f=1;{c,h}=Input@Grid;z=Characters;t=<|Thread[z@#->#2]|>&;r="";v=Floor[+##/2]&;b:=a~v~c;g:=f~v~h,r!="y",r=Input[g Alphabet[][[b]]];{{a,c},{f,h}}={t["NSu",{{a,b-1},{b+1,c},{b,b}}]@#,t["uWX",{{g,g},{f,g-1},{g+1,h}}]@#2}&@@Sort[z@r/.{c_}:>{c,"u"}/."E"->"X"]]

```

This program can be tested by cutting and pasting the above code into the Wolfram Cloud. (Test quickly, though: I think there's a time limit for each program run.) The program's guesses look like `2 c` instead of `C2`, but otherwise it runs according to the spec above. The grid must be input as an ordered pair of integers, like `{26,100}`, and responses to the program's guesses must be input as strings, like `"NE"` or `"y"`.

The program keeps track of the smallest and largest row number and column number that is consistent with the inputs so far, and always guesses the center point of the subgrid of possibilities (rounding NW). The program is deterministic, so it's easy to compute the number of guesses it requires on average over a fixed grid. On a 10x10 grid, the program requires 1 guess for a single square, 2 guesses for eight squares, 3 guesses for 64 squares, and 4 guesses for the remaining 27 squares, for an average of 3.17; and this is the theoretical minimum, given how many 1-guess, 2-guess, etc. sequences can lead to correct guesses. Indeed, the program should achieve the theoretical minimum on any size grid for similar reasons. (On a 5x5 grid, the average number of guesses is 2.6.)

A little code explanation, although it's fairly straightforward other than the golfingness. (I exchanged the order of some initializing statements for expository purposes—no effect on byte count.)

```
1  For[a = f = 1; z = Characters; t = <|Thread[z@# -> #2]|> &;
2      v = Floor[+##/2] &; b := a~v~c; g := f~v~h;
3      r = ""; {c, h} = Input@Grid,
4    r != "y",
5    r = Input[g Alphabet[][[b]]];
6      {{a, c}, {f, h}} = {t["NSu", {{a, b - 1}, {b + 1, c}, {b, b}}]@#,
7        t["uWX", {{g, g}, {f, g - 1}, {g + 1, h}}]@#2} & @@
8        Sort[z@r /. {c_} :> {c, "u"} /. "E" -> "X"]
   ]

```

Lines 1-3 initialize the `For` loop, which actually is just a `While` loop in disguise, so hey, two fewer bytes. The possible row-number and column-number ranges at any moment is stored in `{{a, c}, {f, h}}`, and the centered guess in that subgrid is computed by the functions `{b, g}` defined in line 2. Line 3 initializes the max-row `c` and max-column `h` from user input, and also initializes `r` which is the loop-tested variable and also the subsequent user inputs.

While the test on line 4 is satisfied, line 5 gets input from the user, where the prompt comes from the current guess `{b, g}` (`Alphabet[][[b]]]` converts the row number to a letter). Then lines 6-8 update the subgrid-of-possibilities (and hence implicitly the next guess). For example, `t["NSu", {{a, b - 1}, {b + 1, c}, {b, b}}]` (given the definition of `t` on line 1) expands to

```
<| "N" -> {a, b - 1}, "S" -> {b + 1, c}, "u" -> {b, b}|>

```

where you can see the min-row and max-row numbers being updated according to the user's last input. Line 8 converts any possible input to an ordered pair of characters of the form `{ "N" | "S" | "u", "u" | "W" | "X"}`; here `"u"` stands for a correct row or column, and `"X"` stands for East (just to allow `Sort` to work nicely). When the user finally inputs `"y"`, these lines throw an error, but then the loop-test fails and the error is never propogated (the program simply halts anyway).

# Answer
> 0 votes
## Batch, divide-and-conquer

```
@echo off
set z = ABCDEFGHIJKLMNOPQRSTUVWXYZ
set /p g = Grid?
set /a w = 0, n = 0, e = %g :x= + 1, s = % + 1
:l
set /a x = (w + e) / 2, y = (n + s) / 2
call set c = %%z :~%y%,1%%
set /p g = %c %%x%?
if %g :w=.% == %g % set /a w = x
if %g :n=.% == %g % set /a n = y
if %g :e=.% == %g % set /a e = x
if %g :s=.% == %g % set /a s = y
if %g :y=.% == %g % goto l

```

Works by creating the bounding box of the the area still to be searched. The next guess is always the centre of the box. For those compass points that are not included in the response, the box is reduced in that direction. For example for a response of `N`, the left, right and bottom of the box are set to the guessed square.

At 369 bytes I'm not expecting to beat anybody so I've left the spaces in for readibility.

---
Tags: code-challenge, ai-player
---


title: running consecutive commands in bash

text:
# Question
Title: running consecutive commands in bash
Usually to run multiple commands consecutively one would do:

```
sudo apt update && sudo apt upgrade # 35 characters

```

I can't help but feel there's a neat trick to running these with less keystrokes, and you golfers here love challenges :)

I've found a ton of answers around various SE Sites related to running arguments to different commands or commands in parallel, but nothing like what I'm after.

I've come to achieve what I want a couple of ways, but it's way longer and more difficult to type:

```
 x=('update' 'upgrade') && for i in ${x[*]}; do sudo apt $i; done

```

I quickly shortened this to:

```
for x in update upgrade; do sudo apt $x; done

```

then

```
for x in update upgrade;do sudo apt $x;done # 43 characters

```

Using `bash`, what is a golfed way of achieving the above? shortest line wins

(this is my first post to the group, please be kind if I've used the wrong tags) ;)

edit: as pointed out my own loops don't exactly do what is in the question due to the `&&` being conditional on the first command not having an error (I do know this). There's also the fact that my loops (and the original command line without the `-y` switch) still requires user input to complete. An oversight. Time for some more explicit instructions.

My original thought was to have something like:

```
echo update upgrade | sudo apt

```

with the objective of just running one after the other.

In the interests of trying to open this up to other languages, let's expand it thusly:

Objectives:

* run both commands
* require no more than one additional keystroke by the user
* can outsource this to other other languages/scripts\*
* can be scripted if:

+ gracefully fails (error messages are ok, but it shouldn't try and execute anything else in error)
    + it's something commonly or "unobtrusively installable" in linux/ubuntu (I feel I may regret this line)
    + the script takes at least three arguments
    + 1. command to run
    + 2. argument 1
    + 3. argument 2
    + 4. argument n
    + or specified on the command line, (see next example)
    + in this second case, see the note below

    `./twice "sudo apt" update upgrade`

\*I have it in mind that someone could construct a cute little binary/script from a `printf`, but the essence is, if it can be run from an executable script, all characters of the script EXCEPT the first line (the shebang) count.

If I've totally messed this up, feel free to close. Cheers

# Answer
# 40 bytes

```
for a in ${@:2};do eval "${1} ${a}";done

```

Usage: `./[filename] "[primary command]" [arguments]`

Ex. `./twice "sudo apt" update upgrade` (Assumes 'twice' as file name)

Was this what you wanted?

*Note: Please golf me further if it is possible, and correct me if I'm wrong. This was my first bash entry.*
> 2 votes

# Answer
## 24 bytes

Interactively, you can reduce this to 24 keystrokes (plus root password)

```
su
apt update
^dat^grad

```

An abstract script starts at 25 bytes +boilerplate:

```
#!/bin/bash -e
for x in ${@:2}
{
$1 $x
}

```

or at 29 bytes:

```
printf "$1 %s
" ${@:2}|sh -e

```

as in

```
e(){ printf "$1 %s\n" ${@:2}|sh -e;}
e "sudo apt" up{dat,grad}e

```

For concrete one-liners, the 32 bytes of

```
sudo sh -ec apt\ up{dat,grad}e\;

```

are only 1 byte shorter than

```
sudo apt update&&sudo apt upgrade

```

or 3 bytes shorter than

```
e(){ sudo apt up$1e;};e dat&&e grad

```
> 1 votes

---
Tags: code-golf
---


title: Topple the sandpile

text:
# Question
Title: Topple the sandpile
<sup>(There are related questions about infinite sandpiles, and finding identity elements of sandpiles.)</sup>

Given a matrix of non-negative integers, return a matrix of the same dimensions, but *toppled*:

1. If the matrix doesn't contain any values larger than 4, return it.
2. Every "cell" that is larger than 3 gets reduced by 4, and all directly neighboring cells (above, below, left, and right) are incremented, if they exist.
3. GOTO 1.

### Examples:

```
0 1 0        0 2 0
2 4 0   ->   3 0 1
0 0 3        0 1 3

1 2 3    2 3 4    2 5 1    4 1 2    0 3 3    0 3 3    0 3 3
4 5 6 -> 2 4 4 -> 4 2 3 -> 0 5 4 -> 3 2 1 -> 3 3 1 -> 3 3 2
7 8 9    5 7 7    2 6 5    4 3 2    0 5 3    1 1 4    1 2 0

```

(You only need to return the final result. The path on which you reach it may differ from the one shown here: it doesn't matter in which order you perform the toppling operations, they all lead to the same result.)

For a deeper explanation and some motivation see this Numberphile video or the Wikipedia article on the Abelian sandpile model.

## Rules:

* You may take input and output in any of the standard ways
* Loopholes are forbidden
* Input and output may be:
    + a nested list: `[[1, 2, 3], [4, 5, 6], [7, 8, 9]]`
    + a simple list: `[1, 2, 3, 4, 5, 6, 7, 8, 9]` and the shape
    + some kind of native matrix type
    + a string, e.g. `1 2 3\n4 5 6\n7 8 9`
    + or whatever else works in your language.
* Input and output must be in the same form
* The input may contain larger numbers than the ones shown here, but the size may be bound by the limits of your language (MAXINT equivalents, if applicable)
* The matrix may have any shape (e.g. 1x1, 2x2, 3x3, 4x4, 2x7, 11x3, ...)
* You don't need to handle the case where the shape is 0xN or Nx0.

## Testcases

```
[[2, 5, 4], [8, 6, 4], [1, 2, 3]] -> [[3, 3, 0], [1, 2, 2], [1, 3, 2]]
[[0, 0, 2], [1, 3, 3], [0, 0, 0]] -> [[0, 0, 2], [1, 3, 3], [0, 0, 0]]
[[9, 9, 9], [9, 9, 9], [9, 9, 9]] -> [[1, 3, 1], [3, 1, 3], [1, 3, 1]]
[[4, 5], [2, 3]] -> [[2, 3], [0, 1]]
[[2, 3, 5], [2, 2, 0]] -> [[3, 0, 2], [2, 3, 1]]
[[7]] -> [[3]]

```

This is , the shortest code (per language) wins.

# Answer
> 8 votes
# MATL, 17 bytes

```
tss:"t3>t1Y6Z+w4*-+

```

Try it at MATL Online! Or verify all test cases.

### Explanation

The program iterates for as many times as the sum of the input. This is a loose upper bound on the required number of iterations.

For each iteration, entries in the sandpile matrix exceeding `3` are detected, giving a matrix of `1` and `0`, which is convolved with the 4-neighbour mask. The entries exceeding `3` in the sandpile matrix are reduced by `4`, and the result of the convolution is added.

For the last iterations, in which the sandpile matrix does not have any numbers exceeding `3`, zeros are subtracted from and added to it, so it is unaffected.

```
t       % Implicit input (matrix). Duplicate
ss      % Sum of matrix entries
:"      % Repeat that many times
  t     %   Duplicate
  3>    %   True for matrix entries that exceed 3
  t     %   Duplicate
  1Y6   %   Push predefined literal [0, 1, 0; 1, 0, 1; 0, 1, 0]
  Z+    %   2D convolution, keeping size
  w     %   Swap
  4*    %   Multiply by 4
  -     %   Subtract
  +     %   Add
        % Implicit end. Implicit display

```

# Answer
> 4 votes
## Mathematica, 65 bytes

```
#//.s_:>s+ListConvolve[{v={0,1,0},1-v,v},x=UnitStep[s-4],2,0]-4x&

```

### Explanation

```
#//.s_:>...&

```

Repeatedly transform the input by toppling all piles greater than 3. This process stops automatically when the transformation fails to change the matrix (i.e. when no large piles exist any more). In the following expression the matrix is called `s`.

```
...x=UnitStep[s-4]...

```

Create a matrix that has a `1` whenever the current matrix has a `4` or greater, and a zero otherwise. This is essentially a mask that indicates which piles need to be toppled. Call the mask `x`.

```
ListConvolve[{v={0,1,0},1-v,v},x=UnitStep[s-4],2,0]

```

First we compute the number of sand that is added to each pile due to toppled neighbouring piles. This is done with a convolution of the following matrix over `x`:

```
0 1 0
1 0 1
0 1 0

```

Essentially, it adds one to the current cell for each of its von-Neumann neighbours in the mask.

```
s+...-4x

```

We add the previous result to `s` and then we subtract four times the mask from it to reduce the toppled piles.

# Answer
> 3 votes
# Octave, 65 bytes

This doesn't seem very good, I must be missing some tricks...

```
m=input(0);do;m+=conv2(m>3,[0 1 0;1 -4 1;0 1 0],"same")
until m<4

```

# Answer
> 2 votes
## JavaScript (ES6), ~~101~~ 95 bytes

Takes the width of the matrix `w` and an array of values `a` in currying syntax `(w)(a)`. Returns an array of values.

```
w=>g=a=>(b=a.map((n,i)=>n%4+(F=d=>~m|i%w&&a[i+d]>>2)(m=w)+F(-w)+F(m=-1)+F(!++i)))+0==a+0?a:g(b)

```

### Formatted and commented

```
w =>                      // main function: takes w as input, returns g
  g = a =>                // recursive function g: takes a as input
    (                     //
      b = a.map((n, i) => // for each element n at position i in a:
        n % 4 + (         //   keep only n MOD 4
          F = d =>        //   define F(): function that takes d as input
            ~m |          //     if m is not equal to -1
            i % w &&      //     or i MOD w is not null:
            a[i + d] >> 2 //       return a fourth of the value of the cell at i + d
        )(m = w) +        //   test the cell below the current cell
        F(-w) +           //   test the cell above
        F(m = -1) +       //   test the cell on the left
        F(!++i)           //   test the cell on the right
      )                   // end of map(): assign the result to b
    ) + 0 == a + 0 ?      // if b is equal to a:
      a                   //   stop recursion and return a
    :                     // else:
      g(b)                //   do a recursive call with b

```

### Test cases

```
let f =

w=>g=a=>(b=a.map((n,i)=>n%4+(F=d=>~m|i%w&&a[i+d]>>2)(m=w)+F(-w)+F(m=-1)+F(!++i)))+0==a+0?a:g(b)

console.log(JSON.stringify(f(3)([2, 5, 4, 8, 6, 4, 1, 2, 3]))); // -> [3, 3, 0, 1, 2, 2, 1, 3, 2]
console.log(JSON.stringify(f(3)([0, 0, 2, 1, 3, 3, 0, 0, 0]))); // -> [0, 0, 2, 1, 3, 3, 0, 0, 0]
console.log(JSON.stringify(f(3)([9, 9, 9, 9, 9, 9, 9, 9, 9]))); // -> [1, 3, 1, 3, 1, 3, 1, 3, 1]
console.log(JSON.stringify(f(2)([4, 5, 2, 3]))); // -> [2, 3, 0, 1]
console.log(JSON.stringify(f(3)([2, 3, 5, 2, 2, 0]))); // -> [3, 0, 2, 2, 3, 1]
console.log(JSON.stringify(f(1)([7]))); // -> [3]
```

# Answer
> 1 votes
# C++, ~~261~~ ~~258~~ 250 bytes

```
#import<vector>
#define S size()
void f(std::vector<std::vector<int>>&m){s:int i,j,r;for(i=r=0;i<m.S;++i)for(j=0;j<m[i].S;++j){if(m[i][j]>3){r=1;m[i][j]-=4;j>0&&m[i][j-1]++;i>0&&m[i-1][j]++;j<m[i].S-1&&m[i][j+1]++;i<m.S-1&&m[i+1][j]++;}}if(r)goto s;}

```

Takes input as a reference to a vector of vectors and modifies it directly.

Try it online!

# Answer
> 1 votes
## JavaScript (ES6), ~~118~~ ~~114~~ 104 bytes

*Saved 2 bytes thanks to @Neil*

```
f=a=>a.find(b=>++y&&b.find(c=>++x&&c>3,x=0),y=0)?f(a.map(b=>b.map(c=>c+=--i|y?i*i+y*y==1:-4,i=x,--y))):a

```

---
Tags: code-golf, array, cellular-automata
---