## DEV Community is a community of 906,671 amazing developers

We're a place where coders share, stay up-to-date and grow their careers.

# Daily Challenge #53 - Faro Shuffle

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 top and bottom cards are unchanged.

Write a function that accepts a even-numbered list and faro shuffles the indices.

Example
Faro shuffling the list: `['ace', 'two', 'three', 'four', 'five', 'six']`
will give `['ace', 'four', 'two', 'five', 'three', 'six']`

Good luck, happy coding!

Want to propose a challenge idea for a future post? Email yo+challenge@dev.to with your suggestions!

## Discussion (20) Chris Achard • Edited on

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

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

Thanks! sam
``````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 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. 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/2`th 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 • Edited on

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"
`````` Donald Feury

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)
}
}

`````` E. Choroba

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";
`````` Michael Kohl • Edited on

F#:

``````module FaroShuffle

type Deck = string list

let faroShuffle (deck : Deck) =
let mid = deck.Length / 2
[ 0..mid - 1 ]
|> List.collect (fun i ->
[ deck.[i]
deck.[i + mid] ])
``````

Tests:

``````module FaroShuffleTest

open FsUnit.Xunit
open Xunit
open FaroShuffle

[<Fact>]
let ``6 card deck``() =
faroShuffle [ "ace"; "two"; "three"; "four"; "five"; "six" ]
|> should equal [ "ace"; "four"; "two"; "five"; "three"; "six" ]

[<Fact>]
let ``2 card deck``() =
faroShuffle [ "one"; "two" ] |> should equal [ "one"; "two" ]

[<Fact>]
let ``empty deck``() = faroShuffle [] |> should be Empty

`````` 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 • Edited on

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)
`````` 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

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

I wanted to do it simple - `String`s 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 • Edited on

My solution in JavaScript

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

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