Turn on suggestions

Auto-suggest helps you quickly narrow down your search results by suggesting possible matches as you type.

Showing results for

- KX Community
- :
- Discussion Forums
- :
- kdb+ and q
- :
- Re: kdb question about Euler #31

Options

- Subscribe to RSS Feed
- Mark Topic as New
- Mark Topic as Read
- Float this Topic for Current User
- Bookmark
- Subscribe
- Mute
- Printer Friendly Page

kdb question about Euler #31

Options

- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Report Inappropriate Content

2017.01.05 07:10 AM

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?

14 REPLIES 14

- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Report Inappropriate Content

2017.01.05 07:24 AM

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

- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Report Inappropriate Content

2017.01.05 07:45 AM

- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Report Inappropriate Content

2017.01.05 12:45 PM

Hmmm,

Forgot to update the solution for problem 31.

Please check again.

Have fun.

Kim

cur:200 100 50 20 10 5 2f

num:"f"$cross[;]over 6#cnt:til each 1+"j"$200%cur

num:num where 200>=result:num$6#cur

num:num cross "f"$last cnt

num:num where 200>=result:num$cur

count num

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

Kim

Sent from my iPhone

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

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

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

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!

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

You received this message because you are subscribed to the Google Groups "Kdb+ Personal Developers" group.

To unsubscribe from this group and stop receiving emails from it, send an email to personal-kdbplus+unsubscribe@googlegroups.com.

To post to this group, send email to personal-kdbplus@googlegroups.com.

Visit this group at https://groups.google.com/group/personal-kdbplus.

For more options, visit https://groups.google.com/d/optout.

--

You received this message because you are subscribed to the Google Groups "Kdb+ Personal Developers" group.

To unsubscribe from this group and stop receiving emails from it, send an email to personal-kdbplus+unsubscribe@googlegroups.com.

To post to this group, send email to personal-kdbplus@googlegroups.com.

Visit this group at https://groups.google.com/group/personal-kdbplus.

For more options, visit https://groups.google.com/d/optout.

--

You received this message because you are subscribed to the Google Groups "Kdb+ Personal Developers" group.

To unsubscribe from this group and stop receiving emails from it, send an email to personal-kdbplus+unsubscribe@googlegroups.com.

To post to this group, send email to personal-kdbplus@googlegroups.com.

Visit this group at https://groups.google.com/group/personal-kdbplus.

For more options, visit https://groups.google.com/d/optout.

- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Report Inappropriate Content

2017.01.05 08:03 PM

h:{{sum (y*til ceiling (z+1)%y){(x#0),neg[x] _ 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

Cheers

Ryan

- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Report Inappropriate Content

2017.01.05 08:18 PM

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[x] _ 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

Cheers

Ryan

- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Report Inappropriate Content

2017.01.06 04:04 AM

the earley parser uses a similar technique - finding out early (no pun intended) possibilities and building on those to find parses.

jack.

- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Report Inappropriate Content

2017.01.06 04:43 PM

- 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

- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Report Inappropriate Content

2017.01.07 02:04 AM

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

- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Report Inappropriate Content

2017.01.08 09:05 AM

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:

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:

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

- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Report Inappropriate Content

2017.01.09 03:22 AM

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.

- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Report Inappropriate Content

2017.01.11 12:58 PM

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

- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Report Inappropriate Content

2017.01.11 01:45 PM

{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 stuffwe 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 outsideq){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 cheatingq){raze sums y cut x}/[(t+t)#1;1_c]twhich is twice as slow due to reshaping 2 as much data

- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Report Inappropriate Content

2017.01.13 02:44 AM

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

- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Report Inappropriate Content

2017.01.18 02:03 PM

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

@[;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

Main Office Contacts

**EMEA**

Tel: +44 (0)28 3025 2242

**AMERICAS**

Tel: +1 (212) 447 6700

**APAC**

Tel: +61 (0)2 9236 5700

Useful Information

Resources

KX. All Rights Reserved.

KX and kdb+ are registered trademarks of KX Systems, Inc., a subsidiary of FD Technologies plc.