DEV Community

Daily Challenge #53 - Faro Shuffle

dev.to staff on August 30, 2019

Challenge To faro shuffle a deck of playing cards is to split the deck exactly in half, then perfectly interweave the cards, such that the original...

Read full post

Craig McIlwrath • Aug 30 '19

Haskell:

faroShuffle :: [a] -> [a]
faroShuffle ls = let mid = (length ls) `div` 2
                     fst = take mid ls
                     lst = drop mid ls
                     make2 a b = [a, b] 
                 in concat $ zipWith make2 fst lst

sam • Aug 31 '19

import Control.Arrow (arr, (&&&))

faroShuffle :: [a] -> [a]
faroShuffle a = let d = length a `div` 2
                in concat $
                   uncurry (zipWith (\a b -> [a, b])) $
                   (arr (take d)) &&& (arr (drop d)) a

i feel in my bones there's wholly point-free way to do it but can't quite get there right now

Craig McIlwrath • Aug 31 '19

I managed to get it point free!

import Control.Arrow (arr, (&&&))

faroShuffle :: [a] -> [a]
faroShuffle = concat .
              uncurry (zipWith (\a b -> [a, b])) .
              uncurry splitAt .
              ((arr ((`div`2) . length)) &&& (arr id))

I remember looking for the splitAt function when I was writing my first answer, not sure how I missed it in hoogle.

Also, I've never seen Control.Arrow before (I'm pretty new to Haskell). Seems useful.

Chris Achard • Aug 30 '19 • Edited

Bit of practice with flatMap; I hadn't used it before - but I'm going to start now!

const faro = deck => deck
  .slice(0, (deck.length / 2))
  .flatMap((card, i) => [card, deck[i + (deck.length / 2)]])

arr = ['ace', 'two', 'three', 'four', 'five', 'six']

console.log(faro(arr))

EDIT:

So I had the bright idea to do a screencast of me solving the problem and posting it on youtube... any feedback is welcome! And if it goes well, maybe I'll do more of them in the future :) We'll see! I haven't done youtube before, so this is my first video on there!

youtu.be/srT3yqFsgCQ

Kerri Shotts • Aug 31 '19

Nicely done on the video! Very clear, and nicely put together. :-)

Chris Achard • Aug 31 '19

Thanks!

Donald Feury • Aug 30 '19

Hmm I should try that IRL, how much does a deck of cards Go for nowadays?

shuffle.go

package shuffle

import (
    "errors"
)

// Faro interweaves two halves of a slice, leaving the first and last elements unchanged
func Faro(deck []string) ([]string, error) {
    size := len(deck)

    if size%2 != 0 {
        return nil, errors.New("deck must be of an even size")
    }

    // if the size is empty or just two, simply return the deck
    if size <= 2 {
        return deck, nil
    }

    left := deck[:(size / 2)]
    right := deck[(size / 2):]

    shuffled := []string{}

    for i := range left {
        shuffled = append(shuffled, left[i], right[i])
    }

    return shuffled, nil
}

shuffle_test.go

package shuffle

import "testing"

func equal(result []string, expected []string) bool {
    if len(result) != len(expected) {
        return false
    }

    for i := range result {
        if result[i] != expected[i] {
            return false
        }
    }

    return true
}

func TestFaro(t *testing.T) {
    testCases := []struct {
        description string
        input       []string
        expected    []string
        expectErr   bool
    }{
        {
            "empty slice",
            []string{},
            []string{},
            false,
        },
        {
            "returns error on odd sized slice",
            []string{"ace", "one", "two"},
            nil,
            true,
        },
        {
            "only two entries",
            []string{"ace", "king"},
            []string{"ace", "king"},
            false,
        },
        {
            "small deck",
            []string{"ace", "two", "three", "four"},
            []string{"ace", "three", "two", "four"},
            false,
        },
        {
            "post example",
            []string{"ace", "two", "three", "four", "five", "six"},
            []string{"ace", "four", "two", "five", "three", "six"},
            false,
        },
    }

    for _, test := range testCases {
        result, err := Faro(test.input)
        if err == nil && test.expectErr {
            t.Fatalf("FAIL: %s - Faro(%+v) - expected error to be thrown", test.description, test.input)
        }
        if !equal(result, test.expected) {
            t.Fatalf("FAIL: %s - Faro(%+v): %+v, %+v - expected '%+v'", test.description, test.input, result, err, test.expected)
        }
        t.Logf("PASS: %s", test.description)
    }
}

La blatte • Aug 30 '19 • Edited

A bit of golf:

f=a=>a.map((_,i)=>a[i/2+i%2*(a.length/2-.5)])

It works like this:

.map((_,i) : "i" will be the index of the current element, we don't need to work with the value here
We return a value located inside the input, at the following index:
- If we are in an odd space, the targeted index will be i/2 + true * (a.length / 2 + 0.5). Thanks to coercion, "true" will be translated to 1, hence we will fetch the (a.length / 2 + 0.5)+i/2th index
- Else if we are in an even space, the target will be i/2 + false * (a.length / 2 + 0.5), translated to i/2 + 0 * (a.length / 2 + 0.5) (hence, i/2)

The return will then be the following:

f(['ace', 'two', 'three', 'four', 'five', 'six'])
// ["ace", "four", "two", "five", "three", "six"]

f([...'1234567890abcdef'])
["1", "9", "2", "0", "3", "a", "4", "b", "5", "c", "6", "d", "7", "e", "8", "f"]

Alvaro Montoro • Aug 30 '19 • Edited

Taking into account that the input is an array, you could save some bytes by replacing [...a] with just a (for golf purposes).

Apart from that, the solution seems really specific to the problem, and doesn't work for different arrays. For example:

f(['ace', 'two', 'three', 'four', 'five', 'six', 'seven', 'eight'])
//["ace", "four", "two", "five", "three", "six", "four", "seven"]
// there are 2 "four" and no "eight"

La blatte • Aug 30 '19

Thanks a lot for the input! The problem was in the 2.5 usage, which had to be replaced with a.length/2-.5. I updated my answer!

Andrea Griffini • Aug 30 '19

You can shorten the index computation to:

i+i%2*a.length>>1

Andrea Griffini • Aug 30 '19

Python (golfing, and assuming we want to mutate the input list)

def f(x):x[:]=[x[i+i%2*len(x)>>1]for i in range(len(x))]

The idea is to use as index

(i // 2) + (((i % 2) * len(x)) // 2)

We can however factor //2 so we get

(i + (i % 2) * len(x)) // 2

Then we can use right shift >> to get rid of parenthesis to the final

i + i % 2 * len(x) >> 1

A solution just returning the shuffled array instead could be:

f=lambda x:[x[i+i%2*len(x)>>1]for i in range(len(x))]

cloudyhug • Aug 30 '19 • Edited

Basically using a recusive function picking one element from each half everytime until both are empty.

faro :: [a] -> [a]
faro deck = merge False [] $ splitAt (length deck `div` 2) deck
  where
    merge _     result ([], [])     = reverse result
    merge False acc    (a : as, bs) = merge True  (a : acc) (as, bs)
    merge True  acc    (as, b : bs) = merge False (b : acc) (as, bs)

E. Choroba • Aug 30 '19

Perl solution. Tests stolen from Donald Feury.

#!/usr/bin/perl
use warnings;
use strict;

sub faro_shuffle {
    my ($deck) = @_;
    die "Odd number of cards.\n" if @$deck % 2;

    my $mid = @$deck / 2;
    return [ map @$deck[$_, $mid + $_], 0 .. $mid - 1 ]
}

use Test::More tests => 5;
use Test::Exception;  

is_deeply faro_shuffle([]), [], 'empty';

is_deeply faro_shuffle(['ace', 'two']), ['ace', 'two'], 'two cards';

is_deeply faro_shuffle(['ace', 'two', 'three', 'four']),
                       ['ace', 'three', 'two', 'four'], 'small deck';

is_deeply faro_shuffle(['ace', 'two', 'three', 'four', 'five', 'six']),
                       ['ace', 'four', 'two', 'five', 'three', 'six'],
                       'original example';

throws_ok { faro_shuffle(['ace', 'two', 'three']) }
    qr/^Odd number of cards\.$/, "odd number exception";

Mat-R-Such • Aug 11 '20

python

def Faro(cards):
    half=len(cards)//2
    l, p, shuffle = cards[:half], cards[half:], list()
    for i in range(half):
        shuffle.append(l[i])
        shuffle.append(p[i])
    return shuffle

Kerri Shotts • Aug 31 '19

Oh, it's been a while since I've had bandwidth to participate. Today's was nice & relaxing, though. Just what I need before a flight.

Here's mine:

const split = arr => 
    [arr.slice(0, arr.length / 2), arr.slice(arr.length / 2)];

const interleave = (a, b) => 
    a.reduce((shuffled, aIdx, idx) => (shuffled.push(aIdx, b[idx]), shuffled), []);

const faro = arr => interleave(...split(arr));

Full version w/ tests at gist.github.com/kerrishotts/bde389...

Oleksii Filonenko • Aug 31 '19

I wanted to do it simple - Strings and flat_map()s, but here's a bit more involved solution, with generics, trait bounds, and an awesome case for the itertools crate :)

pub fn faro_shuffle<T: Clone>(deck: &[T]) -> Vec<T> {
    use itertools::Itertools;

    let mid = deck.len() / 2;
    deck[..mid]
        .iter()
        .interleave(deck[mid..].iter())
        .cloned()
        .collect()
}

K.V.Harish • Oct 7 '19 • Edited

My solution in JavaScript

const faroShuffle = (cards) => cards.slice(0, (cards.length / 2)).flatMap((card, index) => [card, cards[index + (cards.length / 2)]]);

Hidde Wieringa • Aug 31 '19

If you like shuffling card decks in this way a lot, see projecteuler.net/problem=622 for an interesting puzzle!