loading...

Daily Challenge #45 - Change Machine

thepracticaldev profile image dev.to staff ・1 min read

Today's challenge is to implement a change function that will accept an integer parameter that represents cents. The function should return the optimal change using the least number of coins.

The function should also return a key for each coin of US currency (specifically 25¢, 10¢, 5¢, and 1¢ coins). The value of each coin should represent the count of each coin in the change. The value for each coin that is not included should return 0.

Ex.
change(31)
{ 25 => 1, 10 => 0, 5 => 1, 1 => 1 }

Good luck!


This challenge comes from user Lordnibbler on CodeWars. Thank you to CodeWars, who has licensed redistribution of this challenge under the 2-Clause BSD License!

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

Posted on by:

thepracticaldev profile

dev.to staff

@thepracticaldev

The hardworking team behind dev.to ❤️

Discussion

pic
Editor guide
 

x86_64 assembly (System V ABI, GNU assembler), for those concerned about speed.

change.S:

    .global change

    .text
change:
    push %rbx
    xor %edx, %edx
    xor %ecx, %ecx
    mov %edi, %eax
    mov $table, %r9
loop:
    mov (%r9, %rcx, 4), %ebx
    div %ebx

    mov %eax, (%rsi, %rcx, 4)
    mov %edx, %eax
    xor %edx, %edx

    inc %ecx
    cmp $4, %ecx
    jne loop

    pop %rbx
    ret


    .section .rodata
table:
    .int 25
    .int 10
    .int 5
    .int 1

change.h:

/*
 * coins[0] = number of 25 cent coins
 * coins[1] = number of 10 cent coins
 * coins[2] = number of 5 cent coins
 * coins[3] = number of 1 cent coins
 */
unsigned int change(unsigned int n, unsigned int coins[4]);
 

I am concerned about speed

we need to get that stuff off the streets smh

causin' good folk to think they need to write stuff in assembly, fcol >.>

 

Rust, iterative style:

use std::collections::HashMap;

const COINS: [u32; 4] = [25, 10, 5, 1];

fn change(mut money: u32) -> HashMap<u32, u32> {
    let mut change = HashMap::new();
    for &coin in &COINS {
        change.insert(coin, money / coin);
        money %= coin;
    }
    change
}
 

ruby <3

def change(amount)
  result = { 25 => 0, 10 => 0, 5 => 0, 1 => 0 }
  case amount
  in 25.. then
    amount -= 25
    result[25] += 1
  in 10.. then
    amount -= 10
    result[10] += 1
  in 5.. then
    amount -= 5
    result[5] += 1
  in 1.. then
    amount -= 1
    result[1] += 1
  end until amount.zero?
  result
end

p change(31)
 

JavaScript

Pure variant of what has already been made in JavaScript.

function change(money) {
  return [25, 10, 5, 1].reduce(function([computedChange, remainingMoney], coin) {
    return [Object.assign(computedChange, {
      [coin]: Math.floor(remainingMoney / coin)
    }), remainingMoney % coin];
  }, [{}, money])[0];
}

Performance

I am curious about the performance in those kind of challenge. I am totally aware that JavaScript is not the fastest to do this kind of thing and the idea is not to bash any language of implementation. I'm just a guy curious about that. If some of you are willing to take the habit to post the performance for one milion iterations that would be cool to compare with others!

// one milion iterations
for (let index = 0; index < 1000000; index++) {
  change(31);
}

console.timeEnd("time");
// time: 21670.730ms

Source-Code

Available online.

 

A pure function is a function where the return value is only determined by its input values, without observable side effects.

Local state inside a function is generally not considered an observable side-effect.

Immutability is neat, but no prerequisite for FP per se. The Backus paper describes an FP system in the following way:

l) a set O of objects;
2) a set F of functions f that map objects into objects;
3) an operation, application;
4) a set F o functional forms; these are used to combine existing functions, or objects, to form new functions in F;
5) a set D of definitions that define some functions in F and assign a name to each.

Don’t get me wrong, I like your version, but in the strict sense I’d argue it isn’t more “pure” than the original version.

 

Hey there, thank you for your comment!

Don’t get me wrong, I like your version, but in the strict sense I’d argue it isn’t more “pure” than the original version.

We might think that the COINS variable declared with a const operator is indeed a constant but it is not. It is not possible to assign another array, but you can still update its values by targeting its indexes. This means that the function is inpure because its result is not predictable as it relies on an out-scope variable that can be updated outside of the function call, but used inside the function. The oustide world can update the array like so:

COINS[0] = "Hello world!";

The solution would be to declare the array as a freezed array in JavaScript:

const COINS = Object.freeze([1, 2, 3, ...]);

That way, no side-effects possible. This would also allow the function to be pure again. Another solution would be to declare the COINS variable inside the function, or even better, declare another parameter if the coins variable is something to be changed later.

const change = (cents, COINS = [1, 2, 3, ...]) => ...

You’re absolutely right there, I had misunderstood the intention of your comment (I thought your issue was with the local state), it was past 1am here. I even mentioned this exact same thing in the snippet I quoted (everything needs to be passed in/defined inside the function), but somehow didn't connect the dots there.

 

F#:

[<Measure>] type c

let COINS = [ 25<c>; 10<c>; 5<c>; 1<c> ]

let change (amount : int<c>) =
    let rec change' coins amount counts =
        match coins with
        | [] -> List.rev counts
        | h :: t -> change' t (amount % h) ((h, amount / h) :: counts)
    change' COINS amount []

Usage:

change 31<c>
// val it : (int<c> * int) list = [(25, 1); (10, 0); (5, 1); (1, 1)]

change 50<c>
// val it : (int<c> * int) list = [(25, 2); (10, 0); (5, 0); (1, 0)]

change 17<c>
// val it : (int<c> * int) list = [(25, 0); (10, 1); (5, 1); (1, 2)]

Notes:

*) Uses a unit of measure so change only works with amounts which are marked as cents, e.g. 25<c>.
*) The change function uses a local tail-recursive helper function called change'.
*) change' uses pattern matching with a cons pattern to destructure the list into head and tail.
*) Results are returned as simple tuples of the form (coin, count).

 

JavaScript with reduce:

const COINS = [25, 10, 5, 1]

const change = (cents) => {

  let remainingValue = cents

  const coinCount = COINS.reduce((count, coin) => {
    count[coin] = Math.floor(remainingValue / coin)
    remainingValue = remainingValue % coin
    return count
  }, {})

  return coinCount
}
 
public static void change(int number)
     {      
        int [] array = {25,10,5,1};
        number = 74;
        for(int m:array)
            {
                System.out.print(m+" =>"+number/m+" ,");
                number = number%m;      
            }
    }
 

This is a nice solution in Java. But don't forget to remove the number = 74;, otherwise the function will always write the same results.

 

Just my two cents, in Gwion

fun void change(int cents) {
  cents / 25 => const int coin25;
  coin25 * 25 -=> cents;
  cents / 10 => const int coin10;
  coin10 *10 -=> cents;
  cents  /5 => const int coin5;
  coin5 * 5 -=> cents;

#! this is a comment
#! below is the debug print.

  <<<
    "{ ",
    "25 => ",   coin25,
    ", 10 => ", coin10,
    ", 5 => ",  coin5,
    ", 1 => ",  cents,
    " }"
  >>>;
}

31 => change;

prints

{ 25 => 1, 10 => 0, 5 => 1, 1 => 1 }

It probably could be written better, but looks like it gets the job done.

 

Go - with tests:

change.go:

// Package change contains methods for interacting with US currency
package change

var coins = []int{25, 10, 5, 1}

// Change returns the fewest amount of each US coin to equal the amount of change indicated
func Change(amount int) map[int]int {
    usedCoins := map[int]int{25: 0, 10: 0, 5: 0, 1: 0}

    if amount == 0 {
        return usedCoins
    }

    remain := amount

    for _, coin := range coins {
        if remain == 0 {
            return usedCoins
        }

        mod := remain % coin
        if mod != remain {
            usedCoins[coin] = int(remain / coin)
            remain = mod
        }
    }

    return usedCoins
}

change_test.go

package change

import "testing"

func equal(actual map[int]int, expected map[int]int) bool {
    if len(actual) != len(expected) {
        return false
    }

    for k, v := range actual {
        expectedVal, present := expected[k]

        if !present || v != expectedVal {
            return false
        }
    }

    return true
}

func TestChange(t *testing.T) {
    for _, test := range changeTests {
        if actual := Change(test.input); !equal(actual, test.expected) {
            t.Fatalf(
                "FAIL: %s - Change(%d): %v, expected: %v \n",
                test.description,
                test.input,
                actual,
                test.expected,
            )
        }
        t.Logf("PASS: %s \n", test.description)
    }
}

change_test_cases.go

package change

var changeTests = []struct {
    description string
    input       int
    expected    map[int]int
}{
    {
        "no change",
        0,
        map[int]int{25: 0, 10: 0, 5: 0, 1: 0},
    },
    {
        "uses one coin",
        5,
        map[int]int{25: 0, 10: 0, 5: 1, 1: 0},
    },
    {
        "uses two coins",
        27,
        map[int]int{25: 1, 10: 0, 5: 0, 1: 2},
    },
    {
        "uses many coin",
        39,
        map[int]int{25: 1, 10: 1, 5: 0, 1: 4},
    },
}

 

that guard clause

defmodule CashMachine do                        #🎵 `goto` a CashMachine
  def change(money) do                          #🎵 to get a ticket home
    exchange(money, %{})                        #🎵 the message on the screen
  end                                           #🎵 says "don't make plans, y'all broke"

  defp exchange(0, coins), do: coins            #🎵 no, no, this can't be right
  defp exchange(coin, coins) when coin >= 25 do #🎵 I know that times is tight
    quarters = div(coin, 25)                    #🎵 I've only just been paid
    coin = rem(coin, 25)                        #🎵 three weeks, five days, do that seem
    exchange(coin, put_in(coins[25], quarters)) #🎵 right? no.
  end
  defp exchange(coin, coins) when coin >= 10 do #🎵 I scratch a livin', it ain't easy
    dimes = div(coin, 10)                       #🎵 you know it's a drag
    coin = rem(coin, 10)                        #🎵 I'm always payin', never makin'
    exchange(coin, put_in(coins[10], dimes))    #🎵 but you can't look back
  end                                           
  defp exchange(coin, coins) when coin >= 5 do  #🎵 I wonder if I'll ever get to
    nickels = div(coin, 5)                      #🎵 where I want to be
    coin = rem(coin, 5)                         #🎵 better believe it,
    exchange(coin, put_in(coins[5], nickels))   #🎵 I'm workin' for the CashMachine
  end
  defp exchange(coin, coins) when coin >= 1 do  # lyrics from "Cash Machine"
    exchange(0, put_in(coins[1], coin))         # by Hard-Fi
  end
end

Some people may say "are the comments really necessary?"

I say to them, "Is capitalism?"

 

My solution in js

const change = (amount) => {
  return {
    '25': Math.floor(amount/25),
    '10': Math.floor((a = amount%25)/10),
    '5': Math.floor((b = a%10)/5),
    '1': b % 5
  }
};
 

Another javascript solution:

function change(money)
{
  let coins = [1, 5, 10, 25];
  let parts = new Map([[25, 0],[10,0],[5,0],[1,0]]);
  let currentCoin = coins.pop();
  while(coins.length > 0)
  {
    if(money < currentCoin)
    {
      currentCoin = coins.pop();
    }
    else
    {
      parts.set(currentCoin, parts.get(currentCoin)+1);
      money -= currentCoin;
    }
  }
  return parts;
}
 

Greedy solution in JS

function getChange(n) {
  n = BigInt(n);
  let amount = 0n;
  let coinIndex = 3;
  let change = {
    25: 0n,
    10: 0n,
    5: 0n,
    1: 0n
  }
  const coins = [1n,5n,10n,25n];
  while(amount < n) {
    let divisibilty = ((n - amount) / coins[coinIndex]);
    if (divisibilty >= 1n) {
      change[coins[coinIndex]] += divisibilty;
      amount += (coins[coinIndex] * divisibilty);
    }
    else
      coinIndex--;
  }
  return change;
}
 

Python

def change(coin,coins = [25,10,5,1]):

    p=0
    ch_tab=[]
    while coin > 0:
        if (coin // coins[p]) > 0:
            ch_tab.append(coin // coins[p])
            coin = coin % coins[p]
            if coin != 0:
                p+=1
        else:
            ch_tab.append(0)
            p+=1
    while len(ch_tab) < 4:
        ch_tab.append(0)
    for i in range(len(coins)):
        print(coins[i], ' ==> ', ch_tab[i])
change(31)