Two Plus Two Publishing LLC
Two Plus Two Publishing LLC
 

Go Back   Two Plus Two Poker Forums > >

Notices

Programming Discussions about computer programming

Reply
 
Thread Tools Display Modes
Old Today, 08:29 PM   #33826
well named
poorly undertitled
 
well named's Avatar
 
Join Date: Jun 2007
Location: esse est coesse
Posts: 73,992
Re: ** UnhandledExceptionEventHandler :: OFFICIAL LC / CHATTER THREAD **

Code:
function findFirstRepeat(test) {
  const firstSeen = {};
  
  let candidatePosition = 99999999,
      updateCandidate,
      candidate = false;

  for (let i = 0; i < test.length; i++) {
    const c = test[i];
    updateCandidate = true;

    if (typeof firstSeen[c] === 'undefined') {
      firstSeen[c] = i;
      updateCandidate = false;
    }

    if (updateCandidate && firstSeen[c] < candidatePosition) {
      candidatePosition = firstSeen[c];
      candidate = c;
    }
  }
  
  return candidate
}

console.log(`earliest repeat: ${findFirstRepeat('hello everyone')}`);
Playing in Chrome scratchpad.
well named is offline   Reply With Quote
Old Today, 08:39 PM   #33827
RustyBrooks
Carpal \'Tunnel
 
RustyBrooks's Avatar
 
Join Date: Feb 2006
Location: Austin, TX
Posts: 23,650
Re: ** UnhandledExceptionEventHandler :: OFFICIAL LC / CHATTER THREAD **

Quote:
Originally Posted by suzzer99 View Post
What kind of data structure could you use thatís like a hash map, but automatically sorted by creation order? You could do that, where the key to the hash map is the letter, and the value is the number of occurrences. Then loop over the word once, and then loop over this sorted Hashmap thing until you hit the first instance with a value > 1. So thatís more like N+x instead of N^2.
The string itself is already in order by the order of letters in the string, there's no need for another kind of structure for it
RustyBrooks is offline   Reply With Quote
Old Today, 09:04 PM   #33828
:::grimReaper:::
veteran
 
:::grimReaper:::'s Avatar
 
Join Date: Jul 2010
Posts: 2,362
Re: ** UnhandledExceptionEventHandler :: OFFICIAL LC / CHATTER THREAD **

Quote:
Originally Posted by suzzer99 View Post
What kind of data structure could you use thatís like a hash map, but automatically sorted by creation order? You could do that, where the key to the hash map is the letter, and the value is the number of occurrences. Then loop over the word once, and then loop over this sorted Hashmap thing until you hit the first instance with a value > 1. So thatís more like N+x instead of N^2.
Balanced binary tree, but that's also not efficient, nor do you need counts. Just use a set.

And I stand corrected by Rusty. It does require traversing the string twice, just don't need counts.
:::grimReaper::: is online now   Reply With Quote
Old Today, 09:15 PM   #33829
RustyBrooks
Carpal \'Tunnel
 
RustyBrooks's Avatar
 
Join Date: Feb 2006
Location: Austin, TX
Posts: 23,650
Re: ** UnhandledExceptionEventHandler :: OFFICIAL LC / CHATTER THREAD **

Quote:
Originally Posted by :::grimReaper::: View Post
Balanced binary tree, but that's also not efficient, nor do you need counts. Just use a set.

And I stand corrected by Rusty. It does require traversing the string twice, just don't need counts.
How would you do it without counts? You need to know which letters occur more than once. If you traverse the list once and put every letter in a set, all that tells you is... what letters exist at some point in the string. For "abba" your set would look like {a, b}, how does that help?
RustyBrooks is offline   Reply With Quote
Old Today, 09:21 PM   #33830
well named
poorly undertitled
 
well named's Avatar
 
Join Date: Jun 2007
Location: esse est coesse
Posts: 73,992
Re: ** UnhandledExceptionEventHandler :: OFFICIAL LC / CHATTER THREAD **

My snippet above does it without counts, in one traversal
well named is offline   Reply With Quote
Old Today, 09:28 PM   #33831
RustyBrooks
Carpal \'Tunnel
 
RustyBrooks's Avatar
 
Join Date: Feb 2006
Location: Austin, TX
Posts: 23,650
Re: ** UnhandledExceptionEventHandler :: OFFICIAL LC / CHATTER THREAD **

Quote:
Originally Posted by well named View Post
My snippet above does it without counts, in one traversal
I just read it, that's pretty clever.
RustyBrooks is offline   Reply With Quote
Old Today, 10:19 PM   #33832
jjshabado
Carpal Tunnel
 
jjshabado's Avatar
 
Join Date: Jul 2006
Posts: 22,151
Re: ** UnhandledExceptionEventHandler :: OFFICIAL LC / CHATTER THREAD **

That is pretty clever. Total nitpick, but you can get rid of the 'updateCandidate' by using else if.
jjshabado is offline   Reply With Quote

Reply
      

Thread Tools
Display Modes

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off


Forum Jump


All times are GMT -4. The time now is 10:19 PM.


Powered by vBulletin®
Copyright ©2000 - 2018, Jelsoft Enterprises Ltd.
Copyright © 2008-2017, Two Plus Two Interactive
 
 
Poker Players - Streaming Live Online