A collection of programming problems

[daydreamer]

Use it in American movie universe : every phone number starts with 555-four digit number?
Linear ? Does he mean limited to scalar single thread code, prohibit simd and simt solutions ?
Isnt restricting to same fixed random seed, on purpose to be able to compare speed, with different solutions from different coders?

[Siekmanski]

You could use the same principle as my "CalculateMedian" routine.

http://masm32.com/board/index.php?topic=8671.msg94735#msg94735

Highest phone number = 9999999 = 1250000 bytes to populate = 1.1921 MB memory usage.

Read in all phone numbers and set the corresponding bit in the memory table.
for example: 1234567
1234567 shr 3 = 154320 -> jump to byte offset 154320 in memory.
1234567 and 7 = 7    -> set bit 7

Do this for all phone numbers and set the corresponding bits.

When done start reading the first bit, if set the phone number = 0000000
Read the next bit, if set the phone number is 0000001
Read the next bit, if set the phone number is 0000002 etc. till you reach bit number 9999999.

If a bit is not set it is not a phone number.

This way you have automatically sorted the telephone numbers and you will get rid of duplicate numbers.
Very fast routine and it uses only 1.1921 MB memory

[daydreamer]

The random generator is excellent. It's something else

As in Great entropy? But if you choose crappiest entropy rndgenerator might result in only 10k phone numbers ?

[jj2007]

You could use the same principle as my "CalculateMedian" routine.

http://masm32.com/board/index.php?topic=8671.msg94735#msg94735

Sorry, I can't see what the two things have in common. Can you explain?

Highest phone number = 9999999 = 1250000 bytes to populate = 1.1921 MB memory usage.

Read in all phone numbers and set the corresponding bit in the memory table.

That is exactly what my program does, see attachment in reply #7.

In the meantime, I found the little bugger - it's fixed, see attachment.

Code Select Expand

  elements=1000000
Dim Tel(elements-1) As DWORD
For_ ecx=0 To elements-1 ; one Million random numbers
add Rand(900000), 100000 ; range 100,000 ... 999,999
mov Tel(ecx), eax
Next
...
  lea edi, Tel(0)
  xor ebx, ebx
  .Repeat
mov eax, [edi+4*ebx] ; get a number
bts [esi], eax ; set a bit at this number's distance
inc ebx
  .Until ebx>=elements ; n input numbers

Code Select Expand

8426 µs for creating an array of random phone numbers
1042 µs for getting the max = 999997
3193 µs for setting the bits
10 ms   for sorting & storing 603368 phone numbers
100000
100001
100002
100003
100005
100006
100007
100008
100009
100012
96 ms  for nrQsortA (there are duplicates)
100000
100001
100002
100002
100003
100005
100006
100007
100008
100009

As you can see, with these parameters we have about 40% duplicates. The algo is damn fast, 10x QuickSort with the chosen range, but, as mentioned before, there is no way to keep the duplicates. The interesting question is now what is the actual usage of a DWORD sorter? Should the result have duplicates or not? I guess we need both algos, depending on the actual requirements.

@Z: There is even a Sudoku example

[zedd151]

@Z: There is even a Sudoku example

  I'll look at that later...

edit... a couple minutes later. lol I though you made that puzzle. Anyway, I checked it for validity and it is valid with one solution (for the uniquiness rule). It is a rather easy puzzle though, rated at only 214 (via 'hodoku.exe') for anyone interested in such things.   

[Siekmanski]

> Sorry, I can't see what the two things have in common. Can you explain?

Hi Jochen,

I remembered I used the simulair approach to count colors used in a picture and the median calculation to exclude sorting a while ago.
The number storing as a position in a table to exclude sorting would also be usefull for the phone number approuch.
Sorry, didn't know you used the same technique because I missed the source code in your second .zip 

[jj2007]

The number storing as a position in a table to exclude sorting would also be usefull for the phone number approuch.
Sorry, didn't know you used the same technique because I missed the source code in your second .zip 

Hi Marinus,

I didn't invent the technique - I just translated David Maynard's instructions to Assembly.

Problem: Given a list of one million random 7-digit phone numbers write a program that prints a sorted list of the phone numbers with duplicates removed, using less than 2 M Bytes of memory and that runs in linear time.

Solution:

Create a bit vector of 10 million bits (10/8 = 1.25 million bytes) and initialize all bits to 0. Now read through the list of telephone numbers and convert each telephone number into in integer, i, between 0 an 9,999,999. Now set the ith bit of the bit vector to 1. bitVector = 1;
Now iterate thought the bit vector from bitVector

• through bitVector[9,999,999] and if the bit is set format the index i, as a 7 digit telephone number, and print it.
  Note: This problem was used as a Google Interview question.

[hutch--]

Generate an exhaustive linear list of 7 digit numbers then shuffle them to make them random, no duplicates.

[zedd151]

Generate an exhaustive linear list of 7 digit numbers then shuffle them to make them random, no duplicates.

I see your line of thinking,  except that deviates from the given criteria:

Problem: Given a list of one million random 7-digit phone numbers write a program that prints a sorted list of the phone numbers with duplicates removed, using less than 2 M Bytes of memory and that runs in linear time.

[jj2007]

Generate an exhaustive linear list of 7 digit numbers then shuffle them to make them random, no duplicates.

Rand(1, 50, numbers() As DWORD, unique:6)            ; min, max, array, unique:n: get 6 unique elements in the range 1...49

Feasible but attention, if you set elements=1000000, unique:elements, you run into serious performance issues

[hutch--]

 

Do it with a hash table and keep pouring them through until you have the count you want.

[jj2007]

Do it with a hash table and keep pouring them through until you have the count you want.

We are talking DWORDs here, not strings.

[hutch--]

That can be done with a hash table but there is another technique, a bucket sort if you have enough memory, one pass in, one pass out. It may not fit into the memory constraint criterion but done right, its fast.

[jj2007]

I'll call it BitSort, and it will be added to the next MasmBasic version - source & exe attached. The algo is simple and 160 bytes short. Credits go to David Maynard

Code Select Expand

invoke BitSort, pArray, elements

BitSort returns a ptr to the array in eax (or zero if HeapAlloc fails), plus #elements in ecx

It is blazing fast for not-so-high maximum values, such as "7 digit phone numbers". For example, with 100 Mio elements and range 1,000,000 ... 9,999,999, it's a factor 16 faster than nrQsortA. And, of course - no duplicates:

Code Select Expand

604 ms for sorting 7600084 elements with BitSort
10 s for sorting 100000000 elements with nrQsortA
BitSort 1000000
BitSort 1000001
BitSort 1000004
BitSort 1000005
BitSort 1000006
BitSort 1000007
BitSort 1000008
BitSort 1000010
BitSort 1000011
BitSort 1000012
BitSort 1000013
nrQsortA 1000000
nrQsortA 1000000
nrQsortA 1000000
nrQsortA 1000000
nrQsortA 1000000
nrQsortA 1000000
nrQsortA 1000001
nrQsortA 1000001
nrQsortA 1000001
nrQsortA 1000001
nrQsortA 1000001

For settings with few duplicates, nrQsortA and ArraySort can be faster, though.

[NoCforMe]

Just in case you have nothing better to do

Example:

Given a list of one million random 7-digit phone numbers write a program that prints a sorted list of the phone numbers with duplicates removed, using less than 2MB of memory and that runs in linear time

Interesting challenge, but can you explain what "runs in linear time" means? That's a term I'm not familiar with.