loading...

Daily Challenge #53 - Faro Shuffle

twitter logo ・1 min read

Daily Challenge (161 Part Series)

1) Daily Challenge #1 - String Peeler 2) Daily Challenge #2 - String Diamond 3 ... 159 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? 122) Daily Challenge #122 - Clockwise Spirals 123) Daily Challenge #123 - Curry me Softly 124) Daily Challenge #124 - Middle Me 125) Daily Challenge #125 - 23 Matches or More 126) Daily Challenge #126 - The Supermarket Line 127) Daily Challenge #127 - Playing with Passphrases 128) Daily Challenge #128 - Blackjack Scorer 129) Daily Challenge #129 - Clay Pigeon Shooting 130) Daily Challenge #130 - GCD Sum 131) Daily Challenge #131 - Remove Anchor from URL 132) Daily Challenge #132 - Is my friend cheating? 133) Daily Challenge #133 - Suitcase Packing 134) Daily Challenge #134 - Rice and Chessboard Problem 135) Daily Challenge #135 - The Wide Mouthed Frog! 136) Daily Challenge #136 - The Deaf Rats of Hamelin 137) Daily Challenge #137 - Help the Bookseller 138) Daily Challenge #138 - Do I get a Bonus? 139) Daily Challenge #138 - Keep Up the Hoop 140) Daily Challenge #140 - I love you, a little, a lot, passionately ... not at all 141) Daily Challenge #141 - Two Sum 142) Daily Challenge #142 - Parts of a Whole 143) Daily Challenge #143 - Big Arithmetic 144) Daily Challenge #144 - Box Office Clerk 145) Daily Challenge #145 - SET Card Game 146) Daily Challenge #146 - The Dollar Game 147) Daily Challenge #147 - NIM 148) Daily Challenge #148 - Disemvowel Trolls 149) Daily Challenge #149 - Fun with Lamps 150) Daily Challenge #150 - Boggle Guess Validator 151) Daily Challenge #151 - Reverse Parentheses 152) Daily Challenge #152 - Strongest Number in an Interval 153) Daily Challenge #153 - Horse Race Gamble 154) Daily Challenge #154 - Stable Arrangement 155) Daily Challenge #155 - Royal Arranged Marriages 156) Daily Challenge #162 - Taxi Dispatching 157) Daily Challenge #163 - Significant Figures 158) Daily Challenge #164 - Jump 159) Daily Challenge #165 - Password Lost in a Grid 160) Daily Challenge #166 - Cat and Mouse 161) Daily Challenge #167 - Return String As Sorted Blocks

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 May 29 '19

Is generalization killing creativity in the software industry?

As software gets more and more integrated into our lives, the industrialization of its crafting process becomes inevitable. But the over-generalization of software engineering can be crushing the creative side of programming.

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