Daily Challenge #53 - Faro Shuffle

twitter logo ・1 min read

Daily Challenge (121 Part Series)

1) Daily Challenge #1 - String Peeler 2) Daily Challenge #2 - String Diamond 3 ... 119 3) Daily Challenge #3 - Vowel Counter 4) Daily Challenge #4 - Checkbook Balancing 5) Daily Challenge #5 - Ten Minute Walk 6) Daily Challenge #6 - Grandma and her friends 7) Daily Challenge #7 - Factorial Decomposition 8) Daily Challenge #8 - Scrabble Word Calculator 9) Daily Challenge #9 - What's Your Number? 10) Daily Challenge #10 - Calculator 11) Daily Challenge #11 - Cubic Numbers 12) Daily Challenge #12 - Next Larger Number 13) Daily Challenge #13 - Twice Linear 14) Daily Challenge #14 - Square into Squares 15) Daily Challenge #15 - Stop gninnipS My sdroW! 16) Daily Challenge #16 - Number of People on the Bus 17) Daily Challenge #17 - Double Trouble 18) Daily Challenge #18 - Triple Trouble 19) Daily Challenge #19 - Turn numbers into words 20) Daily Challenge Post #20 - Number Check 21) Daily Challenge #21 - Human Readable Time 22) Daily Challenge #22 - Simple Pig Latin 23) Daily Challenge #23 - Morse Code Decoder 24) Daily Challenge #24 - Shortest Step 25) Daily Challenge #25 - Double Cola 26) Daily Challenge #26 - Ranking Position 27) Daily Challenge #27 - Unlucky Days 28) Daily Challenge #28 - Kill the Monster! 29) Daily Challenge #29 - Xs and Os 30) Daily Challenge #30 - What is the price? 31) Daily Challenge #31 - Count IPv4 Addresses 32) Daily Challenge #32 - Hide Phone Numbers 33) Daily Challenge #33 - Did you mean...? 34) Daily Challenge #34 - WeIrD StRiNg CaSe 35) Daily Challenge #35 - Find the Outlier 36) Daily Challenge #36 - Let's go for a run! 37) Daily Challenge #37 - Name Swap 38) Daily Challenge #38 - Middle Name 39) Daily Challenge #39 - Virus 40) Daily Challenge #40 - Counting Sheep 41) Daily Challenge #41 - Greed is Good 42) Daily Challenge #42 - Caesar Cipher 43) Daily Challenge #43 - Boardgame Fight Resolver 44) Daily Challenge #44 - Mexican Wave 45) Daily Challenge #45 - Change Machine 46) Daily Challenge #46 - ??? 47) Daily Challenge #47 - Alphabets 48) Daily Challenge #48 - Facebook Likes 49) Daily Challenge #49 - Dollars and Cents 50) Daily Challenge #50 - Number Neighbor 51) Daily Challenge #51 - Valid Curly Braces 52) Daily Challenge #52 - Building a Pyramid 53) Daily Challenge #53 - Faro Shuffle 54) Daily Challenge #54 - What century is it? 55) Daily Challenge #55 - Building a Pile of Cubes 56) Daily Challenge #56 - Coffee Shop 57) Daily Challenge #57 - BMI Calculator 58) Daily Challenge #58 - Smelting Iron Ingots 59) Daily Challenge #59 - Snail Sort 60) Daily Challenge #60 - Find the Missing Letter 61) Daily Challenge #61 - Evolution Rate 62) Daily Challenge #62 - Josephus Survivor 63) Daily Challenge #63- Two Sum 64) Daily Challenge #64- Drying Potatoes 65) Daily Challenge #65- A Disguised Sequence 66) Daily Challenge #66- Friend List 67) Daily Challenge #67- Phone Directory 68) Daily Challenge #68 - Grade Book 69) Daily Challenge #69 - Going to the Cinema 70) Daily Challenge #70 - Pole Vault Competition Results 71) Daily Challenge #71 - See you next Happy Year 72) Daily Challenge #72 - Matrix Shift 73) Daily Challenge #73 - ATM Heist 74) Daily Challenge #74 - Free Pizza 75) Daily Challenge #75 - Set Alarm 76) Daily Challenge #76 - Bingo! (or not...) 77) Daily Challenge #77 - Bird Mountain 78) Daily Challenge #78 - Number of Proper Fractions with Denominator d 79) Daily Challenge #79 - Connect Four 80) Daily Challenge #80 - Longest Vowel Change 81) Daily Challenge #81 - Even or Odd 82) Daily Challenge #82 - English Beggars 83) Daily Challenge #83 - Deodorant Evaporator 84) Daily Challenge #84 - Third Angle of a Triangle 85) Daily Challenge #85 - Unwanted Dollars 86) Daily Challenge #86 - Wouldn't, not Would. 87) Daily Challenge #87 - Pony Express 88) Daily Challenge #88 - Recursive Ninjas 89) Daily Challenge #89 - Extract domain name from URL 90) Daily Challenge #90 - One Step at a Time 91) Daily Challenge #91 - Bananas 92) Daily Challenge #92 - Boggle Board 93) Daily Challenge #93 - Range Extraction 94) Daily Challenge #94 - Last Digit 95) Daily Challenge #95 - CamelCase Method 96) Daily Challenge #96 - Easter Egg Crush Test 97) Daily Challenge #97 - Greed is Good 98) Daily Challenge #98 - Make a Spiral 99) Daily Challenge #99 - Balance the Scales 100) Daily Challenge #100 - Round Up 101) Daily Challenge #101 - Parentheses Generator 102) Daily Challenge #102 - Pentabonacci 103) Daily Challenge #103 - Simple Symbols 104) Daily Challenge #104 - Matrixify 105) Daily Challenge #105 - High-Sum Matrix Drop 106) Daily Challenge #106 - Average Fuel Consumption 107) Daily Challenge #107 - Escape the Mines 108) Daily Challenge #108 - Find the Counterfeit Coin 109) Daily Challenge #109 - Decorate with Wallpaper 110) Daily Challenge #110 - Love VS. Friendship 111) Daily Challenge #111 - 99 Bottles of Beer 112) Daily Challenge #112 - Functions of Integers on the Cartesian Plane 113) Daily Challenge #113 - Iterative Rotation Cipher 114) Daily Challenge #114 - Speed Control 115) Daily Challenge #115 - Look and Say Sequence 116) Daily Challenge #116 - Shortest Knight Path 117) Daily Challenge #117 - MinMinMax 118) Daily Challenge #118 - Reversing a Process 119) Daily Challenge #119 - Adding Big Numbers 120) Daily Challenge #120 - Growth of a Population 121) Daily Challenge #121 - Who has the most money?

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!

twitter logo DISCUSS (19)
markdown guide
 

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
 
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.

 

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

 
 

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"]

 

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"
 

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!

 

You can shorten the index computation to:

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

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

 

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

 

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)
 

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";
 

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

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...

 

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

My solution in js

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

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

Classic DEV Post from Nov 1

How I Got Hired at DEV (and Every Other Tech Job)

dev.to staff profile image
The hardworking team behind dev.to ❤️