23
\$\begingroup\$

Bowling

Bowling is a game where, essentially, each player gets 10 turns to:

Take 2 attempts at knocking down 10 pins arranged in a triangle.

  • between turns the pins are reset
  • from the 1st to the 2nd attempt the pins are left as-is

The arrangement of the pins resembles the following scheme, with the pins numbered 0-9:

6 7 8 9
 3 4 5
  1 2
   0

(Some rules and scoring mechanics omitted.)

Split spare

In bowling, a spare is when the player manages to knock down the pins that were left standing after a first attempt. A spare is said to be a split spare1 if the pins that were left standing are not adjacent.

E.g. if the pins are laid out as such:

. . 8 9
 . . .
  . 2
   .

Then a player who manages to knock down all these 3 pins would score a split spare, given that the pin 2 is not adjacent to the 8, 9 group.

(1 for the purposes of this challenge, a split spare is defined taking into account only the adjacency of the pins left standing, even though Wikipedia's link states that for a split spare to take place, the pin 0 must have been knocked down already)

Your task

Given the numbers of the pins left standing, output a Truthy value if such an arrangement would give a split spare and Falsy otherwise.

Input

The list of all pins left standing (at least 2), in any reasonable format. Pin numbering may be 0- or 1-indexed provided it follows the numbering direction shown above. Sensible input formats include:

  • a list of integers, like [2, 8, 9]
  • a string of integers, like "289"
  • separate arguments to a function
  • an integer whose bits correspond to the pints left standing and whose least significant bit corresponds to pin 0, e.g. 0b1100000100 for pins 2, 8 and 9.

You may assume input is sorted, if that helps you in any way.

Output

A single consistent value for Falsy test cases and anything else for Truthy test cases.

Test cases

Truthy

[0, 9]
[2, 8, 9]
[1, 5, 8]
[3, 5]
[3, 8]
[3, 9]
[6, 8]
[6, 9]
[3, 5, 8, 9]
[5, 6]
[0, 1, 5, 6, 7, 9]
[1, 2, 8, 9]

Falsy

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

Bonus imaginary internet points

Bonus imaginary internet points if your algorithm works for any triangle number of pins, instead of just 10.

So far, only Grimmy's 05AB1E answer qualifies for the bonus internet points!


Standard loopholes are forbidden by default.

This is so shortest solution wins! If you enjoy the challenge, consider upvoting it... And happy golfing!

\$\endgroup\$
  • 1
    \$\begingroup\$ Can we assume at least 2 pins? \$\endgroup\$ – G B Feb 11 at 10:10
  • 1
    \$\begingroup\$ May we take the input as a single 10-bit integer? \$\endgroup\$ – Arnauld Feb 11 at 12:06
  • 1
    \$\begingroup\$ @Noodle9 yes, the pin 2 was misplaced. Yes, [1, 2, 8, 9] is a split spare and for the challenge, for a spare to be a split spare we only care about adjacency. We don't care about the headpin. \$\endgroup\$ – RGS Feb 11 at 14:08
  • 1
    \$\begingroup\$ @RGS My initial version was outputting either false (Boolean value) or 0 (integer) for the falsy output. I had to fix it to always output false. \$\endgroup\$ – Arnauld Feb 11 at 14:18
  • 5
    \$\begingroup\$ A shame we couldn't make it a code-bowling contest somehow! \$\endgroup\$ – JDL Feb 11 at 16:51
9
\$\begingroup\$

05AB1E, 27 25 24 23 bytes

ÅTαε.āθDƪ}©æε®yKδαOß}à

Try it online!

Outputs 2 for falsy and a larger integer for truthy. Works for any triangle number of pins, thus qualifying for the bonus internet points.

A set of pins is split if and only if there is a partition of the set of pins in two subsets A and B such that no pin in A is adjacent to a pin in B.

Adjacency is determined using 3-element hexagonal coordinates.

First, we convert the input pins to their hex coordinate triplets:

   ε      }     # for each pin in the input:
ÅT              #  list of triangle numbers <= pin
  α             #  absolute difference of each one with pin
    .ā          #  enumerate: [a, b, c] => [[a, 1], [b, 2], [c, 3]]
      θ         #  get the last pair
       D        #  duplicate
        Æ       #  reduce the copy by subtraction
         ª      #  append that to the pair

Then, we iterate over partitions of this set of triplets in two subsets:

©               # save the set in the register
 æ              # powerset (list of subsets)
  ε       }     # for each subset y:
   ®            #  push the set from the register
    y           #  push y
     K          #  set difference (=> y's complement)

Then, we compute the 2D list of distances between each pin in the first subset and each pin in the second subset. Thanks to the elegance of 3-element hexagonal coordinates, this is surprisingly easy:

      δα        #  double vectorized absolute difference
        O       #  sum each triplet

Finally, we answer the question:

         ß      #  minimum distance for the current partition
          }     #  end the loop
           à    # maximum of the list of minimums
| improve this answer | |
\$\endgroup\$
  • 1
    \$\begingroup\$ Good job on winning the bonus internet points! Can you explain how you did it? \$\endgroup\$ – RGS Feb 11 at 14:49
  • 2
    \$\begingroup\$ @RGS explanation added, also i golfed 3 more bytes. \$\endgroup\$ – Grimmy Feb 11 at 15:52
7
\$\begingroup\$

Ruby, 72... 74 bytes

->l{*r=l[0];l.map{r.map{|w|r|=l&"zê-ǓᔂYMŰɃc"[w].ord.digits}};l&r!=l}

Try it online!

What is that?

Starting from the first pin in the list, check if all pins can be reached within a finite number of steps.

The binary string "zê-ǓᔂYMŰɃc" is the UTF-8 encoding of the adjacency list [122,234,45,467,5378,89,77,368,579,99]. Some digits are repeated to make the numbers fit into the ASCII range and spare some bytes, some edges are omitted if the node can be reached through different paths.

Thanks Value Ink for smoothing out rough edges (-3 bytes).

| improve this answer | |
\$\endgroup\$
  • 2
    \$\begingroup\$ I have very high expectations for your corrected version :) \$\endgroup\$ – RGS Feb 11 at 17:12
  • \$\begingroup\$ The main optimization that comes to mind is *r=l[0]. Also, it seems you only need to take "steps" up to the number of pins remaining, so l.map{r.map{ works too (at least for the existing test cases) \$\endgroup\$ – Value Ink Feb 11 at 23:37
6
\$\begingroup\$

JavaScript (ES6),  87  83 bytes

Saved 4 bytes thanks to @Grimmy

Takes input as a 10-bit integer (LSB = pin \$0\$, MSB = pin \$9\$). Returns a non-zero integer for a split spare, or \$0\$ otherwise.

n=>(g=m=>[6,29,51,210,430,788,136,344,688].map((v,i)=>m|=m>>i&1&&n&v)|m)(g(n&-n))^n

Try it online!

How?

Starting with the lowest bit set in the input, we progressively expand a bitmask with the pin neighbors. We eventually compare the result with the input.

Because we expand from pin \$0\$ to pin \$9\$ (let's call them \$P_0\$ to \$P_9\$), a single pass would occasionally miss a connection. Fortunately, processing two passes is always enough for all possible paths, which is what this code is doing.

For instance, let's consider the following configuration:

6 - - -
 3 4 -
  - 2
   -

First pass

We start with \$P_2\$, which expands to \$P_4\$. Then, \$P_4\$ expands to \$P_3\$. The connection between \$P_3\$ and \$P_6\$ is missed because \$P_3\$ is not included in the bitmask at the time it's processed.

Second pass

Again, we start with \$P_2\$, which expands to \$P_4\$ (no change). Then, \$P_3\$ expands to \$P_4\$ (no change) and \$P_6\$, which completes the bitmask.

Improvement

As pointed out by @Grimmy, we never need to expand from \$P_9\$: when we reach it, its neighbors (\$P_5\$ and \$P_8\$) have necessarily been found already. Therefore, we can safely discard its neighbor bitmask and iterate only from \$P_0\$ to \$P_8\$.

Commented

n => (                // n = input bitmask
  g = m =>            // g is a recursive function taking a mask m
    [                 //   lookup table:
             6,       //     neighbors of pin 0
           29,51,     //     neighbors of pins 1, 2
        210,430,788,  //     neighbors of pins 3, 4, 5
      136,344,688     //     neighbors of pins 6, 7, 8
    ]                 //   
    .map((v, i) =>    //   for each value v at position i in the above array:
      m |=            //     update m:
        m >> i & 1 && //       if the i-th bit is set in m:
        n & v         //         m = m OR (n AND v)
    ) | m             //   end of map(); return the new value of m
)(                    // invoke g twice to support the longer paths,
  g(n & -n)           // starting with the lowest bit set in n
) ^ n                 // compare the result with n
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ +1 for the solution using bitwise operations \$\endgroup\$ – RGS Feb 11 at 14:24
  • \$\begingroup\$ You can drop ,288 from the array: if we start with bit 9, that means it's the only bit set, so it's neighbors are irrelevant; otherwise, we can only reach 9 through 5 or 8, and they are adjacent to each other, so we don't need 9 to make the connection. \$\endgroup\$ – Grimmy Feb 12 at 14:15
  • \$\begingroup\$ @Grimmy Very nice catch. :) (PS: the input is guaranteed to include at least 2 pins, so we don't even have to worry about the 'pin 9 alone' case.) \$\endgroup\$ – Arnauld Feb 12 at 14:39
2
\$\begingroup\$

Python 3.8 (pre-release), 106 121 bytes

Defines a function P.__contains__ that takes a set of pins and returns False for a split spare or True otherwise.

e.g. P.__contains__({"0", "9"}) returns False while P.__contains__({"0", "1"}) returns True

d="6310214374254859876"
P={*map(frozenset,zip(d,d[1:]))}
while P<(P:={a|b for a in P for b in P if a&b}):0
P.__contains__

Try it online!

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ +1 for a nice python solution :) \$\endgroup\$ – RGS Feb 11 at 20:13
  • \$\begingroup\$ Wouldn't P.__contains__ have to actually count towards you byte count? \$\endgroup\$ – mypetlion Feb 12 at 23:34
  • \$\begingroup\$ @mypetlion looked around meta a bit and the general consensus seems to be that it does count towards your byte count. Updated. \$\endgroup\$ – Kyle G Feb 13 at 14:41
2
\$\begingroup\$

C++ (gcc), 381 \$\cdots\$ 267 248 bytes

#import<set>
using S=std::set<long>;int f(S s){std::set<S>c;for(long b=0x5792628a5a065664;b>9;b/=10)c.insert({b%10,b/10%10});for(S i:c)for(S j:c){S q(i);q.insert(begin(j),end(j));if(q.size()<i.size()+j.size())c.insert(q);}return c.find(s)==end(c);}

Try it online!

Ungolfed

#include<set>
#include<algorithm>
using namespace std;
using S=set<int>;
bool f(S s) {
    // Change array a for any number or shape of pins,
    //  instead of just a triangle of 10.
    // It lists all the pins next to all their adjacent pins.
    int a[]{6,3,1,0,2,1,4,3,7,4,2,5,4,8,5,9,8,7,6};                                                                                                              
    set<S> c;
    for(int i=0;i<sizeof(a)/sizeof(int)-1;++i) 
        c.insert({a[i], a[i+1]});
    set<S> t;
    // Keep on adding connected sets of pins until there are no more new ones.
    while (t!=c) {
        for (auto i:c)
            for (auto j:c)
                if (any_of(begin(i),end(i),
                   [&](auto e){return j.find(e)!=end(j);}))
                {
                    S q(i);
                    q.insert(begin(j),end(j));
                    t.insert(q);
                }
        swap(t,c);
    }
    return c.find(s)==end(c);
}

Builds a set of all connected pin sets as per Kyle Gullion's idea and then simply tests for membership.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ I'm having trouble with the TIO link, is it from my phone? \$\endgroup\$ – RGS Feb 12 at 9:23
  • \$\begingroup\$ Ah I see! +1 for your submission, even though you are currently losing :'( \$\endgroup\$ – RGS Feb 12 at 13:18
  • 1
    \$\begingroup\$ @RGS I'm still golfing it, you just wait and see! T_T \$\endgroup\$ – Noodle9 Feb 12 at 13:40
  • 1
    \$\begingroup\$ @RGS Check it out now, runs fine on TIO with optimisation cranked! :-) \$\endgroup\$ – Noodle9 Feb 12 at 17:01
  • \$\begingroup\$ Really cool! Thanks for the effort :D \$\endgroup\$ – RGS Feb 12 at 17:15
1
\$\begingroup\$

Charcoal, 47 bytes

UO⁸#Fθ«≔⌊⊘⊖₂⊕×⁸ιηJ⁺³⁻⊗ι×η⁺²η⊗ηUO²ψ»¤#≔›⁶⁴LKAη⎚η

Try it online! Link is to verbose version of code. Takes input as an array of integers and outputs a Charcoal boolean, - for a split spare, empty output otherwise. Explanation:

UO⁸#

Draw an 8-by-8 rectangle of #s.

Fθ«

Loop over the input pins.

≔⌊⊘⊖₂⊕×⁸ιη

Calculate the row of the pin.

J⁺³⁻⊗ι×η⁺²η⊗η

Jump to the position of the pin.

UO²ψ

Erase a 2-by-2 rectangle representing the pin.

»¤#

Fill with #s starting at the last pin.

≔›⁶⁴LKAη

See whether the fill restored all 64 #s.

⎚η

Clear the canvas and output the result.

Although I calculate the position of the pin directly (I tried a look-up table but it was the same byte count) this method won't handle arbitrary numbers of pins since it needs to be able to draw a large enough initial rectangle. However it can be adjusted to handle a specific maximum number of pins: the initial 8 needs to be increased by 2 for each additional row of pins, the 3 needs to be one less than the new number of rows of pins, and the 64 needs to be the square of the number that replaces 8.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Nice submission! You don't qualify for the bonus imaginary internet points, unfortunately :( \$\endgroup\$ – RGS Feb 12 at 6:59
  • 1
    \$\begingroup\$ @RGS Right, the bonus points aren't worth the extra byte count. \$\endgroup\$ – Neil Feb 12 at 10:03
  • \$\begingroup\$ No problem, the bonus points are just imaginary \$\endgroup\$ – RGS Feb 12 at 13:16
1
\$\begingroup\$

Excel (Ver. 1911), 142 Bytes

A1     'Input
B1:B10 3ÒƮ̔ŘʰĠ 'one character per row
       ^^^ (Non-printing characters)
C1     =ROW(B1:B10)-1
D1     =BITAND(INT(A1/2^C1#),1)*UNICODE(B1:B10)
E1     =SUM(MMULT(N(BITAND(2^C1#,TRANSPOSE(D1#))*D1#>0),N(C1#>=0)))+2<2*SUM(N(D1#>0)) 'Output

Here un-golfed using named ranges and extra columns

Input         'Input
Bit_List      3ÒƮ̔ŘʰĠ 'as a column of chars
Pin_Num       =SEQUENCE(ROWS(Bit_List))-1
Unicode       =UNICODE(Bit_List)
Pins_Left     =BITAND(INT(Input/2^Pin_Num),1)*Unicode
Pins_Adjacent =MMULT(SIGN(BITAND(2^Pin_Num,TRANSPOSE(Pins_Left))*Pins_Left),SIGN(Pin_Num+1))
Split         =SUM(Pins_Adjacent)<2*(SUM(SIGN(Pins_Left))-1)

Try it offline! (link to the workbook in a google drive)

You'll need to download and open in the latest version of excel for the formulas to work.

Single Test+Comments screenshot

Test+Comments

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ +1 incredible work on this! \$\endgroup\$ – RGS Feb 14 at 20:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.