kdb question about Euler #31

Community Support
1

Hi kdb Group,

I am new to kdb and have been using Project Euler as a learning resource. 

I have been looking at this problem and would like to know how to solve using kdb code to improve my understanding.

The problem is below, many thanks to all!

http://projecteuler.net/index.php?section=problems&id=31


In England the currency is made up of pound, £, and pence, p, and there are eight coins in general circulation:

1p, 2p, 5p, 10p, 20p, 50p, £1 (100p) and £2 (200p).It is possible to make £2 in the following way:

1x£1 + 1x50p + 2x20p + 1x5p + 1x2p + 3x1p

How many different ways can £2 be made using any number of coins?

2

Hi wchan0284,

That’s an interesting problem, perhaps the best thing is to start by calculating all the ways of distributing 1p, 2p, 3p, etc. using each available denomination and building up a list of solutions from there - then the total number of combinations for larger amounts just involve looking up the already calculated smaller combinations. 

For example, if we want to calculate the number of ways of distributing 5p we could:

(i) Hand out 1p and look up the total number of combinations for handing out 4p

(ii) Hand out 2p and look up the total number of combinations for handing out 3p

(iii) Hand out 5p and look up the total number of combinations for handing out 0p (which is 1).    

In terms of translating this into q we would get the below:

target:200

coins:1 2 5 10 20 50 100 200

// Keeps track of the number of combinations for each amount until we reach the target

// For example combo[5] gives the number of ways of distributing 5p

// Start with 0p = 1, initialise the rest to be 0 

combos:1,#[target;0]

// Builds up solution out to the target amount

{r:_[y;til 1+z];{@[x;y;+;x@y-z]}/[x;r;y]}/[combos;coins;target]

The outer loop runs across each coin denomination, the inner one builds up the number of combinations. The last entry in the result will give you your required solution. 

Some info on using / (over) in kdb+ is available here: http://code.kx.com/wiki/Reference/Slash

Thanks,

Kevin

3

https://github.com/kimtang/kdb-euler

Kim
Sent from my iPhone

4

Hmmm,<o:p></o:p>

<o:p> </o:p>

Forgot to update the solution for problem 31.<o:p></o:p>

<o:p> </o:p>

Please check again.<o:p></o:p>

<o:p> </o:p>

Have fun.<o:p></o:p>

<o:p> </o:p>

Kim<o:p></o:p>

<o:p> </o:p>

cur:200 100 50 20 10 5 2f<o:p></o:p>

num:“f”$cross[;]over 6#cnt:til each 1+“j”$200%cur <o:p></o:p>

num:num where 200>=result:num$6#cur  <o:p></o:p>

num:num cross “f”$last cnt <o:p></o:p>

num:num where 200>=result:num$cur<o:p></o:p>

count num<o:p></o:p>

<o:p> </o:p>

<o:p> </o:p>

Von: personal-kdbplus@googlegroups.com [mailto:personal-kdbplus@googlegroups.com] Im Auftrag von Kim Tang
Gesendet: Donnerstag, 5. Januar 2017 16:46
An: personal-kdbplus@googlegroups.com
Betreff: Re: [personal kdb+] kdb question about Euler #31<o:p></o:p>

<o:p> </o:p>

https://github.com/kimtang/kdb-euler<o:p></o:p>

<o:p> </o:p>

Kim
Sent from my iPhone<o:p></o:p>

On 5 Jan 2017, at 15:24, Kevin Smyth <kevin154@gmail.com> wrote:<o:p></o:p>

Hi wchan0284,<o:p></o:p>

<o:p> </o:p>

That’s an interesting problem, perhaps the best thing is to start by calculating all the ways of distributing 1p, 2p, 3p, etc. using each available denomination and building up a list of solutions from there - then the total number of combinations for larger amounts just involve looking up the already calculated smaller combinations. <o:p></o:p>

<o:p> </o:p>

For example, if we want to calculate the number of ways of distributing 5p we could:<o:p></o:p>

(i) Hand out 1p and look up the total number of combinations for handing out 4p<o:p></o:p>

(ii) Hand out 2p and look up the total number of combinations for handing out 3p<o:p></o:p>

(iii) Hand out 5p and look up the total number of combinations for handing out 0p (which is 1).    <o:p></o:p>

<o:p> </o:p>

In terms of translating this into q we would get the below:<o:p></o:p>

<o:p> </o:p>

target:200<o:p></o:p>

coins:1 2 5 10 20 50 100 200<o:p></o:p>

// Keeps track of the number of combinations for each amount until we reach the target<o:p></o:p>

// For example combo[5] gives the number of ways of distributing 5p<o:p></o:p>

// Start with 0p = 1, initialise the rest to be 0 <o:p></o:p>

combos:1,#[target;0]<o:p></o:p>

<o:p> </o:p>

// Builds up solution out to the target amount<o:p></o:p>

{r:_[y;til 1+z];{@[x;y;+;x@y-z]}/[x;r;y]}/[combos;coins;target]<o:p></o:p>

<o:p> </o:p>

The outer loop runs across each coin denomination, the inner one builds up the number of combinations. The last entry in the result will give you your required solution. <o:p></o:p>

Some info on using / (over) in kdb+ is available here: http://code.kx.com/wiki/Reference/Slash<o:p></o:p>

<o:p> </o:p>

Thanks,<o:p></o:p>

Kevin<o:p></o:p>

<o:p> </o:p>

On 5 January 2017 at 15:10, <wchan0284@gmail.com> wrote:<o:p></o:p>

Hi kdb Group,<o:p></o:p>

<o:p> </o:p>

I am new to kdb and have been using Project Euler as a learning resource. <o:p></o:p>

<o:p> </o:p>

I have been looking at this problem and would like to know how to solve using kdb code to improve my understanding.<o:p></o:p>

<o:p> </o:p>

The problem is below, many thanks to all!<o:p></o:p>

<o:p> </o:p>

<o:p> </o:p>

http://projecteuler.net/index.php?section=problems&id=31<o:p></o:p>

<o:p> </o:p>

In England the currency is made up of pound, £, and pence, p, and there are eight coins in general circulation:<o:p></o:p>

1p, 2p, 5p, 10p, 20p, 50p, £1 (100p) and £2 (200p).It is possible to make £2 in the following way:<o:p></o:p>

1x£1 + 1x50p + 2x20p + 1x5p + 1x2p + 3x1p<o:p></o:p>

How many different ways can £2 be made using any number of coins?<o:p></o:p>

–
Submitted via Google Groups

5

That is such a nice answer Kevin! Took a while for me to get my head around it, good explanation. For fun I tried modifying it slightly, trying to avoid the inner recursion. Turns out it can be done with a modified version of xprev (with 0 instead of 0N):

h:{{sum (y*til ceiling (z+1)%y){(x#0),neg _ y}:x}/[1,x#0;y;x]}

For euler problem 31 this seems to be a bit faster than the double over, (e.g. \t:100 140 vs 107), however, think the recursion works better for larger targets (although conversely worse for larger numbers of coins). Also I reckon your original recursion looks neater/simpler.

Cheers

Ryan

6

(not sure if my previous attempt reply worked, apologies if a double post) 

That is such a nice answer Kevin! Took a while for me to get my head around it, good explanation. For fun I tried modifying it slightly, trying to avoid the inner recursion. Turns out it can be done with a modified version of xprev (with 0 instead of 0N):

h:{{sum (y*til ceiling (z+1)%y){(x#0),neg _ y}:x}/[1,x#0;y;x]}

For euler problem 31 this seems to be a bit faster than the double over, (e.g. \t:100 140 vs 107), however, think the recursion works better for larger targets (although conversely worse for larger numbers of coins). Also I reckon your original recursion looks neater/simpler.

Cheers

Ryan

7

i think they call it ‘dynamic programming’?
the earley parser uses a similar technique - finding out early (no pun intended) possibilities and building on those to find parses.

jack.

8

Dynamic Programming solution

  • using last row (total ways  for amounts  from 0 to target  using previous set of coins ) to calcuate new row values (total ways after adding current coin to previous set) 

cl:1 2,5 10 20 50 100 200  / coins list
t:200  / target

/ params - previous row ; current coin; target amount; amount list from 0 to target
/ initial row will be for coin 0  which is 1 way for 0 amount and 0 ways for all other amounts => 1,t#0

({[s;c;t;l] raze sums s (div[t;c]+0<mod[t;c];c)#l}[;;1+t;til 1+t]/[1,t#0;cl]) t

9

Looks like my last  post didn’t work. Trying again:

Dynamic Programming solution - use last row to calculate new row.

-amount list : list containing all amounts from 0 to target =>til target+1

  • last row : total ways for every amount in amount list using previous set of coins
  • new row: total ways for every amount in amount list after adding current coin to previous set of coins
  • initial row - total ways to get all amounts from coin 0 =>1 t#0

c:1,2,5,10,20,50,100,200 / coins list
t:200  / target

/ params- last row sums; current coin; target+1;amout list from 0 till target

({[s;c;t;l] raze sums s (ceiling t%c;c)#l}[;;1+t;til 1+t]/[1,t#0;coins]) t

10

Yes it seems like each post gets put in a pending state waiting for an approval, so shows up several hours later. 

Your reshape is a much better idea, nice. Think you can skip the first iteration and just use (t+1)#1 instead (assuming count[c]>1), but I guess by this stage it doesn’t really need to go much faster (as yours was already < 0 ms). Using (t+1)# instead of indexing:

p.p1 {margin: 0.0px 0.0px 0.0px 0.0px; font: 12.0px Monaco}span.s1 {font-variant-ligatures: no-common-ligatures} p.p1 {margin: 0.0px 0.0px 0.0px 0.0px; font: 12.0px Monaco}span.s1 {font-variant-ligatures: no-common-ligatures}

last{z#raze sums (ceiling z%y;y)#x}/[k#1;1_c;k:1+t]

On Saturday, January 7, 2017 at 7:10:36 AM UTC-5, RAHUL ASATI wrote:

Looks like my last  post didn’t work. Trying again:

Dynamic Programming solution - use last row to calculate new row.

-amount list : list containing all amounts from 0 to target =>til target+1

  • last row : total ways for every amount in amount list using previous set of coins
  • new row: total ways for every amount in amount list after adding current coin to previous set of coins
  • initial row - total ways to get all amounts from coin 0 =>1 t#0

c:1,2,5,10,20,50,100,200 / coins list
t:200  / target

/ params- last row sums; current coin; target+1;amout list from 0 till target

({[s;c;t;l] raze sums s (ceiling t%c;c)#l}[;;1+t;til 1+t]/[1,t#0;coins]) t

11

You are correct that it can be improved by using first row as (t+1)#1 which is the output for 1p coin. 

Just wanted to share the basic idea to calculate row for every coin so that it can be used with any set of coins which is not possible if we start with row with all 1’s.

You have also reduced 1 param to function. Nice.

12

very neat stuff

we can also

  • use indexing instead of last, so z# is not needed

  • take works on atoms, so no need for k# either

  • calculation of shapes can be done outside

q){raze sums y#x}/[1;flip(ceiling(1+t)%1_c;1_c)]t

(only marginally faster)

we can also use cut with a bit of cheating

q){raze sums y cut x}/[(t+t)#1;1_c]t

which is twice as slow due to reshaping 2 as much data

13

Very nice. One small follow up to a comment Rahul made from earlier - I think if the coin set doesn’t happen to have a 1c coin, we can still skip the first coin, but start with 1,(c[0]-1)#0 instead of 1

p.p1 {margin: 0.0px 0.0px 0.0px 0.0px; font: 10.0px Monaco}span.s1 {font-variant-ligatures: no-common-ligatures}

{raze sums y#x}/[1,(c[0]-1)#0;flip(ceiling(1+t)%1_c;1_c)]t   

On Wednesday, January 11, 2017 at 3:58:58 PM UTC-5, Attila wrote:

very neat stuff

we can also

  • use indexing instead of last, so z# is not needed

  • take works on atoms, so no need for k# either

  • calculation of shapes can be done outside

q){raze sums y#x}/[1;flip(ceiling(1+t)%1_c;1_c)]t

(only marginally faster)

we can also use cut with a bit of cheating

q){raze sums y cut x}/[(t+t)#1;1_c]t

which is twice as slow due to reshaping 2 as much data

14

Great, that will work. Just need to add one check to cover case with only 1 coin in input.

15

Rosetta Code also has examples of the problem although only a “J” APL solution not k/q

Recursive on coinlist - this version assumes the list ends with hard-coded 2 1 since that’s just 1 + floor of half remaining total

 {$[0=count x;1+floor y%2;y<x[0];.z.s[1_x;y];.z.s[x;y-x[0]]+.z.s[1_x;y]]}[200 100 50 20 10 5;200]

Whereas this more general case tests the last coin can divide remaining balance exactly .. so here only half the leaves contribute.

{$[1=count x;y=x[0]*floor y%x[0];y<x[0];.z.s[1_x;y];.z.s[x;y-x[0]]+.z.s[1_x;y]]}[200 100 50 20 10 5 1 2;200]

Much much faster is to iterate a vector recurrence relation adding coins in increasing order

 f:{raze sums ((1+floor (count x)%y),y)#x}       / NB. the vector will be extended with junk as we reshape to rectangle for sums - cut produces incompatible ragged output

@[;1000] ( ((1000+1)#1i) f/ 2 5 10 20 50 100 200 500 1000 )

327631322i

/ note integer arithmetic wraps so using float vectors instead here

@[;100000] ( ((100000+1)#1) f/ 5 10 25 50 100 )

    13398445413854501