x64 NASM Assembler: Binary Search While quarantine I decided to look into the assembly language, as it's quite interesting to see how code works on the lower levels. To challenge myself I made a binary search algorithm. The OS is Windows.
I just code casually (in Python and C++, so I know about the concept of pointers), therefore I don't have that much experience.
I just wanted to put this on code review to know if this code style is acceptable or if I'm disregarding important conventions. So please critique and let me know.
bits 64

section .text
    global main
    extern printf
    extern ExitProcess

main:
    mov r12, list       ; load list into register
    mov r13, len >> 3   ; r13 holds the width of the search "sector"
    test r13, 1         ; test if the first search "sector" is even
    jz is_even          ; if not, it's set to an even number
    inc r13
    is_even:
    push r13            ; save width
    shl r13, 2          ; multiply index by 4 to get the width in bytes
    add r12, r13        ; move the pointer to the first search position
    pop r13             ; restore width

search:
    shr r13, 1          ; halve search "sector"
    push r13
    shl r13, 2          ; get width in bytes

    mov r14d, dword [r12]
    cmp r14d, dword [target] ;compare target to current search position
    je finish
    jl search_right
    jg search_left

search_left:
    sub r12, r13   ; move search position
    pop r13
    jmp search
search_right:
    add r12, r13   ; move search position
    pop r13
    jmp search

finish:
    lea rcx, [fmt]  ; set printf format
    mov rdx, r12    ; rdx is pointer to the target
    sub rdx, list   ; we want the index of the target, so we SUB the pointer to the first element
    shr rdx, 2      ; ints are 4-byte, so we have to devide the difference by 4

    sub rsp, 40     ; shadow space
    call printf
    add rsp, 40

    mov rax, 0
    call ExitProcess

section .data
    fmt db "%d", 10, 0     ; printf format string
    target dd 123          ; number we're looking for
    list dd 4, 123 ,2584, 4510, 8451, 6987, 12543
    len equ $ - list

Code style
Your code style is certainly acceptable - everyone is entitled to their own coding habits.
To further improve readability, and readability is key, I would change the following:

put all labels in the same separate column. You didn't do this for is_even, fmt, target, list, and len.
don't just have 1 space character between the instruction/directive and its operand(s). Start all operands in their own column.
beware of redundant comments like 'mov r12, list  ; load list into register'
don't add redundant tags like dword in mov r14d, dword [r12]. The register name r14d already states this is a dword.
avoid using ambiguous terminology. I found it odd to read about sectors and widths. In case of binary searching, many people will prefer to talk about array partitions and number of elements.

The code has multiple issues
You seem to be confident that a match will always be found. No provision is made for a failure!
The comment on mov rdx, r12  ; rdx is pointer to the target is wrong. What you've got is a pointer to the matching array element.
The array list holds dword-sized elements. In mov r13, len >> 3, you only need to shift twice to get the number of elements.
In the top part of the program you first add an imaginary element to the array, then you make r12 point to behind it, and later your code also happily reads from these non-existing elements. Analyzing beyond this point becomes futile.
I think having recognized an attempt to write a uniform binary search. Although I didn't use that particular approach, you might find it interesting to read a post of mine that shows 2 ways to binary search an array. I know it was written for 16-bit, but that should not stop you from stealing from it...


Computing logits for a vector and for all vectors in a set I've had to write two different functions (shown below), but I want to combine the two functions into one. Is there a way to do this?

softmax_a_set() takes a list of numpy arrays, applies softmax() to each individual numpy array, and then returns a list of processed numpy arrays.

def softmax(a_vector):
    """Compute a logit for a vector."""
    denom = sum(numpy.exp(a_vector))
    logit = numpy.exp(a_vector)/denom
    return logit

def softmax_a_set(a_set):
    """computes logits for all vectors in a set"""
    softmax_set = numpy.zeros(a_set.shape)

    for x in range(0, len(a_set)):
        softmax_set[x] = softmax(a_set[x])

    return softmax_set

Why do you want to combine them into two functions? It’s possible, but I don’t think it would be an improvement. They’re two fairly distinct functions, and cramming the code for both into a single function would make the code less readable.

If you really need a single function that handles both, you could do something like:

def softmax(a):
    if isinstance(a, vector):
        return softmax_a_vector(a)
    elif isinstance(a, set):
        return softmax_a_set(a)

which gets what you want, but you keep the nice separation of code into distinct functions.

One other minor thing: you can improve the for loop in softmax_a_set with enumerate:

for idx, a_vector in enumerate(a_set):
    softmax_set[idx] = softmax(a_vector)


Method for finding all classes This was inspired by a Stack Overflow question about getting all the classes of an application and I took it a little too seriously (or perhaps not seriously enough).

It's rather silly to do it this way, but I believe the code below is guaranteed to find every class exposed in the scope it is called from...eventually. (As long as the class name is 255 chars or less.)

I'm looking for improvements on my coding style, hardcore criticism, and anything that would optimize this code.

application:didFinishLaunchingWithOptions

NSString * set = @"_ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789";
NSInteger setLength = 255;
NSLog(@"Here we go!");
[Enumerator enumerateAllStringCombinationsInSet:set toMaximumLength:setLength withBlock:^(NSString *string) {
    Class class = NSClassFromString(string);
    if (class != nil) {
        NSLog(@"Found one! %@", string);
    }
}];

Enumerator.m

@implementation Enumerator

+ (void)enumerateAllStringCombinationsInSet:(NSString*)set toMaximumLength:(NSInteger)maximumLength withBlock:(void(^)(NSString *string))actionBlock {

    const char *charSet = [set UTF8String];

    NSInteger i, j, k;
    NSInteger setLength = [set length];
    NSInteger lastPlace = setLength-1;
    NSInteger activePlace = 0;

    NSInteger *places = calloc(maximumLength, sizeof(NSInteger));

    char lastChar = charSet[lastPlace];
    char *cStrBuffer = calloc(maximumLength, sizeof(char));

    BOOL go = true;

    while (go) {
        // increment active place
        for (j=0; j<setLength; ++j) {
            cStrBuffer[activePlace] = charSet[j];
            places[activePlace] = j;
            actionBlock([NSString stringWithUTF8String:cStrBuffer]);
        }

        for (i=activePlace; i >= 0; --i) {
            // check for carry over / overflow
            if (cStrBuffer[i] == lastChar) {
                // carry over, set to "zero" and defer processing to one place to the left.
                if (i == 0) {
                    if (++activePlace >= maximumLength) {
                        //  maximum size has been reached because all places are maxed out
                        go = false;
                        break;
                    }
                }

                cStrBuffer[i] = charSet[0];
                places[i] = 0;

                // otherwise, check previous char
            } else {

                // safe to increment this char up
                cStrBuffer[i] = charSet[places[i]+1];
                places[i] = places[i]+1;

                if (i<activePlace) {
                    // set all trailing figures to "zero"
                    for (k = i+1; k < activePlace; ++k) {
                        cStrBuffer[k] = charSet[0];
                        places[k] = 0;
                    }
                }
                break;
            }
        }
    }

    NSLog(@"Done!");
}

@end

Output:

Started at 3:07AM

2015-10-05 03:07:38.572 ClassFinder[59704:4595935] Here we go!
2015-10-05 03:09:29.770 ClassFinder[59704:4595935] Found one! NSSet
2015-10-05 03:09:29.774 ClassFinder[59704:4595935] Found one! NSURL
2015-10-05 03:10:27.769 ClassFinder[59704:4595935] Found one! UINib
2015-10-05 03:26:32.810 ClassFinder[59704:4595935] Found one! ALCity

It's now 3:29AM and it has made it all the way to the string AcAeZP.

First and foremost, I must absolutely recommend against doing anything of this sort.

If you want to know what classes are available in the scope, you need only look up at the imports you're making.  All of the imports will either be your own files, for which you should only really have one visible class per import, or they will be library/framework imports.  The library/framework imports are likely bringing multiple classes with them, but they should be well documented.

Anything that a program like yours does manage to find is going to fall into one of two categories:

Stuff we already know about anyway.
Stuff that's undocumented and we almost certainly shouldn't be using.

And perhaps more importantly, this is incredibly inefficient.  The difference between just looking at your source code and making this run-time check is, well, your check is happening at run-time.  But, what useful thing can you actually do with that knowledge?  None, really.

More importantly, when do you know to stop looking?  There's not a character limit to class names (as far as I know).  All we can do is check literally every character combination.  The math to figure out how many combinations we need to check is:

Number of characters = N
Maximum length = M
Minimum length = m

  (N^M) - (N^(m-1))

(roughly... I might be slightly off)

If we don't impose a minimum length, and we just want to check every combination with 8 characters, we have to check 248,155,780,267,521 combinations.  That's 248 trillion, and that's just for every combination of characters up to 8 length, so forget about discovering anything that starts with NSMutable which alone is already 9 characters long before we count the last part (Array, Dictionary, Set, Data, String, etc).

If I do 63^255 on the OS X calculator, it says simply "Infinity".  While that's not technically correct, it might as well be.  And I don't even know that 255 characters is actually any sort of limit on class name length.

But, with all of this said, a little multithreading can go quite a long ways.

With two threads working on this problem, you're checking twice as many strings per cycle.  With four, four times as many, etc.  All that is required is a strategy for effectively breaking your total workload into equal chunks of work for all of the threads to work on.

And it doesn't matter if you create more threads than your CPU can actively work on.  The overhead for creating threads is relatively low.

What might make sense is to create 53 separate threads--one for each of the valid starting characters (class names can not start with numbers).  It's unlikely we'll be running this on a CPU that can simultaneously process 53 threads at a time any time soon, so this should be more than plenty to make sure we're getting maximum value out of our CPU.


Project Euler problem 14 (longest Collatz sequence) in Swift 3 I was trying to solve Project Euler:Problem 14 using Swift 3, but it takes ages to give me an answer, which is a sign that my code is absolute garbage performance-wise. What could I do to increase the performance of the code?

import UIKit

/* The following iterative sequence is defined for the set of positive integers:

 n → n/2 (n is even)
 n → 3n + 1 (n is odd)

 Using the rule above and starting with 13, we generate the following sequence:

 13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1
 It can be seen that this sequence (starting at 13 and finishing at 1) contains 10 terms. Although it has not been proved yet (Collatz Problem), it is thought that all starting numbers finish at 1.

 Which starting number, under one million, produces the longest chain?

 NOTE: Once the chain starts the terms are allowed to go above one million. */

func collatzSeq(starting: Int) -> [Int] {

    var collatzArray = [starting]

    while collatzArray.last != 1 {
        if collatzArray.last! % 2 == 0 {
            collatzArray.append(collatzArray.last!/2)
        } else {
            collatzArray.append((3*collatzArray.last!)+1)
        }
    }
    return collatzArray
}

var longestChain = 0
for index in 1...999999 {
    if collatzSeq(starting: index).count > longestChain {
        longestChain = index
        print("Starting at \(longestChain) produces the longest chain.")
    }
    }

The main performance bottleneck of your code was already pointed out in the other answers: building lots of arrays (without need).
I'll like to point out how some Swift techniques can be used to achieve
the goal in a functional (and fast) way.
First, I would separate the computation of the next Collatz number into
a separate function:
func collatzFunc(n: Int64) -> Int64? {
    if n == 1 {
        return nil
    } else if n % 2 == 0 {
        return n/2
    } else {
        return 3*n + 1
    }
}

or, using the conditional operator:
func collatzFunc(n: Int64) -> Int64? {
    return n == 1 ? nil : n % 2 == 0 ? n/2 : 3*n + 1
}

(As already pointed out in other answers, we must operate on Int64
here). For reasons which become apparent shortly, this function returns nil
when called with 1, i.e. when the sequence "ends".
Now, instead of building an array with all elements, we build a
sequence, using sequence(first:next:)
from the Swift Standard Library:

Returns a sequence formed from first and repeated lazy applications of next.
func sequence<T>(first: T, next: @escaping (T) -> T?) -> UnfoldSequence<T, (T?, Bool)>

Our collatzFunc is exactly what is needed as the next parameter.
For example,
let seq = sequence(first: 13, next: collatzFunc)

creates the Collatz sequence starting at 13. But in contrast to your
function, all elements are evaluated lazily, i.e. on demand when
the sequence is enumerated.
for n in seq { print(n) }

would print that Collatz sequence. But we need only the length,
so we define a collatzLength function. A straightforward
implementation would be
func collatzLength(n: Int) -> Int {
    var count = 0
    for _ in sequence(first: Int64(n), next: collatzFunc) {
        count += 1
    }
    return count
}

The for-loop enumerates the sequence and increments a count for
each element. Since the sequence element itself is not needed,
the "wildcard pattern" _ is used as the loop variable.
This can be written more concisely/functionally using
reduce():
func collatzLength(n: Int) -> Int {
    return sequence(first: Int64(n), next: collatzFunc)
        .reduce(0, { (count, _) in count + 1 })
}

Finally, we have to find the number (under one million) which has the
longest Collatz length. This can be done with a for-loop, as you did.
Alternatively, one can consider that as the maximum of all
(n, collatzLength(n)) pairs with respect to the second component:
let (maxN, maxLength) = (1...999_999)
    .map { ($0, collatzLength(n: $0)) }
    .max { $0.1 < $1.1 }!

This code, compiled with Xcode with optimization ("Release" configuration)
runs in about 0.8 seconds on my 1.2 GHz Intel Core m5 MacBook.

EBrown demonstrated
how to use caching/memoization to increase the performance.
Here is a similar but slightly different approach. Instead of
caching all computed values in a dictionary, cache only the
computed values for n up to a maximum value in an array.
With the cache array size equal to the maximal needed n (1 million
in our case), this turned out to be very fast.
let cacheSize = 1_000_000

var cache = [Int](repeating: 0, count: cacheSize)
cache[1] = 1

func collatzLengthCached(n: Int64) -> Int {
    if let smallN = Int(exactly: n), smallN < cacheSize {
        if cache[smallN] > 0 {
            return cache[smallN]
        }
        let len = 1 + collatzLengthCached(n: collatzFunc(n: n)!)
        cache[smallN] = len
        return len
    }
    return 1 + collatzLengthCached(n: collatzFunc(n: n)!)
}

let (maxN, maxLength) = (1...999_999)
    .map { ($0, collatzLengthCached(n: $0)) }
    .max { $0.1 < $1.1 }!

This code, compiled with Xcode with optimization ("Release" configuration)
runs in about 0.08 seconds on my 1.2 GHz Intel Core m5 MacBook.


Painting a lot of diagrams for a board game I'm creating a chess application and I would like to show plenty of big chess diagrams in scrollview. At the moment I just create ImageView for every diagram, create bitmap into it, paint the diagram on a canvas and that's it.

However, it goes crazy with memory necessary to work. On my quadHD display it uses hundreds of MB even on A4R4G4B4. As I need always to show only a chess board, pieces and arrows, it seems pretty unnecessary to store so much bitmap data as I'm only reusing the same images many times plus painting some polygons. Is there a way to make this more efficiently? Is there a way how to use ImageView without bitmap data, just painting to it when it's on the screen?

public void UpdateLecturePreviewPositionsCount(int newCount)
{
    //Function never removes extra views, but adds views if more then previously necessary
    while (lecturePreviewBoards.Count < newCount)
    {
        lecturePreviewBoards.Add(CreateBoard((xScreen - (NUM_DIAGRAMS_PER_PAGE * 2) * DIAGRAM_PADDING) / NUM_DIAGRAMS_PER_PAGE));
        lecturePreviewBoards[lecturePreviewBoards.Count - 1].imgv.SetPadding(DIAGRAM_PADDING, DIAGRAM_PADDING, DIAGRAM_PADDING, DIAGRAM_PADDING);
        layoutLecturePositionsPreview.AddView(lecturePreviewBoards[lecturePreviewBoards.Count - 1].imgv);
    }
    for (int i = 0; i < newCount; i++)
        lecturePreviewBoards[i].imgv.Visibility = ViewStates.Visible;
    for (int i = newCount; i < lecturePreviewBoards.Count; i++)
        lecturePreviewBoards[i].imgv.Visibility = ViewStates.Gone;

}

public c_image_painting CreateBoard(double dblSize = -1)
{
    if (dblSize < 0)
        dblSize = xScreen;
    int size = (int)dblSize;
    c_image_painting cbp = new c_image_painting();
    cbp.bmp = Bitmap.CreateBitmap(size, size, Bitmap.Config.Argb4444);
    cbp.cnv = new Canvas();
    cbp.imgv = new ImageView(context);
    cbp.cnv.SetBitmap(cbp.bmp);
    cbp.imgv.SetImageBitmap(cbp.bmp);
    return cbp;
}

public class c_image_painting
{
    public Canvas cnv;
    public Bitmap bmp;
    public ImageView imgv;
    private Bitmap.Config bmpFormat;
    public c_image_painting()
    {
        bmpFormat=Bitmap.Config.Argb4444;
    }
    public c_image_painting(Bitmap.Config bc)
    {
        bmpFormat = bc;
    }
}

Instead of rendering the bitmap in memory, you could define a custom view that takes a Board and renders it.

I did this for an Android app for a variant of the Go board game, and it worked pretty well. The basic idea of this AbstractBoardView is to have the board state somewhere and to connect it to a view so that it can be drawn.

The memory requirements for this class are exceptionally low, compared to a precomputed bitmap. Even more because my implementation doesn't even hold the board state, it just provides access to it via abstract methods.


Advice on taming a slow loop required for visualization of large GIS dataset I'm working towards plotting a large GIS dataset of which I've shown a sample above of about 1/6 of the data. I'm happy with how quickly the data loads in, and bokeh renders the html nearly instantaneously.  However, I've encountered a pretty hot loop in my code that is not scaling well as I increase the 1) number of rows and 2) resolution of the polygons. I'm just getting killed in the #count points loop and am wondering if there isn't a better way of doing this?

I found the suggestion for a loop off a GIS readthedoc.io and was happy with its performance for a few thousand points a couple months ago. But now the project needs to process a GeoDataFrame with >730000 rows. Is there a better method I'm suppose to be using to count the number of points in each polygon? I'm on a modern desktop to do the computation but the project has access to Azure resources so maybe that's most people professionally do this sort of computation? I'd prefer to do the computation locally but it means my desktop might have to sit at max cpu cycles overnight or longer which isn't a thrilling prospect. I'm using Python 3.8.2 & Conda 4.3.2.

from shapely.geometry import Polygon
import pysal.viz.mapclassify as mc
import geopandas as gpd

def count_points(main_df, geo_grid, levels=5):
    """
    outputs a gdf of polygons with a columns of classifiers to be used for color mapping
    """
    pts = gpd.GeoDataFrame(main_df["geometry"]).copy()

    #counts points
    pts_in_polys = []
    for i, poly in geo_grid.iterrows():
        pts_in_this_poly = []
        for j, pt in pts.iterrows():
            if poly.geometry.contains(pt.geometry):
                pts_in_this_poly.append(pt.geometry)
                pts = pts.drop([j])
        nums = len(pts_in_this_poly)
        pts_in_polys.append(nums)
    geo_grid['number of points'] = gpd.GeoSeries(pts_in_polys) #Adds number of points in each polygon

    # Adds Quantiles column
    classifier = mc.Quantiles.make(k=levels)
    geo_grid["class"] = geo_grid[["number of points"]].apply(classifier)

    # Adds Polygon grid points to new geodataframe
    geo_grid["x"] = geo_grid.apply(getPolyCoords, geom="geometry", coord_type="x", axis=1)
    geo_grid["y"] = geo_grid.apply(getPolyCoords, geom="geometry", coord_type="y", axis=1)
    polygons = geo_grid.drop("geometry", axis=1).copy()

    return polygons

The nested loop compares each poly to each point, so the complexity is (Npoly * Npts).

If the grid is regular, that is each square in a row has the same top and bottom coordinate, and each square in a column has the same left and right coordinate, then binary searches (bisect in std library) could be used to determine which grid row and column a point falls in.  This would be Npts * log Npoly.  I think this could be combined with .groupby() to eliminate any explicit loops.  I don't have time to post code now,  maybe tomorrow.

(It's tomorrow)

Better yet, use numpy.histogram2d.  On my laptop, it takes about 220ms to bin 2M points:

import numpy as np

min_lat, max_lat = 49.22, 49.30
num_lat_bins = 10

min_long, max_long = -123.23, -122.92
num_long_bins = 20

num_points = 2_000_000

# random coordinates for testing
lats  = np.random.uniform(min_lat,  max_lat,  num_points)
longs = np.random.uniform(min_long, max_long, num_points)

h, lat_edges, long_edges = np.histogram2d(lats, longs,
                                          bins=(10,20),
                                          range=[(min_lat,max_lat), (min_long, max_long)])

Where, h is the histogram, or count in each grid square and lat_edges and 'long_edges are the grid lines.  They look like:

# h  (10 rows by 20 columns)
[[ 9982. 10126. 10124. ... 10218. 10140.  9844.]
 [ 9971. 10096. 10035. ... 10057.  9844.  9923.]
 [ 9940. 10036.  9982. ...  9966. 10034.  9872.]
 ...
 [10025. 10011. 10027. ...  9870.  9942.  9985.]]

# lat_edges
[49.22 , 49.228, 49.236, 49.244, 49.252, 49.26 , 49.268, 49.276,
       49.284, 49.292, 49.3  ]

# long_edges
[-123.23  , -123.2145, -123.199 , -123.1835, -123.168 , -123.1525,
 -123.137 , -123.1215, -123.106 , -123.0905, -123.075 , -123.0595,
 -123.044 , -123.0285, -123.013 , -122.9975, -122.982 , -122.9665,
 -122.951 , -122.9355, -122.92  ]


Caching Color-Bitmaps as MemoryStreams I am in the need to cache Bitmap's in a memory-optimized way because the API I am building will need to process many colored Bitmap's in parallel and can be used in x86 or x64 compiled applications.

If the API is being used in x86 I can't just store the Bitmap's as they are but need to store them as compressed MemoryStream's otherwise the API would throw an OutOfMemoryException pretty fast.

After storing the "Bitmap's" they will be processed by multiple threads hence thread-safety is a major point.

Any feedback is welcome.

public static class ImageCache
{
    private static int currentId = 0;
    private static readonly object addImageLock = new object();
    private static readonly object releaseImageLock = new object();
    private static readonly ConcurrentDictionary<int, MemoryStream> images = new ConcurrentDictionary<int, MemoryStream>();

    /// <summary>
    /// Release an image based on its id.
    /// </summary>
    /// <param name="id"></param>
    public static void ReleaseIamge(int id)
    {
        lock (releaseImageLock)
        {
            ReleaseMemoryStream(id);
        }
    }

    private static void ReleaseMemoryStream(int id)
    {
        MemoryStream ms = null;
        if (images.TryGetValue(id, out ms) && ms != null)
        {
            images[id].Dispose();
            images[id] = null;
        }
    }

    /// <summary>
    /// Releases all Images
    /// </summary>
    public static void ReleaseAllImages()
    {
        lock (releaseImageLock)
        {
            lock (addImageLock)
            {
                foreach (var id in images.Keys)
                {
                    ReleaseMemoryStream(id);
                }
                images.Clear();
            }
        }
    }

    /// <summary>
    /// Returns a Bitmap from the cache which is identified by an id
    /// </summary>
    /// <param name="id"></param>
    /// <returns></returns>
    public static Bitmap GetBitmap(int id)
    {
        lock (releaseImageLock)
        {
            MemoryStream ms = null;
            if (images.TryGetValue(id, out ms))
            {
                if (ms != null)
                {
                    return (Bitmap)Image.FromStream(ms);
                }
            }
        }
        return null;
    }

    /// <summary>
    /// Adds an Bitmap to the cache
    /// </summary>
    /// <param name="bitmap"></param>
    /// <returns>0 if the Bitmap is null, otherwise a uique id</returns>
    public static int Add(Bitmap bitmap)
    {

        if (bitmap == null)
        {
            return 0;
        }

        var ms = new MemoryStream();
        bitmap.Save(ms, ImageFormat.Tiff);
        var id = 0;
        lock (addImageLock)
        {
            // If the dictionary is empty we can reset the currentId
            if (images.Count == 0)
            {
                currentId = 0;
                id = Interlocked.Increment(ref currentId);
                images.TryAdd(id, ms);
                return id;
            }

            // We don't know how long an application using this is running and how many
            // images having been stored but we don't want to reach int.MaxValue here
            // hence we recycle the Value of a KeyValuePair of the dictionary if the Value
            // will be null.
            id = images.Where(item => item.Value == null).FirstOrDefault().Key;
            if (id == 0)
            {
                id = Interlocked.Increment(ref currentId);
            }

            images[id] = ms;

        }
        return id;
    }
}

Clarifying comments:

  Why don't you use a Guid as id and key in the dictionary?

Well the problem with this is that I need to "mimic" an API we use for our main application in such a way that I can interchange this API and the other API. The other api is a comercial imaging sdk whichs licence doesn't permits the use of it for a sdk/api.

First I'm not a fan of recycling IDs. Too much confusion can happen.  For example Thread 1 adds a Dog Image and gets ID 1.   Thread 2 calls ReleaseAllImages and then adds a Cat image and gets ID 1.  Now Thread 1 think it has a Dog image but instead returns back a Cat image.  There are times we need to recycle ID but only you know the business requirements if it's truly needed or not.

Second It's thread safe but you are not getting the benefit of ConcurrentDictionary this way. Everything is locked.  If two threads are trying to add one will be blocked until the other is free.  It doesn't have to be this way.

I'm going to go down the path that you need to recycle IDs

Instead of leaving the record in the dictionary you can remove it and have a queue of ID to recycle.  Then on the removing methods check if we removed all the records from the Dictionary and if so then enter the lock to see if we can reset the counter and queue. Going to use ReaderWriterLockSlim to allow multiple adds and only block when we are removing.

public static class ImageCache
{
    private static int currentId = 0;

    private static readonly ConcurrentDictionary<int, MemoryStream> images =
        new ConcurrentDictionary<int, MemoryStream>();

    // stores removed ID to reuse
    private static ConcurrentQueue<int> recycle = new ConcurrentQueue<int>();
    private static readonly ReaderWriterLockSlim recycleLocker = new ReaderWriterLockSlim();

    /// <summary>
    /// Release an image based on its id.
    /// </summary>
    /// <param name="id"></param>
    public static void ReleaseIamge(int id)
    {
        ReleaseMemoryStream(id);
        TryReset();
    }

    /// <summary>
    /// Releases all Images
    /// </summary>
    public static void ReleaseAllImages()
    {
        foreach (var id in images.Keys)
        {
            ReleaseMemoryStream(id);
        }

        TryReset();
    }

    private static void ReleaseMemoryStream(int id)
    {
        MemoryStream ms = null;
        if (images.TryRemove(id, out ms))
        {
            recycle.Enqueue(id);
            ms.Dispose();
        }
    }

    private static void TryReset()
    {
        if (!images.IsEmpty)
        {
            return;
        }

        //need to lock here
        if (recycleLocker.TryEnterWriteLock(TimeSpan.FromMilliseconds(100)))
        {
            try
            {
                // make sure another thread didn't sneak in and add another image
                if (images.IsEmpty)
                {
                    currentId = 0;
                    Interlocked.Exchange(ref recycle, new ConcurrentQueue<int>());
                }
            }
            finally
            {
                recycleLocker.ExitWriteLock();
            }
        }
    }

GetBitmap method doesn't need to check if the image is null now we can use the TryGetValue and not need to lock at all

/// <summary>
/// Returns a Bitmap from the cache which is identified by an id
/// </summary>
/// <param name="id"></param>
/// <returns></returns>
public static Bitmap GetBitmap(int id)
{
    MemoryStream ms = null;
    if (images.TryGetValue(id, out ms))
    {
        return (Bitmap) Image.FromStream(ms);
    }
    return null;
}

Add method will need to let the lock know we are reading from the recycle queue

/// <summary>
/// Adds an Bitmap to the cache
/// </summary>
/// <param name="bitmap"></param>
/// <returns>0 if the Bitmap is null, otherwise a uique id</returns>
public static int Add(Bitmap bitmap)
{
    if (bitmap == null)
    {
        return 0;
    }

    recycleLocker.EnterReadLock();

    try
    {
        var ms = new MemoryStream();
        bitmap.Save(ms, ImageFormat.Tiff);

        // Recycle Id or make new one
        int id;
        if (!recycle.TryDequeue(out id))
        {
            id = Interlocked.Increment(ref currentId);
        }

        // this should never be possible to fail
        images.TryAdd(id, ms);

        return id;
    }
    finally
    {
        recycleLocker.ExitReadLock();
    }
}

Using the ReaderLockerSlim will allow multiple reads but only one write.  Now multiple threads could Add images and Get images without blocking each other and the code only blocks when it's resetting the counters.


Search and replace on command line Is there a tighter (less characters) way to use perl on the command line to search and replace text from STDIN than I've got here? The code below works.

echo hi | perl -e '$a = <STDIN>; $a =~ s/i/o/g; print $a;'

You can use -p option (see perl --help):

  assume loop like -n but print line also, like sed

So the script becomes:

echo hi | perl -pe 's/i/o/g'

which is really compiled to:

$ perl -MO=Deparse -pe 's/i/o/g'
LINE: while (defined($_ = <ARGV>)) {
    s/i/o/g;
}
continue {
    die "-p destination: $!\n" unless print $_;
}
-e syntax OK


Sleep and prolong sleep What do you think about such an object function?

const stc = {
  delayTimer: {},
  sleep: (m, name) => new Promise(r => stc.delayTimer[name] = setTimeout(r, m)),
  sleepProlong: async (ms, name)=> {
    if (stc.delayTimer[name])
      clearTimeout(stc.delayTimer[name]);
    delete stc.delayTimer[name];
    return await stc.sleep(ms, name);
  }
}

It is used to make a delay, but additionally when you call it again before the set time expires, it clears the counter and counts from the beginning, does not release the function any further.

async function s (){
  console.log("wy");
  await stc.sleepProlong(5000, "mek");
  console.log("my");
}

For example, when in the console you will start s() before 5 seconds elapses from the previous firing, "we" will not appear. when you stop, it will complete the last counting and "we" will be displayed.

What do you think? Can you do it better?

What is it for?
Without knowing what you would use this for I can only go by your question.
The behaviour of stc is not what the  question's title suggests as it is very easy to make it fail or behave in a non intuitive manner.
Forever pending
Consider the following use example
stc.sleep(1000, "test").then(()=>log("Test timeout");  // this promise is never resolved
setTimeout(()=>{
        stc.sleepProlong(2000, "test").this(()=>log("Test prolonged timeout")
    },200);

The first promise is left pending and will never be resolved.
Some other potential problems

Each time sleepProlong is called you leave another promise unresolved.
When sleepProlong is called the name implies that it "prolongs sleep", but if the sleep has already timeouted out it creates a new sleep???
If sleep is called with the same name as an existing sleep, the previous sleep can no longer be prolonged,
The stc interface exposes delayTimer making the state of stc untrustable.

Expectations?
From the question's title I would expect

that there is only one promise for a named sleep.
that the sleep and prolonged sleep can be canceled
that the sleep can be prolonged indefinitely
that attempting to prolong a sleep that has timeout does nothing.
that calling sleep with the name of an unresolved existing sleep does nothing

Some general style and coding points

Function argument names are inconsistent you call the timeout delay m in one function and ms in the other.
The line delete stc.delayTimer[name]; is not needed as you overwrite the value by calling sleep on the next line.
not using curlies {} to delimited statement blocks is a bad habit, Always delimit statement blocks with {...}.You had if (stc.delayTimer[name])  clearTimeout(stc.delayTimer[name]); is better as if (stc.delayTimer[name])  { clearTimeout(stc.delayTimer[name]); }
There is no need to check if the named timeout event handle exists. clearTimeout will ignore undefined and already timed out handles. Thus if (stc.delayTimer[name])  { clearTimeout(stc.delayTimer[name]); } can be clearTimeout(stc.delayTimer[name]); and not change the behaviour.
This may just be my personal preference but it feels wrong having the time m, or ms as the first argument. Putting the name first and then the delay seems more natural (and thus easier to remember)
You don't need to await the promise you return in the async function, Async functions do this automatically .
Ensure that you protect important state variables. If entries in the  object delayTimer are mutated then you lose the ability to maintain stc's correct behaviour. You can protect it via closure.

Cleanup and keeping original behaviour
without changing the behaviour of you code I have made changes as outlined in the above points, and modified some names.
const stc = (() => {
    const handles = {};
    return {
        sleep(name, time) { return new Promise(r => handles[name] = setTimeout(r, time)) },
        async prolong(name, time) {
            clearTimeout(handles[name]);
            return stc.sleep(name, time);
        }
    };
})();


C# small caching API public interface ICacheable<TK,TV>
{
   TV Get(TK key);
   void Add(TK key, TV val);
}

public abstract class BaseCache<TK, TV>
{
    protected static Dictionary<Guid, Dictionary<TK, TV>> data = new Dictionary<Guid, Dictionary<TK, TV>>();
    private Guid StorageNameSpage;

    protected BaseCache(Guid storageNameSpage)
    {
        StorageNameSpage = storageNameSpage;
    }

    protected BaseCache()
    {
        StorageNameSpage = Guid.NewGuid();
    }

    public TV Get(TK key)
    {
        return data[StorageNameSpage][key];
    }

    public void Add(TK key, TV val)
    {
        data.Add(....);
     }
}

2 different ways to implement it:

"mulityTon" or what ever you want to call it.

public class KeyValCacheStorage<TK, TV> : BaseCache<TK, TV>, ICacheable<TK, TV>
{

}

SingleTome

public class KeyValCacheStorageSingleTon<TK, TV> : BaseCache<TK, TV>, ICacheable<TK, TV>
{
    private static Guid storageNameSpage = Guid.NewGuid();
    public KeyValCacheStorageSingleTon():base(storageNameSpage)
    {

    }
}

usage:

KeyValCacheStorageSingleTon<string, string> storageSingleTon1 = new KeyValCacheStorageSingleTon<string, string>();
storageSingleTon1.Add("storageSingleTon1", "KeyValCacheStorageSingleTon");
storageSingleTon1.Add("bla", "yada");

KeyValCacheStorageSingleTon<string, string> storageSingleTon2 = new KeyValCacheStorageSingleTon<string, string>();
storageSingleTon2.Add("storageSingleTon2", "KeyValCacheStorageSingleTon2");

So I've made a few modifications; here are the explanations:

Used interfaces a bit more liberally (IDictionary)
Made BaseClass implement ICacheable so the subclasses don't explicitly have to
Made fields readonly as appropriate to declare intent
Made field data private and exposed as protected by way of a property
Chained the BaseCache constructors
Created the storage dictionary in the constructor (could do this in Add if you were looking for lazy creation)
sealed subclasses (if they're intended to be non-inheritable, of course)

The code:

public interface ICacheable<TK, TV>
{
    TV Get(TK key);

    void Add(TK key, TV val);
}

public abstract class BaseCache<TK, TV> : ICacheable<TK, TV>
{
    private static readonly IDictionary<Guid, IDictionary<TK, TV>> data = new Dictionary<Guid, IDictionary<TK, TV>>();

    private readonly Guid storageNameSpace;

    protected BaseCache(Guid storageNameSpace)
    {
        this.storageNameSpace = storageNameSpace;
        data[this.storageNameSpace] = new Dictionary<TK, TV>();
    }

    protected BaseCache() : this (Guid.NewGuid())
    {
    }

    protected static IDictionary<Guid, IDictionary<TK, TV>> Data
    {
        get
        {
            return data;
        }
    }

    public TV Get(TK key)
    {
        return data[this.storageNameSpace][key];
    }

    public void Add(TK key, TV val)
    {
        data[this.storageNameSpace].Add(key, val);
    }
}

public sealed class KeyValCacheStorage<TK, TV> : BaseCache<TK, TV>
{
}

public sealed class KeyValCacheStorageSingleton<TK, TV> : BaseCache<TK, TV>
{
    private static readonly Guid storageNameSpace = Guid.NewGuid();

    public KeyValCacheStorageSingleton() : base(storageNameSpace)
    {
    }
}


python hangman (another one) I'm pretty new to python and have created a simple hangman. Since doing so I realise this appears to be a fairy common theme.
It uses /usr/share/dict/words on the local system, resulting in some tricky words to guess. I guess I should look at maybe curl'ing a URL to get random words or an API. I've also not defined a main(), not sure if that's bad practice. Feedback appreciated.

#!/usr/local/bin/python3

import os
import random
import subprocess

def draw_man_and_show_word():
   global word
   showword=''.join(word)
   os.system('clear')
   for y in range(0,7):
      for x in range(0,7):
         print (chr(array[y][x]),end='')
      print()
   print ()
   print (showword)
   print ()

def add_limb_to_man():
   global size
   y=man[size][0]
   x=man[size][1]
   c=man[size][2]
   array[x][y]=c
   size=size+1

def find_random_word():
   global theword
   lines=int(subprocess.getoutput("wc -l /usr/share/dict/words | awk \'{print $1}\'"))
   line=random.randint(1,lines)
   theword=subprocess.getoutput("head -"+str(line)+" /usr/share/dict/words |tail -1")
   theword=str.lower(theword)

# 2D array of character (ASCII) values as a matrix for the hangman pic
array=[[124,45,45,45,45,32,32,32],[124,32,32,32,124,32,32,32],[124,32,32,32,32,32,32,32],[124,32,32,32,32,32,32,32],[124,32,32,32,32,32,32,32],[124,32,32,32,32,32,32,32],[124,32,32,32,32,32,32,32]]

# 2D array with the (single) character position to change (x,y,newvalue) for each additional limb
man=[[4,2,79],[4,3,43],[3,3,47],[5,3,92],[4,4,124],[3,5,47],[5,5,92]]

size=tries=0
limit=6
letters_tried=""

find_random_word()

# Array to represent word shown on screen (using array as string immutable)
word=['-' for x in range(0,len(theword))]

while ((tries <= limit)):
   draw_man_and_show_word()

   letter=""
   while (len(letter) != 1 or not letter.islower() or letters_tried.find(letter) >= 0):
      letter=input("Enter your choice of (single lowercase) letter:")

   letters_tried=letters_tried+letter

   pos=theword.find(letter)
   if (pos >= 0):
      tmpword=theword
      while (pos >= 0):
         word[pos]=letter
         tmpword=tmpword.replace(letter,'#',1)
         pos=tmpword.find(letter)

   else:
      add_limb_to_man()
      tries=tries+1

   if (''.join(word) == theword):
      draw_man_and_show_word()
      print()
      print("you got it!")
      exit()

draw_man_and_show_word()

print ("you lost. It was "+theword)

Avoid working in the global namespace

This makes maintenance of code a pain. Instead create a main or hangman function
Don't use global instead make these variables parameters of you function

def draw_man_and_show_word():
   global word

Could be

def draw_man_and_show_word(word):

Don't make lines to long, they become really hard to read

array=[[124,45,45,45,45,32,32,32],[124,32,32,32,124,32,32,32],[124,32,32,32,32,32,32,32],[124,32,32,32,32,32,32,32],[124,32,32,32,32,32,32,32],[124,32,32,32,32,32,32,32],[124,32,32,32,32,32,32,32]]

See how you need to scroll all the way to the right, this would be much more easy on the eyes

HANGMAN =  [
               ['|', '-', '-', '-', '-', ' ', ' ', ' '],
               ['|', ' ', ' ', ' ', '|', ' ', ' ', ' '],
               ['|', ' ', ' ', ' ', ' ', ' ', ' ', ' '],
               ['|', ' ', ' ', ' ', ' ', ' ', ' ', ' '],
               ['|', ' ', ' ', ' ', ' ', ' ', ' ', ' '],
               ['|', ' ', ' ', ' ', ' ', ' ', ' ', ' '],
               ['|', ' ', ' ', ' ', ' ', ' ', ' ', ' ']
           ]

I also changed it to their character form which makes it even more easy to read

And made the variable name ALL_CAPS since this is a constant
Use unpacking // Optional namedtuple

man=[[4,2,79],[4,3,43],[3,3,47],[5,3,92],[4,4,124],[3,5,47],[5,5,92]]
y=man[size][0]
x=man[size][1]
c=man[size][2]
array[x][y]=c
size=size+1

First I cleaned it up a bit

HANGMAN_STAGES = [
                     [4, 2, 'O'],
                     [4, 3, '+'],
                     [3, 3, '/'],
                     [5, 3, '\\'],
                     [4, 4, '|'],
                     [3, 5, '/'],
                     [5, 5, '\\']
                 ]

And we can unpack the values from the list of lists with this

x, y, value = HANGMAN_STAGES[size]

Alternatively you can use the namedtuple module to store information more visually

The it would become

from collections import namedtuple

Stage = namedtuple('Stage', 'x, y, value')
HANGMAN_STAGES = [
                     Stage(4, 2, 'O'),
                     Stage(4, 3, '+'),
                     Stage(3, 3, '/'),
                     Stage(5, 3, '\\'),
                     Stage(4, 4, '|'),
                     Stage(3, 5, '/'),
                     Stage(5, 5, '\\')
                 ]

And you can call them like this

stage = HANGMAN_STAGES[size]
HANGMAN[stage.y][stage.x] = stage.value

Make the guessed_letters a set()

For fast lookup O(0)
join() instead of manually appending chars

for y in range(0,7):
    for x in range(0,7):
        print (chr(array[y][x]),end='')
    print()

Could be rewritten as print('\n'.join(''.join(row) for row in draw_list))

If we have changed the HANGMAN to contain chr instead of the ordinal values
Instead of the find and replace methods you could have used enumerate

pos=theword.find(letter)
if (pos >= 0):
    tmpword=theword
    while (pos >= 0):
        word[pos]=letter
        tmpword=tmpword.replace(letter,'#',1)
        pos=tmpword.find(letter)

Can be rewritten in the form of

for idx, char in enumerate(theword):
    if char == letter:
        guessed_word[idx] = letter

But strings can't be assigned... so you should set the data type of guessed_word to a list
Lastly top it off with a if __name__ == '__main__'

Putting it all together

import random

HANGMAN =  [
                ['|', '-', '-', '-', '-', ' ', ' ', ' '],
                ['|', ' ', ' ', ' ', '|', ' ', ' ', ' '],
                ['|', ' ', ' ', ' ', ' ', ' ', ' ', ' '],
                ['|', ' ', ' ', ' ', ' ', ' ', ' ', ' '],
                ['|', ' ', ' ', ' ', ' ', ' ', ' ', ' '],
                ['|', ' ', ' ', ' ', ' ', ' ', ' ', ' '],
                ['|', ' ', ' ', ' ', ' ', ' ', ' ', ' ']
           ]

HANGMAN_STAGES = [
                    [4, 2, 'O'],
                    [4, 3, '+'],
                    [3, 3, '/'],
                    [5, 3, '\\'],
                    [4, 4, '|'],
                    [3, 5, '/'],
                    [5, 5, '\\']
                 ]
SPACE = '_'

def print_man_and_word(draw_list, guessed_word):
    print('\n'.join(''.join(row) for row in draw_list))
    print()
    print(''.join(guessed_word))

def get_random_word():
    # Your logic here (I don't have linux atm ;)
    word_list = ['cheese', 'pepper', 'sausage']
    return random.choice(word_list)

def get_letter(guessed_letters):
    letter = ''
    while len(letter) != 1 or not letter.islower() or letter in guessed_letters:
        letter = input("Enter your choice of (single lowercase) letter:")
    return letter

def hangman(word=None, draw_list=HANGMAN):
    if word is None:
        word = get_random_word()

    guessed_word = [SPACE] * len(word)
    guessed_letters = set()
    tries = 0

    while True:
        print_man_and_word(draw_list, guessed_word)
        letter = get_letter(guessed_letters)
        guessed_letters.add(letter)

        if letter in word:
            for idx, char in enumerate(word):
                if char == letter:
                    guessed_word[idx] = letter
        else:
            x, y, value = HANGMAN_STAGES[tries]
            draw_list[y][x] = value
            tries += 1

        if all(char != SPACE for char in guessed_word):
            print_man_and_word(draw_list, guessed_word)
            print('\nYou got it!')
            exit()

        elif tries == len(HANGMAN_STAGES):
            print_man_and_word(draw_list, guessed_word)
            print('You lost! it is {}'.format(word))
            exit()

if __name__ == '__main__':
    hangman()


jQuery function to display an alert when submitting blank fields I am new to jquery and implemented following function in a js file in case of error-

function before_submit_check_if_has_blank_field() {
    $("[type=submit]").click(function(e) {
        var of_key_field = $('.key_field')
        var of_val_field = $('.val_field')
        var should_run = 1

        if (of_key_field.length === 1) {
            $('.key_field:not(:first)').filter(function() {
                if (this.value === "") {
                    alert('Please Fill In Or Remove The Blank Fields First')
                    e.preventDefault();
                    should_run = 0
                }
            });
        } else {
            $('.key_field').filter(function() {
                if (this.value === "") {
                    alert('Please Fill In Or Remove The Blank Fields First')
                    e.preventDefault();
                    should_run = 0
                }
            });
        }

        if (should_run != 0) {
            if (of_val_field.length === 1) {
                $('.val_field:not(:first)').filter(function() {
                    if (this.value === "") {
                        alert('Please Fill In Or Remove The Blank Fields First')
                        e.preventDefault();
                        should_run = 0
                    }
                });
            } else {
                $('.val_field').filter(function() {
                    if (this.value === "") {
                        alert('Please Fill In Or Remove The Blank Fields First')
                        e.preventDefault();
                        should_run = 0
                    }
                });
            }
        }

        update_config_field_from_key_value_field()
    });
}

The above code snippet is a part of my jquery where I am displaying a layout to the user with some fields and once those fields are empty then I am showing alert message while saving the form.

In above function I am repeating following lines of alert message which must be replaced by standard one-

if (this.value === "") {
    alert('Please Fill In Or Remove The Blank Fields First')
    e.preventDefault();
    should_run = 0
}

Can anyone please review my code and refactor it?

Your code can be refactor in multiple ways. To remove code repetition, create a new function for repeated code and use it as a callback of each filter.

function someFunc(e) {
  if (this.value === "") {
    alert('Please Fill In Or Remove The Blank Fields First')
    e.preventDefault();
    should_run = 0
  }
}

Use above function as

$('.key_field:not(:first)').filter(someFunc);

This will automatically remove redundant code as well as reduce number lines.

Suggestions:

Instead of playing around DOM and get value for each field separately, try to use serializeArray method of JQuery. See example

Please make habit to use ; to terminate line.

Hope this is helpful.


Fetching busy students and their latest product I use SQL Server 2014 and I have three tables:

Student (ID, Name, Age)
Product  (ID, Name)
StudentProduct (StudentID, ProductID, Date)

TABLE Student(ID, Name, Age) >>
ID  Name    Age
1   Adam    20
2   Bob     17
3   Ben     18
4   Joseph  18
5   Jon     18

TABLE Product (ID, Name) >>
ID  Name
1   SQLServer
2   Visual Studio
3   Idea
4   Eclipse

TABLE StudentProduct (StudentID, ProductID, Date) >>
StudentID   ProductID     Date
1           1             25.05.2016 0:00:00
1           4             26.06.2016 0:00:00
1           3             27.06.2016 0:00:00
1           2             28.06.2016 0:00:00
2           1             29.07.2016 0:00:00

I've written a query to get all students who meet these criteria

Are older than 19
Participate in developing more than 3 products

Both criteria should be checked in a single query.

The desired result should then contain the

Age of the student
Name of student
Name of the last developed product (using StudentProduct.Date)

Result should be:

Age   StudentName      ProductName
20    Adam             Visual Studio

My query is:

select e.age, e.name ,
(select top 1 p.Name from Product p
inner join StudentProduct peOut on p.ID = peOut.ProductID
where peOut.StudentID = e.ID
order by peOut.Date desc)
from Student e where e.age > 19
and exists (select pe.StudentID, count(1) from StudentProduct pe
where pe.StudentID = e.ID group by pe.StudentID
having count(1) > 3)

How can I improve the efficiency of my query?

Without additional info about indexes and row counts it's hard to tell, but the most elegant solution is probably using Analytical Functions (using employees instead of students):

with cte as
 (
    select s.age, s.name as EmployeeName, p.Name as ProductName,
       -- row with the newest date
       row_number() over (partition by s.ID order by sp.Date desc) as rn,
       -- number of Products per employee
       count(*) over (partition by s.ID) as cnt
    from Student as s
    join StudentProduct as sp
      on sp.EmployeeID = e.ID
    join Product as p
      on p.ID = sp.ProductID
    where s.age > 19
 )
select age, EmployeeName, ProductName
from cte
where cnt > 3  -- more than three products
  and rn = 1   -- the latest product


Brick Wall Leetcode challenge I solved this problem on Leetcode

  There is a brick wall in front of you. The wall is rectangular and has
  several rows of bricks. The bricks have the same height but different
  width. You want to draw a vertical line from the top to the bottom and
  cross the least bricks.

  The brick wall is represented by a list of rows. Each row is a list of
  integers representing the width of each brick in this row from left to
  right.

  If your line go through the edge of a brick, then the brick is not
  considered as crossed. You need to find out how to draw the line to
  cross the least bricks and return the number of crossed bricks.

  You cannot draw a line just along one of the two vertical edges of the
  wall, in which case the line will obviously cross no bricks.

Input:
[[1,2,2,1],
 [3,1,2],
 [1,3,2],
 [2,4],
 [3,1,2],
 [1,3,1,1]]
Output: 2

  Explanation:

The time complexity is O(height of the wall * total bricks in the wall) assuming Add, Remove, ContainsKey in Dictionary is O(1) and the space complexity is O(height of the wall).

I'm not sure if there is a better algorithm or more suited data structure that could improve the performance.

public int LeastBricksDictionary(IList<IList<int>> wall)
{
    var totalRows = wall.Count;
    var values = new SortedDictionary<int, List<Tuple<int, int>>>();
    int leastBrick = int.MaxValue, bricksNotCrossing = 0;
    for (int i = 0; i < wall.Count; i++)
    {
        var newTuple = new Tuple<int, int>(i, 0);
        if (values.ContainsKey(wall[i][0]))
        {
            values[wall[i][0]].Add(newTuple);
        }
        else
        {
            values.Add(wall[i][0], new List<Tuple<int, int>>() { newTuple });
        }
    }
    while (values.Count > 0)
    {
        int minSum = values.Keys.First();
        var minList = values[minSum];
        values.Remove(minSum);
        bricksNotCrossing = 0;
        foreach (var temp in minList)
        {
            int row = temp.Item1, col = temp.Item2;

            if (wall[row].Count > 1 && col + 1 < wall[row].Count)
            {
                ++bricksNotCrossing;
            }
            if (col + 1 < wall[row].Count)
            {
                int newSum = minSum + wall[row][col + 1];
                var newTuple = new Tuple<int, int>(row, col + 1);
                if (values.ContainsKey(newSum))
                {
                    values[newSum].Add(newTuple);
                }
                else
                {
                    values.Add(newSum, new List<Tuple<int, int>>() { newTuple });
                }
            }
        }
        leastBrick = Math.Min(leastBrick, totalRows - bricksNotCrossing);
    }
    return leastBrick;
}

You could look at it in a different way, transform the wall of bricks to a wall of edges, in your example it would be

1, 3, 5
3, 4
1, 4
2
3, 4
1, 4, 5

The first, the third and the last row have an edge at 1, thus you can draw a line that crosses three bricks less than the height of the wall.
You need to find the edge that appears the most.

In this case it would be four it appears in rows 2,3,5,6.

After transforming the wall to a wall of edges, a SelectMany into a GroupBy and Max will do the trick.


Incremental Sieve of Eratosthenes Generator So I was fiddling around with the Euler challenges. One of the things they mentioned in their discussions of the solutions is the Sieve of Eratosthenes and that you can only use it when you know an upper bound of the primes you want to generate.

I wondered whether the algorithm can be adapted to work without that upper bound. This works be replacing the bool[] for a Dictionary<int, int>. Where the original algorithm would fill all multiples immediately after finding a prime, I will fill them one at a time, keeping a dictionary to keep track of which prime has filled that value in the sieve. This way the sieve can be filled incrementally as enumeration continues.

In my version of C#, this method runs out of steam before we reach int.MaxValue, due to the increasing size of the dictionary. If I am correct, this algorithm runs in \$O(n)\$ space, and \$O(n)\$ time.

/// <summary>
/// Produce an "infinite" generator for primes.
/// </summary>
/// <remarks>Runs out of memory at prime 1_003_875_373.</remarks>
public static IEnumerable<int> Primes() {
  var sieve = new Dictionary<int, int>();
  var primeCandidate = 2;
  while (true) {
    // If sieve contains primeCandidate, it's not a prime. We retrieve its factor from the dictionary.
    if (sieve.TryGetValue(primeCandidate, out var smallestFactor)) {
      // Not needed anymore
      sieve.Remove(primeCandidate);

      // Look for the next multiple that isn't already in the sieve.
      // Unchecked because if it overflows, we don't really care, since primeCandidate would have overflowed earlier.
      unchecked {
        var nextMultiple = primeCandidate + smallestFactor;
        while (sieve.ContainsKey(nextMultiple)) {
          nextMultiple += smallestFactor;
        }
        sieve[nextMultiple] = smallestFactor;
      }
    }
    else {
      // In this case, we have found a prime. Add its square to the sieve:
      yield return primeCandidate;
      // Unchecked because if it overflows, we don't really care, since primeCandidate would have overflowed earlier.
      unchecked { sieve[primeCandidate * primeCandidate] = primeCandidate; }
    }
    // This cannot overflow!
    checked { primeCandidate++; }
  }
}

[TestMethod]
public void TestFirst20Primes() {
  var actual = Primes().Take(20).ToList();
  var expected = new[] { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71 };
  CollectionAssert.AreEqual(expected, actual);
}

My main concern is efficiency, both in memory and time.

// Unchecked because if it overflows, we don't really care, since primeCandidate would have overflowed earlier.
      unchecked { sieve[primeCandidate * primeCandidate] = primeCandidate; }

is wrong. For example, every int in the range 65537 to 80264 inclusive overflows to a value which is greater than itself.

The easy fix is to add an overflow check. That would also fix the memory problem, because sieve would have no more entries than there are primes below 65536.


Titleize words in a sentence but with some conditions Below is the code I have written to capitalize all the words of a sentence except if

The words belong to the littleWords list.
The word would be capitalized if it's the first word of the sentence even if it is in the littleWords list.

def titleize(sentence)
    littleWords = ["end", "over", "and", "the"]
    words = sentence.split(/^(\w+)\b/)
    sentence = if words[2]
        words[2].split(" ").map do |word|
            littleWords.include?(word) ? (" " + word) : (" " + word.titleize)
        end
    end
    words[1].titleize + (sentence||[]).join("")
end

SPEC

describe "titleize" do
it "capitalizes a word" do
  titleize("jaws").should == "Jaws"
end

it "capitalizes every word (aka title case)" do
  titleize("david copperfield").should == "David Copperfield"
end

it "doesn't capitalize 'little words' in a title" do
  titleize("war and peace").should == "War and Peace"
end

it "does capitalize 'little words' at the start of a title" do
  titleize("the bridge over the river kwai").should == "The Bridge over the River Kwai"
end
end

I am new to ruby/script and am coming from Java. The code above doesnt looks as nice and clean as I think could be done with ruby.

Rather than split and join the string, it'd be simpler to

Always capitalize the sentence itself, so it always starts with an uppercase letter
Pass a block to gsub, letting it do the filtering.

Also: a minor thing but unlike Java, Ruby favors snake_case rather than camelCase for names. So conventionally, it'd be little_words, not littleWords.

Here's a simplistic implementation:

def titleize(sentence)
  little_words = %w(end over and the)
  sentence.capitalize.gsub(/(\w+)/) do |word|
    little_words.include?(word) ? word : word.capitalize
  end
end

Of course, capitalize doesn't just make the leading letter uppercase, it also foribly downcases the rest of the string. So writing, say, "DNA and RNA" will incorrectly give you "Dna and Rna". It isn't fond of unicode characters either, so caveat emptor.

Basically, that "titleizing" a string is bit of hornet's nest. There are multiple schools of thought on how it should be done, some depending on context. And right when you think you have it, someone writes a URL or a name like "iPhone" in a sentence, and it comes out wrong anyway.

A slightly more clever - but still brittle! - solution might be:

def titleize(sentence)
  little_words = %w(end over and the)
  sentence.gsub(/\b(\p{Ll}+)\b/) do |word|
    # The following breaks codereview's syntax highlighting, but it's valid Ruby code.
    # I used a "full" if-else rather than a ternary just to keep the lines shorter.
    if $`.empty? || !little_words.include?(word)
      word.capitalize
    else
      word
    end
  end
end

The regex only matches words that are all-lowercase meaning "DNA" and "iPhone" will pass though undisturbed. But we can't capitalize the string in its entirety because it'd just make everything except the first word an all-lowercase word. So instead, we have the $` "magic" variable, which contains the string before the current match. If it's empty, we're at the start, and should capitalize the word even if it's on the small_words list.

But again, this isn't a great solution at all. It's just here to illustrate some regex voodoo.

And in any event this isn't a new problem. Here's a gem that sounds like it's a port of this Perl script, which, if nothing else, comes with an explanation of its working.

Edit: As tokland points out in the comments, using a Set instead of an array for litte_words would make for faster lookups; no searching necessary. It'd also be nicer to define the list of little words as a constant, rather than declare it as a local variable when the method's run:

LITTLE_WORDS = %w{ end over and the }
  #=> ["end", "over", "and", "the"]


Using methods and constructors to construct a basic calculator I am trying to come up with a simple basic calculator but am supposed to work with the following constructors and methods:

simpleCalc();
simpleCalc(double op1, double op2);
double add();
double add(double op1, double op2);
double mult();
double mult(double op1, double op2);
double exp();
double exp(double op1, double op2);
void show();
void show(int dp);

I have written down some working code and I just want to know if am doing the right thing.

MyClass.java

package basicjavacalculator;

public class MyClass {
public static void main(String[] args) {
// TODO code application logic here
simpleCalc sc = new simpleCalc();
sc.show();

 }

}

simpleCalc.java

package basicjavacalculator;

import java.util.Scanner;

public class simpleCalc {

double add(){
return 0;
}

double mult(){
return 0;
}

double exp(){
return 0;
}

simpleCalc(){

}

void show(){

Scanner userInput = new Scanner(System.in);

System.out.println("=================Welcome to SimpleCalcDemo=================");
System.out.println("\n");

System.out.println("Enter first number: ");
double op1 = userInput.nextInt();

System.out.println("Enter second number: ");
double op2 = userInput.nextInt();

System.out.print("Enter operation to perform (+,x,^):");
String operation= userInput.next();

if(operation.equals("+")){
    System.out.println(add(op1, op2));
}

else if (operation.equals("x")){
    System.out.println(mult(op1, op2));
}

else if (operation.equals("^")){
    System.out.println(exp(op1, op2));
}
else{
System.out.println("The operation is not valid.");

}

}

double add(double op1, double op2){
return op1 + op2;
}

double mult(double op1, double op2){
return op1 * op2;
}

double exp(double op1, double op2){
double result = 1;
while (op2 > 0){
    result = result * op1;
    op2--;
}

return result;
}

}

This can be simplified:

double exp(double op1, double op2){
double result = 1;
while (op2 > 0){
    result = result * op1;
    op2--;
}

return result;
}

You should be using the Math.pow() method:

double exp(double op1, double op2){
    return Math.pow(op1, op2);
}

Also, you should use proper indentation to help you read and understand your code better, which will help prevent bugs.

This doesn't do anything:

simpleCalc(){

}

It is best to remove code like this to make your project easier to understand and maintain.


Injecting a set of files in a Thymeleaf template while keeping the amount of tags at a minimum I use a Thymeleaf template to inject a set of files (which contain precalculated HTML) into one big HTML. The files with their metadata are stored in a map called files, the files content is stored in another map called content. Both maps share the same key which is basically an id of the files.

The relevant section of the template has these lines:

        [(${content[ f.key ]})]

The result after this template was processed is:

Title of document with ID 1

    Content of file with ID 1

Title of document with ID 2

    Content of file with ID 2

This works fine but in order to place the th:each I had to introduce a superfluous div. Can I get rid of the div in the template and have a result like this:

Title of document with ID 1

Content of file with ID 1

Title of document with ID 2

Content of file with ID 2

Thymeleaf has a mechanism for removing template fragments. You can use the th:remove="tag" attribute to remove the containing tag but not its children:

<div th:each="f : ${files}" th:remove="tag">
    <h1 th:text="${f.value.pageTitle}"></h1>
    [(${content[ f.key ]})]
</div>

The resulting output will not contain the div but the h1 element and the text node.


Simple Python 3 TicTacToe Game Relatively new here so please let me know if I'm doing something wrong.

I'm mostly wondering if there's any additional way I can make this code more efficient. Specifically the moveset and win condition part of the code feels unnecessarily long or overcomplicated. Still a beginner in python, so any feedback regarding syntax is also appreciated! Thank you!

#Contains all basic variables for ease of coding
class Player():

    symbols = ['O','X']

    def __init__(self, number):
        self.wins = 0
        self.number = number
        self.symbol = self.symbols[number]

#2D list to represent the 3x3 board
def createBoard():
    a = ['', '', '']
    b = ['', '', '']
    c = ['', '', '']
    return [a, b, c]

board = createBoard()

#Makes the board look nicer for user; numbers as placeholder for empty spaces
def printBoard():
    i = 0
    for row in board:
        print("---------------")
        for place in row:
            i += 1
            if place == '':
                print("|",i,"|", end='')
            else:
                print("|",place,"|", end='')
        print("")
    print("---------------")

#Receives numbers to return x and y position of the 2d list
def getMove():
   #Any other more efficient way for this?
    moveset = {
            '1': (0,0),
            '2': (1,0),
            '3': (2,0),
            '4': (0,1),
            '5': (1,1),
            '6': (2,1),
            '7': (0,2),
            '8': (1,2),
            '9': (2,2)
            }
    print("Please enter the number of the spot to place your move",end='')
    xpos, ypos = moveset[input("> ")]
    return xpos, ypos

#changes the board with received x and y
def placeMove(xpos, ypos, player):
    global board
    board[ypos][xpos] = player.symbol

#Checkes if the spot has been filled
def validateMove(xpos, ypos):
    if board[ypos][xpos] != '':
        print("Cannot place there!")
        return False
    return True

#Checks win conditions; any more efficient way for this as well?
def checkWin():
    for row in board:
        if row[0]==row[1]==row[2]:
            return row[0]
    for i in range(0,3):
        if board[0][i]==board[1][i]==board[2][i]:
            return board[0][i]
    if board[0][0]==board[1][1]==board[2][2]:
        return board[1][1]
    elif board[0][2]==board[1][1]==board[2][0]:
        return board[1][1]
    for row in board:
        for spot in row:
            if spot == '':
                return False
    return 2

def switchPlayer(currentPlayer):
    if currentPlayer.number == 0:
        return 1
    else:
        return 0

#game loop
def game():
    global board

    playerList = [Player(0), Player(1)]
    game = True
    currentPlayer = playerList[0]
    printBoard()

    while game:
        print("Current Player:",currentPlayer.number+1,)
        xpos, ypos = getMove()
        #repeats until valid input
        while not validateMove(xpos, ypos):
            xpos, ypos = getMove()
        placeMove(xpos, ypos, currentPlayer)
        printBoard()
        if checkWin() == currentPlayer.symbol:
            print("Player",currentPlayer.number+1, "wins!")
            game = False
        elif checkWin() == 2:
            print("The game is a draw!")
            game = False
        else:
            currentPlayer = playerList[switchPlayer(currentPlayer)]

#Should I just make the game() the main() function?
def main():
    game()

if __name__ == "__main__":
    main()

symbols = ['O','X']

This will not change, so it doesn't need to be mutable. It's better represented as a string:

symbols = 'OX'

This:

def createBoard():
    a = ['', '', '']
    b = ['', '', '']
    c = ['', '', '']
    return [a, b, c]

can simply be

def create_board():
    return [['']*3 for _ in range(3)]

Note that the convention for Python is snake_case, not camelCase.

getMove can be made more efficient. You do not need a dictionary.

i = int(input('Please enter the number of the '
              'spot to place your move > ')) - 1
return i%3, i//3

You're using board as a global, which is a code smell. Most of these methods, along with the board member, should be put into a class.

This:

if currentPlayer.number == 0:
    return 1
else:
    return 0

can be:

return 1 - current_player.number

Your boolean game variable is unnecessary. Rather than setting it to false, simply break out of the loop.

At the top of the file, there should be a shebang:

#!/usr/bin/env python3


Left Shifting an array of ints The problem I am referring to is here

So basically it's about shifting an array of ints 1 position to the left and relocating the lost first int in the start of the array to the last position at the right:

\$\mathrm{shiftLeft}(\{6, 2, 5, 3\}) → \{2, 5, 3, 6\}\$

\$\mathrm{shiftLeft}(\{1, 2\}) → \{2, 1\}\$

\$\mathrm{shiftLeft}(\{1\}) → \{1\}\$

Please feel free to review the code below:

public int[] shiftLeft(int[] nums) {
    for(int i = 0, start = 0; i < nums.length; i++)
    {
        if(i == 0)
            start = nums[i];
        if(i == (nums.length -1))
        {
            nums[i] = start;
            break;
        }
        nums[i] = nums[i + 1];
    }
    return nums;
}

Also I would like to get rid of the variable start and try to solve it only using the loop iterator i, any suggestions are welcome.

Your current solution is actually pretty good, conceptually. There's nothing wrong with the start variable. I am not sure why you want to remove it. The loop is logically a good solution, but there's a better way than that, though (better because you can make the system do it for you....).

public int[] shiftLeft(int[] nums) {
    if (nums == null || nums.length <= 1) {
        return nums;
    }
    int start = nums[0];
    System.arraycopy(nums, 1, nums, 0, nums.length - 1);
    nums[nums.length - 1] = start;
    return nums;
}

Note that, in addition to using System.arraycopy I also check to see that the input has valid values available....


Take first 12 bits of a number if longer than 12 I need to only take first 12 bits of a number if its longer than a 12 bit number and convert it to a decimal number. So if 7000 is entered than it will return 3500. I also print out the binary form of the new number to check if its converting and far as I can tell it is.

I am wondering if there is a better way to write this code?

#include <iostream>
#include <sstream>
#include <string>
#include <stack>
using namespace std;

int main()
{
    int num, total = 0, x = 0, sizeOfStack, foo[12], i = 0;
    stack <int>  s; // You need the stack;
    stringstream ss;
    unsigned long long int binaryNumber;

    cout << "Please enter a decimal: ";
    cin >> num;

    while (num > 0)
    {
        total = num % 2;
        num /= 2;
        s.push(total); // push 'total'(?) onto the stack
                       //cout << total;
    }
    sizeOfStack = s.size();
    while (x < 12 && x < sizeOfStack) // Another loop to get the values from the stack / now in the correct order
    {
        if (!s.empty())
        {
            foo[i] = s.top();
            s.pop();
        }
        x++; // increment while loop
        i++; //increment array

    }
    for (int w : foo)
    {
        ss << w; // Converting an Integer Array into a Number
    }
    string some = ss.str();
    const char *p = some.c_str();
    binaryNumber = strtoull(p, NULL, 10);
    cout << "The Binary Number is: " << binaryNumber << endl;
    unsigned long long int  dec = 0, rem, num2, base = 1;
    num2 = binaryNumber; //set binarynum2ber to num2
    while (num2 > 0)
    {
        rem = num2 % 10;
        dec = dec + rem * base;
        base = base * 2;
        num2 = num2 / 10;
    }
    cout << "The Decimal Number is: " << dec << endl;
    cout << endl;
    return 0;
}

There is a lot of room for improvement here, but first, let us talk about code style and best practices.

using namespace std; is not a good practice, because it can make your code harder to read if you are using a lot of standard functionality and introduce hard-to-spot name resolution problems. While that is less likely to be an issue in short programs, I still advise you to not use it (creating good habits is worth a lot in the long run!).
Don't do too much on a single line! In particular, don't int num, total = 0, x = 0, sizeOfStack, foo[12], i = 0;, because, on the one hand, you are likely to forget an initializer or a part of a type here and, in the worst case, end up with undefined behavior, and, on the other hand, it is just hard to read for everybody not familiar with your code (such as I). Please split that line up into multiple definitions and declarations. Also, ...
Initialize and use variables as locally as possible. This not only prevents scope pollution, but also increases the readability of your code. As a reviewer, I don't want to (and even cannot) keep a mental map on more than a handful of variables, especially if I have to remember them through large blocks of code where they don't even appear once.
To my understanding at least, the term decimal implies floating point numbers, not just integers. Please think about clarifying, e.g. by writing "decimal integers" or something alike.
Your code does (probably) unexpected thing for numbers smaller than 0. Since you take input as an int and also do virtually no error checking, you could end up with the user inputting a negative number, for which your code will output 0 for the binary and 0 for the decimal representation. If you don't want to accept negative numbers at all, num should be unsigned. If you do, change your implementation to work correctly for those. Either way, you should do input verification on the numbers (or non-numbers) you get.
Don't use std::endl. If you want a newline, simply write '\n'. The reason is that std::endl does more than the name suggests. In particular it writes a '\n' and flushes the underlying buffer which is very rarely what you want or need to do because it seldom yields any benefits and can decrease performance.
Order your includes. In general, alphabetic ordering is expected to enable fast header verification for people reading your code.
Write meaningful comments. In particular, follow the DRY principle in comments as well as code, which means that s.push(total); // push 'total'(?) onto the stack, for example, should go without the comment because it only repeats what the code does. Instead, try to us comments to give reasons as to why you're doing something, and don't overuse them because you've read somewhere that "the more comments, the better". Usefulness and clarity are key.
foo is not exactly what I would call a good variable name. Most of your other names are good, but this one identifier is definitely not. How about something along the lines of binaryDigits instead?
If you have access to anything >=C++11, use nullptr in place of NULL because NULL is fragile and convertible to a lot of things that are not actually pointers.

You asked

  I am wondering if there is a better way to write this code?

and the answer to that is yes. The main idea of your current implementation is to use a stack with your numbers binary digits, which is wasteful (and probably slow) in comparison to just doing the operation in place using bitshifting.

The algorithm that I would propose works like this:

1. Find the highest set bit (= most significant set bit/mssb) in the input
2. Shift the number right so that the mssb is in 12th position

which should be simple enough to implement. Let's walk this through step by step:

There are different algorithms for finding the most significant bit, but usually an iterative approach works well enough. The general idea is to iterate the number bitwise from the most significant to the least significant bit, checking whether the current bit is set. If it is, return the current bit position. In code, this might look like this:

static unsigned find_mssb(unsigned const num) {

    unsigned const num_bit_count = sizeof num * CHAR_BIT;

    unsigned flag = 1u << (num_bit_count - 1u);

    //num_bit_count is also the index of the msb
    unsigned index = num_bit_count;
    while (index) {

        if (num & flag) {
            return index;
        }

        flag >>= 1u;
        --index;
    }

    return 0u;
}

It is important to note that the least significant byte has the index 1, not 0, because we reserve 0 for the occasion that no bit is actually set. Alternatively, if you use either gcc or clang, there is the builtin __builtin_clz which returns the number of leading zeroes, greatly simplifying the computation:

static unsigned find_mssb(unsigned const num) {

    unsigned const num_bit_count = sizeof num * CHAR_BIT;

    //__builtin_clz(0u) is undefined behavior
    if (num) {
        unsigned leading_zeroes = __builtin_clz(num);
        return num_bit_count - leading_zeroes;
    }

    return 0u;
}

Now that we have a way to find the most significant set bit, let's move on to step
Shifting the number right so that the most significant set bit is in the 12th position. This is trivial to do. In code:

unsigned mssb = find_mssb(number);

if (mssb < 12u) {
  //error message, exit, ...
}

number >>= mssb - 12u;

And we're done.

Putting all of this (and some bits of supporting code) together, a reworked version of your program could look something like this:

#include <algorithm>
#include <climits>
#include <iostream>
#include <limits>
#include <sstream>

static unsigned find_mssb(unsigned const num) {

    unsigned const num_bit_count = sizeof num * CHAR_BIT;

#ifdef __GNUG__

    if (num) {
        unsigned leading_zeroes = __builtin_clz(num);
        return num_bit_count - leading_zeroes;
    }

#else
    unsigned flag = 1u << (num_bit_count - 1);

    unsigned index = num_bit_count;
    while (index) {

        if (num & flag) {
            return index;
        }

        flag >>= 1;
        --index;
    }

#endif

    return 0;
}

static std::string binary_representation(unsigned num) {

    std::ostringstream representation;

    while (num) {
        representation << (num & 0x1u);
        num >>= 1;
    }

    std::string str {representation.str()};
    std::reverse(str.begin(), str.end());

    return str;
}

int main() {

    std::cout << "Please enter an integer\n> ";
    unsigned number;
    std::cin >> number;

    unsigned mssb = find_mssb(number);

    if (mssb < 12u) {
        std::cout << "The number you entered is too short. Its binary"
            " representation is only " << mssb << " bits long, which is"
            " less than the required length of 12. In binary, your number is "
            << binary_representation(number) << ".\n";
        return 0;
    }

    number >>= mssb - 12u;
    std::cout << "The trimmed number is "<< number
            << ". The 12 most significant bits are "
            << binary_representation(number) << '\n';
}

Edit: As TobySpeight mentioned in the comments, the bit length of char is not dictated by the standard, so assuming each byte has eight bits is not portable. Instead, the standard library offers CHAR_BIT instead, which is now used in the updated code.


String search algorithm for finding if a long list of long strings string exists in a similarly sized haystack My use case is that I have a list of emails and I need to find if the email is in the chain:

emails = [
    ['    RE: I just got your test || This is a top level email roughly 300+ words in length on average'],
    ['RE:RE: Something | RE: Something | This is another entirely distinct email that is the top level'],
    ['RE: FooBar | A third email that is entirely distinct']
    ... #performance issues start occurring with emails growing to > 50 items
]

Now I would search for an email which is a reply:

test_email = """
A third email that is entirely distinct
"""

Currently I am using a KMP type search but I believe this is inefficient because it searches for multiple copies of the needle. I also believe the in operator is inefficient because it is using the niave method of searching the string.

An implementation of KMP in python I found and modified slightly:

class KMP:
    @classmethod
    def partial(self, pattern):
        """ Calculate partial match table: String -> [Int]"""
        ret = [0]

        for i in range(1, len(pattern)):
            j = ret[i - 1]
            while j > 0 and pattern[j] != pattern[i]:
                j = ret[j - 1]
            ret.append(j + 1 if pattern[j] == pattern[i] else j)
        return ret

    @classmethod
    def search(self, T, P):
        """
        KMP search main algorithm: String -> String -> [Int]
        Return all the matching position of pattern string P in S
        """
        partial, ret, j = KMP.partial(P), [], 0

        for i in range(len(T)):
            while j > 0 and T[i] != P[j]:
                j = partial[j - 1]
            try:
                if T[i] == P[j]: j += 1
            except:
                return False
            if j == len(P):
                return True
        return False

Used here:

for choice in choices: #choice[0] is email in the reply chain
    if current_email == choice[0]:
        incident_type = choice[1]
        break
    elif len(current_email) > len(choice[0]):
        if KMP.search(current_email, choice[0]):
            incident_type = choice[1]
            break
    else:
        if KMP.search(choice[0], current_email):
            incident_type = choice[1]
            break

Should I fix this implementation or scrap it in favor of another algo?

In the post you write:

  I also believe the in operator is inefficient because it is using the naïve method of searching the string.

But if you look at the implementation of Python's in operator for strings, you find that it calls the FASTSEARCH function, which is "based on a mix between Boyer–Moore and Horspool".

The problem of searching many times for strings in a collection of documents is known as full-text search. The approach in the post is to search for the string in each document in turn: this scales linearly with the number and length of the documents. To improve on this scaling behaviour, you need to preprocess the collection of documents into an index. (Note that this only helps if you are searching many times—if you are searching only once, then you can't do better than searching each document.)

Here's a simple demonstration of the full-text search approach:

from collections import defaultdict

class SearchIndex:
    "A full-text search index."

    def __init__(self):
        # Mapping from word to set of documents containing that word.
        self._index = defaultdict(set)

    def add(self, document):
        "Add document to the search index."
        for word in document.split():
            self._index[word].add(document)

    def search(self, query):
        "Generate the documents containing the query string."
        candidates = min((self._index[word] for word in query.split()), key=len)
        for document in candidates:
            if query in document:
                yield document

This works by building a mapping from words to the sets of documents containing each word (an "inverted index"). When a document is added to the index, it is split into words by calling str.split, and the document is added to the mapping for each word. This is conveniently implemented using collections.defaultdict.

To search for a string, the string is also split into words, and the index consulted for each word. The rarest word (the one mapping to the fewest number of documents) is used to get a set of candidates, and then each candidate is searched for the entire string.

This is a very simple approach and there are many refinements you can make. In particular, if you are going to be making queries of the same set of documents over a long period of time then you will want to make your inverted index persistent, and for that you will want a full-text search engine or database.


Transforming data from an array of objects to a nested array of objects I have an array of objects where each object has a datetime key/value pair:

var original = [
  {
    datetime: '2015-07-22 09:00:00'
  },
  {
    datetime: '2015-07-22 11:00:00'
  },
  {
    datetime: '2015-07-23 10:00:00'
  }
]

I need to transform them into a new array with objects where the first key/value pair of each object is the date associated with an array of datetimes from the original array of objects. The second key/value pair is an array of the original objects which have a datetime date that matches the new date.

var new = [
  {
    date: '2015-07-22',
    events: [
      {
        datetime: '2015-07-22 09:00:00'
      },
      {
        datetime: '2015-07-22 11:00:00'
      }
    ]
  },
  {
    date: '2015-07-23',
    events: [
      {
        datetime: '2015-07-23 10:00:00'
      }
    ]
  }
];

Below is my current method of making this transformation happen and it is this method that I am seeking to improve upon. It is clunky. It is convoluted. It is hacky.

I am currently selecting the substring from the first object's datetime as currentDate which only contains the date. Then I'm creating an empty array, new. as well as an object as datum which contains a date key with currentDate as it's value  and an events key with an empty array as its value.

var currentDate = original[0].datetime.substring(0,10); // => '2015-07-22';
var new = [];
var datum = {
  date: currentDate,
  events: []
};

Then I'm using a forEach function on the original array in the following manner:

original.forEach(function(item){

  //if item's date matches currentDate add it to datum object
  if (item.datetime.substr(0,10) === currentDate){
    datum.events.push(item);
  }

  //if item's date does not match then it is the next date
  else {

    //add the previous day's datum object to the new array
    new.push(datum);

    //set new currentDate and set new datum object
    currentDate = item.datetime.substr(0,10);
    datum = {
      date: currentDate,
      events: []
    };

    //push the current item into the new datum array
    datum.events.push(item);
  }
});

//push final day's datum to new array
new.push(datum);

What is a more efficient way to transform this data?

The general idea of your attempt is not so bad.

Its main default is to be not generic enough so you repeat some code. This can be simply avoided using this (already antique) rule: never prepare a container before you know you need it.
So here, instead of immediately creating a first date item, wait for the time you see that it's required.

A fortunate side effect is that it responds to another lack in your code: if original contains a sequence of unsorted events, it will fail. With the new method, all events will be regularly processed.
(look at this fiddle, where I intentionally interweaved dates)

Modified code looks like this:

var original = [
  {
    datetime: '2015-07-22 09:00:00'
  },
  {
    datetime: '2015-07-22 11:00:00'
  },
  {
    datetime: '2015-07-23 10:00:00'
  }
];
var result = [], // (don't like "var new", which is a reserved word!)
    index = [];

for (var i in original) {
  var date = original[i].datetime,
      day = date.substr(0,10),
      j = index.indexOf(day);
  if (j == -1) {
    // first instance for the current day, create it
    result.push({
      date: day,
      event: [],
    });
    // register its index
    index.push(day);
    // get this new index value
    j = index.length - 1;
  }
  // in any case, populate the right day with the current event
  result[j].event.push(date);
}


Palindrome test in Haskell I am new to Haskell and, coming from a OO/procedural programming background, I want to make sure my code follows the functional way of doing things. I built this short module to test if a given string is a palindrome (same backwards and forwards, case-sensitive) and I am simply wondering if this is the most "Haskell" way to do it. Any criticism is greatly appreciated.

module PalindromeTest (isPalindrome) where

isPalindrome :: String -> Bool

isPalindrome w
 | nChars <= 1           = nChars == 1
 | nChars == 2           = firstElem == lastElem
 | firstElem /= lastElem = False
 | firstElem == lastElem = isPalindrome (take (nChars - 2) (tail w))
 where firstElem = head w
       lastElem  = last w
       nChars    = length w

I would just write

isPalindrome w = w == reverse w

Short, and very easy to understand! And in this case it's also a lot more efficient, but that's another story...


Age verification module in Python I wrote an age verification module in Python 2.5 . How can I improve on current_year? import  time perhaps?

current_year = 2016
year_of_birth = int(raw_input('Enter Year Of Birth: '))
age = current_year - year_of_birth
mytext = 'You are %s years old.'
print(mytext % age)
if age < 18:
    print('YOU SHALL NOT PASS!')
else:
    print('Welcome To The Portal.')

Current year

If you don't want the current year to be hardcoded, you could use the method today() from datetime.date.

from datetime import date
current_year = date.today().year

User input

You should always put your user input request in a try/except block, because you never knows what the user will think and do. I'd go with:

def ask_for_birth_year():
    while True:
        try:
            return int(raw_input('Enter Year Of Birth: '))
        except ValueError:
            print('This is not a number, try again.')

This way it will keep asking until the user enters a proper number.

UPDATE (following comment) :

If you need some restriction on the input number, you could try this kind of structure :

def ask_for_birth_year():
    while True:
        try:
            nb = int(raw_input('Enter Year Of Birth: '))
            if nb < 0:  # can be any condition you want, to say 'nb' is invalid
                print('Invalid year')
            else:  # if we arrive here, 'nb' is a positive number, we can stop asking
                break
        except ValueError:
            print('This is not a number, try again.')
    return nb

Other remarks

Since age is an integer, you'll prefer using %d instead of %s (strings) in your print call.

mytext = 'You are %d years old.'

It is also recommended that you put all level-0 code under a __name__ == '__main__' condition, to avoid having it launched later when you import this module. This is a good habit to take, you can read about it in the brand new StackOverflow Documentation here.

if __name__ == '__main__':
    # do stuff

Finally, the limit age (18), is what we call a magic number. It should be avoided, if you plan on making your code grow, and replaced by a meaningful constant.

#at the beginning
LIMIT_AGE = 18

#your 'if' statement
if age < LIMIT_AGE:
    ...

Altogether

from datetime import date

LIMIT_AGE = 18

def ask_for_birth_year():
    while True:
        try:
            nb = int(raw_input('Enter Year Of Birth: '))
            if nb < 0:
                print('Invalid year')
            else:
                break
        except ValueError:
            print('This is not a number, try again.')
    return nb

def print_message(age):
    mytext = 'You are %d years old.'
    print(mytext % age)
    if age < LIMIT_AGE:
        print('YOU SHALL NOT PASS!')
    else:
        print('Welcome To The Portal.')

if __name__ == '__main__':
    year_of_birth = ask_for_birth_year()
    current_year = date.today().year
    age = current_year - year_of_birth
    print_message(age)