This blog has moved to Medium

Subscribe via email


Archive for February 2009

Reached level 2 on Project Euler

And got me this nice cube as a reward.

.

Problems are starting to get more interesting, but not quite there yet. Still, brute force or nearly brute force solves a lot of problems. I’m somewhat surprised that I didn’t have to implement a decent primality test yet.

Cool problems to look at are 79 and 31 (hint: think of problem 18).

First non-trivial problem in Project Euler

So far, all the problems I saw were trivial, at least in the sense that some brute-force approach would work (with some optimizations perhaps).

Problem 30 is different.

After solving it, I looked in the forum. The first entry was this:


I have a question. Can you actually be sure that there is no higher number that can fit this description?
I just let my program run until it doesn’t seem to find any more solution and then manually stop it. Doesn’t feel like its a very pretty solution to it though.

You can’t formally solve this problem without a correctness proof. There is a limit beyond which there is no chance to encounter numbers relevant to the problem.
How to prove the limit? I leave that as an exercise to the reader (hint: use logarithms).

Reached level 1 in Project Euler

This is a horrible waste of time, don’t dare check out Project Euler (thanks Eli).

I just reached Level 1 after solving my first 25 problems. Still haven’t reached a problem that requires much thinking, even though Problem 17 was annoying (Eli had to think in order to solve Problem 12 in Python, for me the brute-force approach in C# just worked).

Don’t switch your lock object mid-lock

Today I encountered a weird exception from List.AddRange()

[Exception(System.ArgumentException)]:
Destination array was not long enough. Check destIndex and length, and the array's lower bounds.

Looking at the code, I saw it multithreaded like this:

List<int> tmp;
lock (_list)
{
    tmp = _list;
    _list = new List<int>(1);
}
 
// use tmp object like it's owned exclusively by this thread

The thinking here was to avoid “expensive” operations inside the lock, so we locked _list only for enough time to replace it with a new list, and then do the heavy lifting on the tmp variable (assuming no other threads can interfere). Most locks are used immutably – the lock object itself rarely changes identity.

Well, it appears the above code is indeed not thread safe. Here what I recon happened:

  1. Thread 1 acquired a lock on _list
  2. Thread 2 tried acquiring the lock, but blocked.
  3. Thread 1 changed _list to a new instance and released the lock on the old value of _list
  4. Thread 3 came and acquired the lock on the new value of _list
  5. Thread 2 was now released and acquired the lock on the old value of _list

At this point, both thread 2 & 3 got inside the critical section and grabbed the same value of _list (the new one) as their “exclusive” tmp, and then worked on it concurrently outside the lock. The easy solution is not to lock on an object whose identity (not state) changes. In this case, a lock either on the containing object or on a new custom object (object _lock = new object()) should do the trick.

This program reproduces the problem:

using System;
using System.Collections.Generic;
using System.Threading;
 
namespace tstlock
{
    public class LockTester
    {
        private List<int> _list = new List<int>(1);
 
        public void Run()
        {
            var threads = new Thread[40];
            for (int i = 0; i < threads.Length; ++i)
            {
                threads[i] = new Thread(ThreadFunc);
                threads[i].Start();
            }
            foreach (var thread in threads)
                thread.Join();
        }
 
        private void ThreadFunc()
        {
            for (int i = 0; i < 1000000; ++i)
            {
                List<int> tmp;
                lock (_list)
                {
                    tmp = _list;
 
                    // at this point _list is always supposed to be an empty list
                    // because all the additions to it are after the new list is allocated
                    _list = new List<int>(1);
                }
 
                var array = new []{1,2,3,54,5,6};
                tmp.AddRange(array);
                if (tmp.Count != array.Length)
                {
                    throw new Exception("Bug - tmp is not local as we thought");
                }
            }
        }
    }
}

Conflux draft walkthrough (Domain/5 color)

A new Magic set has been released, check out my new draft walkthrough.

C# Alternative to Directory.GetFiles()

A while ago I was working with directories with thousands of files, and wanted to get only the first few files in the directory.
Directory.GetFiles() always returns the entire directory, and so is rather slow on huge directories.

I found and used this excellent post with a managed C++ class that does exactly what I wanted. A caveat I had with the code is that it didn’t work on 64bit machines when run in 64bit mode (instead of in WOW64 compatibility mode). Today I finally got the time to translate it to C#, so we can compile it as part of our solution instead of referencing a pre-built C++ dll. I’m also included a small wrapper DirectoryUtils, that provides an easier way to get a list of N files in a dir (simple API wrapper), plus an additional method to get a random selection of N files from that directory.

using System;
using System.Collections;
using System.Collections.Generic;
using System.ComponentModel;
using System.IO;
using System.Runtime.InteropServices;
using Microsoft.Win32.SafeHandles;
using NUnit.Framework;
using FILETIME=System.Runtime.InteropServices.ComTypes.FILETIME;
using IEnumerator=System.Collections.IEnumerator;
 
namespace Semingo.IntegrationTests.DirectoryUtils
{
    public static class DirectoryUtils
    {
        /// <summary>
        /// Efficiently get only some files from a dir
        /// </summary>
        /// <param name="directory"></param>
        /// <param name="limit"></param>
        /// <returns></returns>
        public static List<string> GetFiles(string directory, int limit)
        {
            Assert.IsTrue(limit > 0, "Limit should be positive");
            List<string> result = new List<string>(limit);
            FilesFinder filesFinder = new FilesFinder(directory + "\\*.*");
            foreach (FoundFileData foundFile in filesFinder)
            {
                string fullFilename = directory + "\\" + foundFile.FileName;
                if (!IsFile(fullFilename))
                    continue;
 
                limit--;
 
                result.Add(fullFilename);
 
                if (limit == 0)
                    return result;
            }
 
            return result;
        }
 
        /// <summary>
        /// Return a random set of count files from a directory. (note, this can be slow on huge directories!)
        /// </summary>
        /// <remarks>
        /// If the directory has less files, all of it is returned
        /// </remarks>
        /// <param name="directory"></param>
        /// <param name="limit"></param>
        /// <returns></returns>
        public static List<string> GetRandomizedFiles(string directory, int limit
        {
            string[] files = Directory.GetFiles(directory);
            if (files.Length <= limit)
                return new List<string>(files);
 
            // we don't have enough, so we have to randomize
            int[] permutation = GenerateRandomPermutation(files.Length);
 
            // take first count files
            List<string> result = new List<string>(count);
            for (int i = 0; i < count; ++i)
            {
                result.Add(files[permutation[i]]);
            }
            return result;
        }
 
        private static bool IsFile(string name)
        {
            return File.Exists(name);
        }
 
        private static int[] GenerateRandomPermutation(int count)
        {
            int[] array = new int[count];
            for (int i = 0; i < count; ++i)
                array[i] = i;
 
            // http://forums.msdn.microsoft.com/en-US/csharpgeneral/thread/8b489948-f1b5-46d0-8bc5-bd94c418e41d/
            Random random = new Random();  // i.e., Random Class.  
            int n = array.Length;       // The number of items left to shuffle (loop invariant).  
            while (n > 1)
            {
                int k = random.Next(n);  // 0 <= k < n.  
                n--;                     // n is now the last pertinent index;  
                int temp = array[n];     // swap array[n] with array[k] (does nothing if k == n).  
                array[n] = array[k];
                array[k] = temp;
            }
            return array;
        }
    }
 
    /// <summary>
    /// Taken from http://blogs.msdn.com/yvesdolc/archive/2005/08/06/448673.aspx and translated to C#
    /// </summary>
    public class FilesEnumerator : IEnumerator<FoundFileData>
    {
        #region Interop imports
 
        private const int ERROR_FILE_NOT_FOUND = 2;
        private const int ERROR_NO_MORE_FILES = 18;
 
        [DllImport("kernel32.dll", SetLastError = true, CharSet = CharSet.Auto)]
        private static extern IntPtr FindFirstFile(string lpFileName, out WIN32_FIND_DATA lpFindFileData);
 
        [DllImport("kernel32.dll", SetLastError = true, CharSet = CharSet.Auto)]
        private static extern bool FindNextFile(SafeHandle hFindFile, out WIN32_FIND_DATA lpFindFileData);
 
        #endregion
 
        #region Data Members
 
        private readonly string _fileName;
        private SafeHandle _findHandle;
        private WIN32_FIND_DATA _win32FindData;
 
        #endregion
 
        public FilesEnumerator(string fileName)
        {
            _fileName = fileName;
            _findHandle = null;
            _win32FindData = new WIN32_FIND_DATA();
        }
 
        #region IEnumerator<FoundFileData> Members
 
        public FoundFileData Current
        {
            get
            {
                if (_findHandle == null)
                    throw new InvalidOperationException("MoveNext() must be called first");
 
                return new FoundFileData(ref _win32FindData);
            }
        }
 
        object IEnumerator.Current
        {
            get { return Current; }
        }
 
        public bool MoveNext()
        {
            if (_findHandle == null)
            {
                _findHandle = new SafeFileHandle(FindFirstFile(_fileName, out _win32FindData), true);
                if (_findHandle.IsInvalid)
                {
                    int lastError = Marshal.GetLastWin32Error();
                    if (lastError == ERROR_FILE_NOT_FOUND)
                        return false;
 
                    throw new Win32Exception(lastError);
                }
            }
            else
            {
                if (!FindNextFile(_findHandle, out _win32FindData))
                {
                    int lastError = Marshal.GetLastWin32Error();
                    if (lastError == ERROR_NO_MORE_FILES)
                        return false;
 
                    throw new Win32Exception(lastError);
                }
            }
 
            return true;
        }
 
        public void Reset()
        {
            if (_findHandle.IsInvalid)
                return;
 
            _findHandle.Close();
            _findHandle.SetHandleAsInvalid();
        }
 
        public void Dispose()
        {
            _findHandle.Dispose();
        }
 
        #endregion
    }
 
    public class FilesFinder : IEnumerable<FoundFileData>
    {
        readonly string _fileName;
        public FilesFinder(string fileName)
        {
            _fileName = fileName;
        }
 
        public IEnumerator<FoundFileData> GetEnumerator()
        {
            return new FilesEnumerator(_fileName);
        }
 
        IEnumerator IEnumerable.GetEnumerator()
        {
            return GetEnumerator();
        }
    }
 
    public class FoundFileData
    {
        public string AlternateFileName;
        public FileAttributes Attributes;
        public DateTime CreationTime;
        public string FileName;
        public DateTime LastAccessTime;
        public DateTime LastWriteTime;
        public UInt64 Size;
 
        internal FoundFileData(ref WIN32_FIND_DATA win32FindData)
        {
            Attributes = (FileAttributes)win32FindData.dwFileAttributes;
            CreationTime = DateTime.FromFileTime((long)
                    (((UInt64)win32FindData.ftCreationTime.dwHighDateTime << 32) +
                     (UInt64)win32FindData.ftCreationTime.dwLowDateTime));
 
            LastAccessTime = DateTime.FromFileTime((long)
                    (((UInt64)win32FindData.ftLastAccessTime.dwHighDateTime << 32) +
                     (UInt64)win32FindData.ftLastAccessTime.dwLowDateTime));
 
            LastWriteTime = DateTime.FromFileTime((long)
                    (((UInt64)win32FindData.ftLastWriteTime.dwHighDateTime << 32) +
                     (UInt64)win32FindData.ftLastWriteTime.dwLowDateTime));
 
            Size = ((UInt64)win32FindData.nFileSizeHigh << 32) + win32FindData.nFileSizeLow;
            FileName = win32FindData.cFileName;
            AlternateFileName = win32FindData.cAlternateFileName;
        }
    }
 
    /// <summary>
    /// Safely wraps handles that need to be closed via FindClose() WIN32 method (obtained by FindFirstFile())
    /// </summary>
    public class SafeFindFileHandle : SafeHandleZeroOrMinusOneIsInvalid
    {
        [DllImport("kernel32.dll", SetLastError = true)]
        private static extern bool FindClose(SafeHandle hFindFile);
 
        public SafeFindFileHandle(bool ownsHandle)
            : base(ownsHandle)
        {
        }
 
        protected override bool ReleaseHandle()
        {
            return FindClose(this);
        }
    }
 
    // The CharSet must match the CharSet of the corresponding PInvoke signature
    [StructLayout(LayoutKind.Sequential, CharSet = CharSet.Auto)]
    public struct WIN32_FIND_DATA
    {
        public uint dwFileAttributes;
        public FILETIME ftCreationTime;
        public FILETIME ftLastAccessTime;
        public FILETIME ftLastWriteTime;
        public uint nFileSizeHigh;
        public uint nFileSizeLow;
        public uint dwReserved0;
        public uint dwReserved1;
        [MarshalAs(UnmanagedType.ByValTStr, SizeConst = 260)]
        public string cFileName;
        [MarshalAs(UnmanagedType.ByValTStr, SizeConst = 14)]
        public string cAlternateFileName;
    }
}