Login or Sign Up to become a member!
LessThanDot Site Logo

LessThanDot

A Technical Community for IT Professionals

Less Than Dot is a community of passionate IT professionals and enthusiasts dedicated to sharing technical knowledge, experience, and assistance. Inside you will find reference materials, interesting technical discussions, and expert tips and commentary. Once you register for an account you will have immediate access to the forums and all past articles and commentaries.

LTD Social Sitings

Lessthandot twitter Lessthandot Linkedin Lessthandot facebook Lessthandot rss

Note: Watch for social icons on posts by your favorite authors to follow their postings on these and other social sites.

Highly Rated Users

Forum
No Posts Rated

Top 50
Given
Received

Forum Statistics

Users
Members:
1591
Members Online:
5
Guests Online:
2

Total Post History
Posts:
80552
Topics:
18446

7-Day Post History
New Posts:
9
New Topics:
1
Active Topics:
7

Our newest member
eirikur

Other

FAQ
All times are UTC [ DST ]

Google Ads

LTD Puzzle 9: Find it

Mind Boggling Puzzles, to keep that grey matter in shape...
Forum rules
Always post answers in a "Hidecode" tag, so that others have a chance to answer the question too.
Please wait...

LTD Puzzle 9: Find it

Postby chrissie1 on Fri Aug 01, 2008 7:39 am

Given an array of 1001 elements which contains integers from 1 to 1000 inclusive. The numbers are randomly stored in the array. Only one number repeats itself. The candidate has to come up with an efficient solution for finding that duplicate given that you can access the elements of an array only once i.e., you can read the elements of the array only once.

Nicked from here http://www.techinterviews.in/programmin ... tricks/119


Lets make that a bit more interesting shall we.

First create the array randomly and the one number randomly. But use 10 million integers plus one of course. Do this 10 times and show the times it takes to find the number and then the average time. Fastest wins.
pink fuzzy slippers
User avatar
chrissie1
Senior Guru
Senior Guru
LTD Gold - Rating: 2088LTD Gold - Rating: 2088LTD Gold - Rating: 2088LTD Gold - Rating: 2088LTD Gold - Rating: 2088
LTD Gold - Rating: 2088LTD Gold - Rating: 2088LTD Gold - Rating: 2088LTD Gold - Rating: 2088LTD Gold - Rating: 2088
LTD Gold - Rating: 2088LTD Gold - Rating: 2088
 
Posts: 9348
Joined: Wed Oct 10, 2007 7:18 pm
Location: Belgium
Unrated

Re: LTD Puzzle 9: Find it

Postby Emtucifor on Fri Aug 01, 2008 7:06 pm

A slow program on a screaming machine might beat a super-fast program on an outdated machine. So I have an idea to allow for this:

We can pick some likely easy-to-run code (like VB code that can run in any Office application). Anyone who has additional code that they can run on their machine can submit their times as well. Then each submitted program can be benchmarked against these. For example, if you have:

Code A : 10 seconds
Code B : 22.2 seconds

• Someone submits Code C which runs at 45 seconds, and on his machine Code A takes 41 seconds, then you can give him an adjusted score of 11 seconds.
• Someone who can't run Code A or B but can run Code C submits code D. His times are: Code C: 17 seconds, Code D: 13 seconds. Adjusting C to 11 we can get his relative time of 8.4 seconds.
• Similarly, someone who can run Code B but not any of the others can still get benchmarked properly.

I *am* assuming that the various programs will run with approximately equal times, but unless someone can run all the submitted programs on a single machine, I can't think of another way to fairly compare execution times.

I'd also like to point out that with randomness, someone will eventually get lucky and find the duplicate value relatively early in each of the 10 attempts. People can run the 10 searches 10,000 times looking for the shortest execution time and submit only that.
God cries a little bit every time someone builds a database.
User avatar
Emtucifor
Guru
Guru
LTD Gold - Rating: 1030LTD Gold - Rating: 1030LTD Gold - Rating: 1030LTD Gold - Rating: 1030LTD Gold - Rating: 1030
LTD Gold - Rating: 1030LTD Gold - Rating: 1030LTD Gold - Rating: 1030LTD Gold - Rating: 1030LTD Gold - Rating: 1030
LTD Gold - Rating: 1030
 
Posts: 2835
Joined: Fri May 30, 2008 9:30 pm
Location: Bellingham, WA
Unrated

Re: LTD Puzzle 9: Find it

Postby chrissie1 on Fri Aug 01, 2008 7:08 pm

I'll try and run all of them. If I can ;-)
pink fuzzy slippers
User avatar
chrissie1
Senior Guru
Senior Guru
LTD Gold - Rating: 2088LTD Gold - Rating: 2088LTD Gold - Rating: 2088LTD Gold - Rating: 2088LTD Gold - Rating: 2088
LTD Gold - Rating: 2088LTD Gold - Rating: 2088LTD Gold - Rating: 2088LTD Gold - Rating: 2088LTD Gold - Rating: 2088
LTD Gold - Rating: 2088LTD Gold - Rating: 2088
 
Posts: 9348
Joined: Wed Oct 10, 2007 7:18 pm
Location: Belgium
Unrated

Re: LTD Puzzle 9: Find it

Postby Remou on Fri Aug 01, 2008 7:11 pm

Including any lolcat submissions, I hope :P
Stop quoting laws to us. We carry swords.
User avatar
Remou
LTD Admin
LTD Admin
LTD Gold - Rating: 948LTD Gold - Rating: 948LTD Gold - Rating: 948LTD Gold - Rating: 948LTD Gold - Rating: 948
LTD Gold - Rating: 948LTD Gold - Rating: 948LTD Gold - Rating: 948LTD Gold - Rating: 948LTD Gold - Rating: 948
LTD Gold - Rating: 948
 
Posts: 5303
Joined: Sun Oct 14, 2007 11:26 am
Unrated

Re: LTD Puzzle 9: Find it

Postby b3orn on Sat Aug 02, 2008 10:03 am

My solution. I had to use numpy because of the dimension of the array. It's written in python, so the performances are not as it was written in C but I've always post my solutions in python and I'll continue along this way :)

Code is hidden, SHOW


And this is the output:
  1. Creating array of 10000000 elements
  2. Array created (intruder is 615850)!
  3. Intruder is 615850
  4. Time 1: 0.039930
  5. Creating array of 10000000 elements
  6. Array created (intruder is 6878589)!
  7. Intruder is 6878589
  8. Time 2: 0.039849
  9. Creating array of 10000000 elements
  10. Array created (intruder is 1179513)!
  11. Intruder is 1179513
  12. Time 3: 0.040164
  13. Creating array of 10000000 elements
  14. Array created (intruder is 5443723)!
  15. Intruder is 5443723
  16. Time 4: 0.040021
  17. Creating array of 10000000 elements
  18. Array created (intruder is 5792156)!
  19. Intruder is 5792156
  20. Time 5: 0.040024
  21. Creating array of 10000000 elements
  22. Array created (intruder is 5213837)!
  23. Intruder is 5213837
  24. Time 6: 0.039809
  25. Creating array of 10000000 elements
  26. Array created (intruder is 9451671)!
  27. Intruder is 9451671
  28. Time 7: 0.046713
  29. Creating array of 10000000 elements
  30. Array created (intruder is 6903729)!
  31. Intruder is 6903729
  32. Time 8: 0.046839
  33. Creating array of 10000000 elements
  34. Array created (intruder is 1059948)!
  35. Intruder is 1059948
  36. Time 9: 0.046524
  37. Creating array of 10000000 elements
  38. Array created (intruder is 2138564)!
  39. Intruder is 2138564
  40. Time 10: 0.046686
  41. Average time: 0.042656
b3orn
Apprentice
Apprentice
LTD Bronze - Rating: 37
 
Posts: 9
Joined: Thu Jul 17, 2008 3:23 pm

Re: LTD Puzzle 9: Find it

Postby chrissie1 on Sat Aug 02, 2008 3:19 pm

SO linq isn't all that fast but it is a vey short way to find the number.

Here is the code for VB.Net

First the Class

Code is hidden, SHOW


then the Module

Code is hidden, SHOW


And here are the pathetic results.

  1. Starting filling array
  2. Making random number
  3. Random number is: 4721158
  4. Filling array took: 90 milliseconds
  5. Shuffeling array
  6. Shuffeling took: 2033 milliseconds
  7. Finding the number
  8. Number found:4721158
  9. Finding the number took: 19615 milliseconds
  10. Starting filling array
  11. Making random number
  12. Random number is: 6706025
  13. Filling array took: 74 milliseconds
  14. Shuffeling array
  15. Shuffeling took: 2007 milliseconds
  16. Finding the number
  17. Number found:670602
  18. Finding the number took: 20155 milliseconds
  19. Starting filling array
  20. Making random number
  21. Random number is: 9181260
  22. Filling array took: 65 milliseconds
  23. Shuffeling array
  24. Shuffeling took: 1995 milliseconds
  25. Finding the number
  26. Number found:9181260
  27. Finding the number took: 20824 milliseconds
  28. Starting filling array
  29. Making random number
  30. Random number is: 9737667
  31. Filling array took: 65 milliseconds
  32. Shuffeling array
  33. Shuffeling took: 2004 milliseconds
  34. Finding the number
  35. Number found:9737667
  36. Finding the number took: 22090 milliseconds
  37. Starting filling array
  38. Making random number
  39. Random number is: 4721158
  40. Filling array took: 62 milliseconds
  41. Shuffeling array
  42. Shuffeling took: 1952 milliseconds
  43. Finding the number
  44. Number found:4721158
  45. Finding the number took: 21096 milliseconds
  46. Starting filling array
  47. Making random number
  48. Random number is: 9389003
  49. Filling array took: 59 milliseconds
  50. Shuffeling array
  51. Shuffeling took: 1944 milliseconds
  52. Finding the number
  53. Number found:9389003
  54. Finding the number took: 23518 milliseconds
  55. Starting filling array
  56. Making random number
  57. Random number is: 9214280
  58. Filling array took: 61 milliseconds
  59. Shuffeling array
  60. Shuffeling took: 1943 milliseconds
  61. Finding the number
  62. Number found:9214280
  63. Finding the number took: 20082 milliseconds
  64. Starting filling array
  65. Making random number
  66. Random number is: 294075
  67. Filling array took: 62 milliseconds
  68. Shuffeling array
  69. Shuffeling took: 1990 milliseconds
  70. Finding the number
  71. Number found:294075
  72. Finding the number took: 21716 milliseconds
  73. Starting filling array
  74. Making random number
  75. Random number is: 6847728
  76. Filling array took: 62 milliseconds
  77. Shuffeling array
  78. Shuffeling took: 1956 milliseconds
  79. Finding the number
  80. Number found:6847728
  81. Finding the number took: 22605 milliseconds
  82. Starting filling array
  83. Making random number
  84. Random number is: 7752800
  85. Filling array took: 62 milliseconds
  86. Shuffeling array
  87. Shuffeling took: 1947 milliseconds
  88. Finding the number
  89. Number found:7752800
  90. Finding the number took: 23195 milliseconds
  91. Finished
  92. Average time to find: 21489,6
pink fuzzy slippers
User avatar
chrissie1
Senior Guru
Senior Guru
LTD Gold - Rating: 2088LTD Gold - Rating: 2088LTD Gold - Rating: 2088LTD Gold - Rating: 2088LTD Gold - Rating: 2088
LTD Gold - Rating: 2088LTD Gold - Rating: 2088LTD Gold - Rating: 2088LTD Gold - Rating: 2088LTD Gold - Rating: 2088
LTD Gold - Rating: 2088LTD Gold - Rating: 2088
 
Posts: 9348
Joined: Wed Oct 10, 2007 7:18 pm
Location: Belgium
Unrated

Re: LTD Puzzle 9: Find it

Postby chrissie1 on Sat Aug 02, 2008 3:21 pm

BTW b3orn what is the timescale of your results? seconds? milliseconds? hours?
pink fuzzy slippers
User avatar
chrissie1
Senior Guru
Senior Guru
LTD Gold - Rating: 2088LTD Gold - Rating: 2088LTD Gold - Rating: 2088LTD Gold - Rating: 2088LTD Gold - Rating: 2088
LTD Gold - Rating: 2088LTD Gold - Rating: 2088LTD Gold - Rating: 2088LTD Gold - Rating: 2088LTD Gold - Rating: 2088
LTD Gold - Rating: 2088LTD Gold - Rating: 2088
 
Posts: 9348
Joined: Wed Oct 10, 2007 7:18 pm
Location: Belgium
Unrated

Re: LTD Puzzle 9: Find it

Postby b3orn on Sat Aug 02, 2008 5:43 pm

Sorry, they are in seconds :P
b3orn
Apprentice
Apprentice
LTD Bronze - Rating: 37
 
Posts: 9
Joined: Thu Jul 17, 2008 3:23 pm
Unrated

Re: LTD Puzzle 9: Find it

Postby chrissie1 on Sat Aug 02, 2008 7:30 pm

Ok you beat linq ;-)

But I made a better version.

Code is hidden, SHOW


  1. Starting filling array
  2. Making random number
  3. Random number is: 3641362
  4. Filling array took: 118 milliseconds
  5. Shuffeling array
  6. Shuffeling took: 1977 milliseconds
  7. Finding the number
  8. Number found:3641362
  9. Finding the number took: 874 milliseconds
  10. Starting filling array
  11. Making random number
  12. Random number is: 6149617
  13. Filling array took: 66 milliseconds
  14. Shuffeling array
  15. Shuffeling took: 1947 milliseconds
  16. Finding the number
  17. Number found:6149617
  18. Finding the number took: 896 milliseconds
  19. Starting filling array
  20. Making random number
  21. Random number is: 294075
  22. Filling array took: 61 milliseconds
  23. Shuffeling array
  24. Shuffeling took: 1951 milliseconds
  25. Finding the number
  26. Number found:294075
  27. Finding the number took: 889 milliseconds
  28. Starting filling array
  29. Making random number
  30. Random number is: 9214280
  31. Filling array took: 61 milliseconds
  32. Shuffeling array
  33. Shuffeling took: 1953 milliseconds
  34. Finding the number
  35. Number found:9214280
  36. Finding the number took: 890 milliseconds
  37. Starting filling array
  38. Making random number
  39. Random number is: 2387626
  40. Filling array took: 61 milliseconds
  41. Shuffeling array
  42. Shuffeling took: 1953 milliseconds
  43. Finding the number
  44. Number found:2387626
  45. Finding the number took: 884 milliseconds
  46. Starting filling array
  47. Making random number
  48. Random number is: 2944034
  49. Filling array took: 59 milliseconds
  50. Shuffeling array
  51. Shuffeling took: 1946 milliseconds
  52. Finding the number
  53. Number found:2944034
  54. Finding the number took: 893 milliseconds
  55. Starting filling array
  56. Making random number
  57. Random number is: 1864238
  58. Filling array took: 61 milliseconds
  59. Shuffeling array
  60. Shuffeling took: 1951 milliseconds
  61. Finding the number
  62. Number found:1864238
  63. Finding the number took: 889 milliseconds
  64. Starting filling array
  65. Making random number
  66. Random number is: 784443
  67. Filling array took: 59 milliseconds
  68. Shuffeling array
  69. Shuffeling took: 1956 milliseconds
  70. Finding the number
  71. Number found:784443
  72. Finding the number took: 889 milliseconds
  73. Starting filling array
  74. Making random number
  75. Random number is: 9704648
  76. Filling array took: 63 milliseconds
  77. Shuffeling array
  78. Shuffeling took: 1949 milliseconds
  79. Finding the number
  80. Number found:9704648
  81. Finding the number took: 892 milliseconds
  82. Starting filling array
  83. Making random number
  84. Random number is: 3849105
  85. Filling array took: 61 milliseconds
  86. Shuffeling array
  87. Shuffeling took: 1946 milliseconds
  88. Finding the number
  89. Number found:3849105
  90. Finding the number took: 892 milliseconds
  91. Finished
  92. Average time to find: 888,8
  93.  


That is 20 times faster then linq.
pink fuzzy slippers
User avatar
chrissie1
Senior Guru
Senior Guru
LTD Gold - Rating: 2088LTD Gold - Rating: 2088LTD Gold - Rating: 2088LTD Gold - Rating: 2088LTD Gold - Rating: 2088
LTD Gold - Rating: 2088LTD Gold - Rating: 2088LTD Gold - Rating: 2088LTD Gold - Rating: 2088LTD Gold - Rating: 2088
LTD Gold - Rating: 2088LTD Gold - Rating: 2088
 
Posts: 9348
Joined: Wed Oct 10, 2007 7:18 pm
Location: Belgium

Re: LTD Puzzle 9: Find it

Postby chrissie1 on Sat Aug 02, 2008 7:39 pm

Added a little something and made it even faster.

Code is hidden, SHOW


  1. Starting filling array
  2. Making random number
  3. Random number is: 2944034
  4. Filling array took: 125 milliseconds
  5. Shuffeling array
  6. Shuffeling took: 1959 milliseconds
  7. Finding the number
  8. Number found:2944034
  9. Finding the number took: 855 milliseconds
  10. Starting filling array
  11. Making random number
  12. Random number is: 8276188
  13. Filling array took: 61 milliseconds
  14. Shuffeling array
  15. Shuffeling took: 1966 milliseconds
  16. Finding the number
  17. Number found:8276188
  18. Finding the number took: 717 milliseconds
  19. Starting filling array
  20. Making random number
  21. Random number is: 3849105
  22. Filling array took: 59 milliseconds
  23. Shuffeling array
  24. Shuffeling took: 1966 milliseconds
  25. Finding the number
  26. Number found:3849105
  27. Finding the number took: 388 milliseconds
  28. Starting filling array
  29. Making random number
  30. Random number is: 8483931
  31. Filling array took: 61 milliseconds
  32. Shuffeling array
  33. Shuffeling took: 1965 milliseconds
  34. Finding the number
  35. Number found:8483931
  36. Finding the number took: 114 milliseconds
  37. Starting filling array
  38. Making random number
  39. Random number is: 5626229
  40. Filling array took: 62 milliseconds
  41. Shuffeling array
  42. Shuffeling took: 1973 milliseconds
  43. Finding the number
  44. Number found:5626229
  45. Finding the number took: 681 milliseconds
  46. Starting filling array
  47. Making random number
  48. Random number is: 1864238
  49. Filling array took: 62 milliseconds
  50. Shuffeling array
  51. Shuffeling took: 1965 milliseconds
  52. Finding the number
  53. Number found:1864238
  54. Finding the number took: 373 milliseconds
  55. Starting filling array
  56. Making random number
  57. Random number is: 8657872
  58. Filling array took: 60 milliseconds
  59. Shuffeling array
  60. Shuffeling took: 1970 milliseconds
  61. Finding the number
  62. Number found:8657872
  63. Finding the number took: 830 milliseconds
  64. Starting filling array
  65. Making random number
  66. Random number is: 7262432
  67. Filling array took: 63 milliseconds
  68. Shuffeling array
  69. Shuffeling took: 1976 milliseconds
  70. Finding the number
  71. Number found:7262432
  72. Finding the number took: 704 milliseconds
  73. Starting filling array
  74. Making random number
  75. Random number is: 5452289
  76. Filling array took: 61 milliseconds
  77. Shuffeling array
  78. Shuffeling took: 1970 milliseconds
  79. Finding the number
  80. Number found:5452289
  81. Finding the number took: 778 milliseconds
  82. Starting filling array
  83. Making random number
  84. Random number is: 3292698
  85. Filling array took: 60 milliseconds
  86. Shuffeling array
  87. Shuffeling took: 1965 milliseconds
  88. Finding the number
  89. Number found:3292698
  90. Finding the number took: 572 milliseconds
  91. Finished
  92. Average time to find: 601,2
  93.  


and allthough this is faster, it is highly variable.
pink fuzzy slippers
User avatar
chrissie1
Senior Guru
Senior Guru
LTD Gold - Rating: 2088LTD Gold - Rating: 2088LTD Gold - Rating: 2088LTD Gold - Rating: 2088LTD Gold - Rating: 2088
LTD Gold - Rating: 2088LTD Gold - Rating: 2088LTD Gold - Rating: 2088LTD Gold - Rating: 2088LTD Gold - Rating: 2088
LTD Gold - Rating: 2088LTD Gold - Rating: 2088
 
Posts: 9348
Joined: Wed Oct 10, 2007 7:18 pm
Location: Belgium
Unrated

Re: LTD Puzzle 9: Find it

Postby Emtucifor on Sat Aug 02, 2008 8:30 pm

days :lol:
God cries a little bit every time someone builds a database.
User avatar
Emtucifor
Guru
Guru
LTD Gold - Rating: 1030LTD Gold - Rating: 1030LTD Gold - Rating: 1030LTD Gold - Rating: 1030LTD Gold - Rating: 1030
LTD Gold - Rating: 1030LTD Gold - Rating: 1030LTD Gold - Rating: 1030LTD Gold - Rating: 1030LTD Gold - Rating: 1030
LTD Gold - Rating: 1030
 
Posts: 2835
Joined: Fri May 30, 2008 9:30 pm
Location: Bellingham, WA
Unrated

Re: LTD Puzzle 9: Find it

Postby tarwn on Sun Aug 03, 2008 6:13 pm

Been playing with this most of the morning. Tried a Python version that was fairly slow, a VBScript version that redefined slow, and the C# methods below. Best one I had appeared to be a Sum method (using the non-threaded option) which came in at 96-103ms running from visual studio (was getting about 30-35ms less running the executable outside the debugger).

Code is hidden, SHOW


And the full code containing a boolean array method, a quicksort method, and the test cases:
Code is hidden, SHOW


My results were (all times in ms):
  1. ------ Sum ------
  2. 10 Loops of 10,000,000 chunksize (threaded): 117.1875
  3. 10 Loops of 1,000,000 chunksize (threaded): 126.5625
  4. 10 Loops of 500,000 chunksize (threaded): 128.125
  5. 10 Loops of 100,000 chunksize (threaded): 134.375
  6. 10 Loops of 50,000 chunksize (threaded): 135.9375
  7. 10 Loops of 10,000 chunksize (threaded): 121.875
  8. 10 Loops of 10,00 chunksize (threaded): 126.5625
  9. 10 Loops of 500 chunksize (threaded): 137.5
  10. 10 Loops of 10,000,000 chunksize (not threaded): 103.125
  11. 10 Loops of 1,000,000 chunksize (not threaded): 103.125
  12. 10 Loops of 500,000 chunksize (not threaded): 106.25
  13. 10 Loops of 100,000 chunksize (not threaded): 101.5625
  14. 10 Loops of 50,000 chunksize (not threaded): 106.25
  15. 10 Loops of 10,000 chunksize (not threaded): 93.75
  16. 10 Loops of 1,000 chunksize (not threaded): 96.875
  17. 10 Loops of 500 chunksize (not threaded): 96.875
  18. ------ Sum2 ------
  19. 10 Loops of 10,000,000 chunksize (threaded): 628.125
  20. 10 Loops of 1,000,000 chunksize (threaded): 542.1875
  21. 10 Loops of 500,000 chunksize (threaded): 625
  22. 10 Loops of 100,000 chunksize (threaded): 637.5
  23. 10 Loops of 50,000 chunksize (threaded): 629.6875
  24. 10 Loops of 10,000 chunksize (threaded): 726.5625
  25. 10 Loops of 1,000 chunksize (threaded): 548.4375
  26. 10 Loops of 500 chunksize (threaded): 621.875
  27. 10 Loops of 10,000,000 chunksize (not threaded): 542.1875
  28. 10 Loops of 1,000,000 chunksize (not threaded): 570.3125
  29. 10 Loops of 500,000 chunksize (not threaded): 570.3125
  30. 10 Loops of 100,000 chunksize (not threaded): 637.5
  31. 10 Loops of 50,000 chunksize (not threaded): 595.3125
  32. 10 Loops of 10,000 chunksize (not threaded): 532.8125
  33. 10 Loops of 1,000 chunksize (not threaded): 576.5625
  34. 10 Loops of 500 chunksize (not threaded): 596.875
  35. ------ Sort ------
  36. 10 Loops (not threaded): 1715.625


* Sum2 is actually a boolean table method that I forgot to rename :P

Um, yeah...I'm going to need you to come in on Saturday -- Bill Lumbergh, Office Space
User avatar
tarwn
LTD Admin
LTD Admin
LTD Gold - Rating: 813LTD Gold - Rating: 813LTD Gold - Rating: 813LTD Gold - Rating: 813LTD Gold - Rating: 813
LTD Gold - Rating: 813LTD Gold - Rating: 813LTD Gold - Rating: 813LTD Gold - Rating: 813LTD Gold - Rating: 813
LTD Gold - Rating: 813
 
Posts: 3671
Joined: Fri Oct 12, 2007 11:10 am
Location: Raleigh, NC, USA

Re: LTD Puzzle 9: Find it

Postby tarwn on Sun Aug 03, 2008 6:24 pm

Chrissie's Code on my PC (with latest additions before my prior post - fulloutput is available but hidden to save space): 640.5 ms avg
Code is hidden, SHOW


My full output from one selected set to fulfill the instructions above:
Code is hidden, SHOW


I don't have numpy so I can't run the python one locally. Sorry. (but without numpy it was in the 14s range, if that helps :) )

Um, yeah...I'm going to need you to come in on Saturday -- Bill Lumbergh, Office Space
User avatar
tarwn
LTD Admin
LTD Admin
LTD Gold - Rating: 813LTD Gold - Rating: 813LTD Gold - Rating: 813LTD Gold - Rating: 813LTD Gold - Rating: 813
LTD Gold - Rating: 813LTD Gold - Rating: 813LTD Gold - Rating: 813LTD Gold - Rating: 813LTD Gold - Rating: 813
LTD Gold - Rating: 813
 
Posts: 3671
Joined: Fri Oct 12, 2007 11:10 am
Location: Raleigh, NC, USA
Unrated

Re: LTD Puzzle 9: Find it

Postby chrissie1 on Sun Aug 03, 2008 6:31 pm

(Edit: Warning, the comment below is a spoiler - hidden by request)


I was thinking about multithreading but I think it will only be really usefull on a multicore systeM;
pink fuzzy slippers
User avatar
chrissie1
Senior Guru
Senior Guru
LTD Gold - Rating: 2088LTD Gold - Rating: 2088LTD Gold - Rating: 2088LTD Gold - Rating: 2088LTD Gold - Rating: 2088
LTD Gold - Rating: 2088LTD Gold - Rating: 2088LTD Gold - Rating: 2088LTD Gold - Rating: 2088LTD Gold - Rating: 2088
LTD Gold - Rating: 2088LTD Gold - Rating: 2088
 
Posts: 9348
Joined: Wed Oct 10, 2007 7:18 pm
Location: Belgium
Unrated

Re: LTD Puzzle 9: Find it

Postby tarwn on Sun Aug 03, 2008 6:33 pm

The first one is basically what the python one does also, unfortunately I didn't notice he had done that until i had started mine, so I had to try some other methods also :P

Yeah, my systems are only single core. I'm thinking about going upstairs and trying it on my wife's dual...

Um, yeah...I'm going to need you to come in on Saturday -- Bill Lumbergh, Office Space
User avatar
tarwn
LTD Admin
LTD Admin
LTD Gold - Rating: 813LTD Gold - Rating: 813LTD Gold - Rating: 813LTD Gold - Rating: 813LTD Gold - Rating: 813
LTD Gold - Rating: 813LTD Gold - Rating: 813LTD Gold - Rating: 813LTD Gold - Rating: 813LTD Gold - Rating: 813
LTD Gold - Rating: 813
 
Posts: 3671
Joined: Fri Oct 12, 2007 11:10 am
Location: Raleigh, NC, USA
Unrated

Re: LTD Puzzle 9: Find it

Postby Emtucifor on Sun Aug 03, 2008 7:29 pm

(Edit: Quoted comment was a spoiler, hidden by request)
[hide]
Chrissie1 wrote:Clever you added them all up and substracted the totalamount thus giving you the dupe.
[/hide]
This was a pretty big unhidden spoiler, there.
God cries a little bit every time someone builds a database.
User avatar
Emtucifor
Guru
Guru
LTD Gold - Rating: 1030LTD Gold - Rating: 1030LTD Gold - Rating: 1030LTD Gold - Rating: 1030LTD Gold - Rating: 1030
LTD Gold - Rating: 1030LTD Gold - Rating: 1030LTD Gold - Rating: 1030LTD Gold - Rating: 1030LTD Gold - Rating: 1030
LTD Gold - Rating: 1030
 
Posts: 2835
Joined: Fri May 30, 2008 9:30 pm
Location: Bellingham, WA
Unrated

Re: LTD Puzzle 9: Find it

Postby shamsm on Thu Aug 07, 2008 10:53 pm

Here's a solution in java, it uses a boolean operation to find the duplicate

Code is hidden, SHOW


  1. "C:\Program Files\Java\jdk1.6.0_06\bin\java" -Xms256M -Xmx768M Puzzle09
  2. Time to create random array: 8578 milliseconds
  3. Found Duplicate: 7595666
  4. Time to find duplicate: 33 milliseconds
  5. Time to create random array: 8811 milliseconds
  6. Found Duplicate: 1588217
  7. Time to find duplicate: 33 milliseconds
  8. Time to create random array: 7935 milliseconds
  9. Found Duplicate: 8314017
  10. Time to find duplicate: 31 milliseconds
  11. Time to create random array: 7824 milliseconds
  12. Found Duplicate: 3222235
  13. Time to find duplicate: 31 milliseconds
  14. Time to create random array: 8367 milliseconds
  15. Found Duplicate: 8127512
  16. Time to find duplicate: 30 milliseconds
  17. Time to create random array: 8434 milliseconds
  18. Found Duplicate: 3449360
  19. Time to find duplicate: 30 milliseconds
  20. Time to create random array: 8071 milliseconds
  21. Found Duplicate: 1969631
  22. Time to find duplicate: 33 milliseconds
  23. Time to create random array: 8059 milliseconds
  24. Found Duplicate: 2830737
  25. Time to find duplicate: 39 milliseconds
  26. Time to create random array: 8252 milliseconds
  27. Found Duplicate: 6042436
  28. Time to find duplicate: 30 milliseconds
  29. Time to create random array: 7820 milliseconds
  30. Found Duplicate: 6534775
  31. Time to find duplicate: 30 milliseconds
  32. Average Time to find the duplicate: 32.0 milliseconds
  33.  
shamsm
Apprentice
Apprentice
LTD Bronze - Rating: 47
 
Posts: 12
Joined: Wed Jul 30, 2008 10:09 am

Re: LTD Puzzle 9: Find it

Postby tisodotsk on Fri Aug 08, 2008 2:59 pm

My solution in PHP:

Code is hidden, SHOW


Output:
  1. 1. needle is: 1593323, founded: 1593323 (2.03187799454 seconds)
  2. 2. needle is: 2869263, founded: 2869263 (2.11517190933 seconds)
  3. 3. needle is: 5696717, founded: 5696717 (2.13595414162 seconds)
  4. 4. needle is: 2639161, founded: 2639161 (2.15742897987 seconds)
  5. 5. needle is: 3115540, founded: 3115540 (2.14666700363 seconds)
  6. 6. needle is: 3790894, founded: 3790894 (2.18299603462 seconds)
  7. 7. needle is: 1154480, founded: 1154480 (2.16829895973 seconds)
  8. 8. needle is: 2535401, founded: 2535401 (2.21659994125 seconds)
  9. 9. needle is: 6805726, founded: 6805726 (2.23850607872 seconds)
  10. 10. needle is: 1021119, founded: 1021119 (2.24144291878 seconds)
  11. average time: 2.16349439621 seconds
I try to improve my English language skills. Most things i do better than this.
tisodotsk
Apprentice
Apprentice
LTD Bronze - Rating: 62LTD Bronze - Rating: 62
 
Posts: 22
Joined: Fri Aug 08, 2008 12:45 pm
Location: Bratislava, Slovakia

Re: LTD Puzzle 9: Find it

Postby chrissie1 on Fri Aug 08, 2008 3:06 pm

I am surprised by the "very" big differences between languages. I guess the algorithm is crucial here.
pink fuzzy slippers
User avatar
chrissie1
Senior Guru
Senior Guru
LTD Gold - Rating: 2088LTD Gold - Rating: 2088LTD Gold - Rating: 2088LTD Gold - Rating: 2088LTD Gold - Rating: 2088
LTD Gold - Rating: 2088LTD Gold - Rating: 2088LTD Gold - Rating: 2088LTD Gold - Rating: 2088LTD Gold - Rating: 2088
LTD Gold - Rating: 2088LTD Gold - Rating: 2088
 
Posts: 9348
Joined: Wed Oct 10, 2007 7:18 pm
Location: Belgium
Unrated

Re: LTD Puzzle 9: Find it

Postby AlexCuse on Fri Aug 08, 2008 3:11 pm

I started working on this the other night and then I realized I don't really understand the question. Can you explain what you mean by "create the array randomly"? Does that just mean a random starting value, then take the next 10 million?
Say what you like about the tenets of National Socialism Dude, at least it's an ethos
User avatar
AlexCuse
LTD Admin
LTD Admin
LTD Gold - Rating: 1021LTD Gold - Rating: 1021LTD Gold - Rating: 1021LTD Gold - Rating: 1021LTD Gold - Rating: 1021
LTD Gold - Rating: 1021LTD Gold - Rating: 1021LTD Gold - Rating: 1021LTD Gold - Rating: 1021LTD Gold - Rating: 1021
LTD Gold - Rating: 1021
 
Posts: 5411
Joined: Tue Oct 09, 2007 5:26 pm
Location: Pennsylvania, US
Unrated

Re: LTD Puzzle 9: Find it

Postby chrissie1 on Fri Aug 08, 2008 3:16 pm

Nope every number should be in a random place. Or do what most people do. Create an array of 10 milion , add the random number and then shuffle them around so that the numbers are in random order.
pink fuzzy slippers
User avatar
chrissie1
Senior Guru
Senior Guru
LTD Gold - Rating: 2088LTD Gold - Rating: 2088LTD Gold - Rating: 2088LTD Gold - Rating: 2088LTD Gold - Rating: 2088
LTD Gold - Rating: 2088LTD Gold - Rating: 2088LTD Gold - Rating: 2088LTD Gold - Rating: 2088LTD Gold - Rating: 2088
LTD Gold - Rating: 2088LTD Gold - Rating: 2088
 
Posts: 9348
Joined: Wed Oct 10, 2007 7:18 pm
Location: Belgium
Unrated

Re: LTD Puzzle 9: Find it

Postby b3orn on Fri Aug 08, 2008 3:44 pm

I think the right way to do this puzzle is the one shamsm, tarwn and I followed. shamsm did a great job enhancing it using a bitwise operator (very good work, are you a c/c++ programmer?)
b3orn
Apprentice
Apprentice
LTD Bronze - Rating: 37
 
Posts: 9
Joined: Thu Jul 17, 2008 3:23 pm
Unrated

Re: LTD Puzzle 9: Find it

Postby AlexCuse on Sat Aug 09, 2008 5:56 pm

I'm sure this has some room for optimization (about 3 seconds per pass), but I am just not that good with F# yet. Maybe I will revisit after some more puzzles:

Code is hidden, SHOW
Say what you like about the tenets of National Socialism Dude, at least it's an ethos
User avatar
AlexCuse
LTD Admin
LTD Admin
LTD Gold - Rating: 1021LTD Gold - Rating: 1021LTD Gold - Rating: 1021LTD Gold - Rating: 1021LTD Gold - Rating: 1021
LTD Gold - Rating: 1021LTD Gold - Rating: 1021LTD Gold - Rating: 1021LTD Gold - Rating: 1021LTD Gold - Rating: 1021
LTD Gold - Rating: 1021
 
Posts: 5411
Joined: Tue Oct 09, 2007 5:26 pm
Location: Pennsylvania, US

Re: LTD Puzzle 9: Find it

Postby shamsm on Mon Aug 11, 2008 10:01 pm

b3orn wrote:shamsm did a great job enhancing it using a bitwise operator (very good work, are you a c/c++ programmer?)


Nope a java developer :), I try to post all my solutions in java :D
shamsm
Apprentice
Apprentice
LTD Bronze - Rating: 47
 
Posts: 12
Joined: Wed Jul 30, 2008 10:09 am
Unrated

Re: LTD Puzzle 9: Find it

Postby chrissie1 on Thu Aug 28, 2008 7:24 pm

The winners for have been determined, finaly!

Peoples Champ: shamsm

LTD Admins Champion - shamsm for the bitwise operator.

Congratulations!
pink fuzzy slippers
User avatar
chrissie1
Senior Guru
Senior Guru
LTD Gold - Rating: 2088LTD Gold - Rating: 2088LTD Gold - Rating: 2088LTD Gold - Rating: 2088LTD Gold - Rating: 2088
LTD Gold - Rating: 2088LTD Gold - Rating: 2088LTD Gold - Rating: 2088LTD Gold - Rating: 2088LTD Gold - Rating: 2088
LTD Gold - Rating: 2088LTD Gold - Rating: 2088
 
Posts: 9348
Joined: Wed Oct 10, 2007 7:18 pm
Location: Belgium
Unrated

Next